[Из песочницы] Иммутабельные данные в C++20.02.2017 13:18

Привет, Хабр! Об иммутабельных данных немало говориться, но о реализации на С++ найти что-то сложно. И, потому, решил данный восполнить пробел в дебютной статье. Тем более, что в языке D есть, а в С++ — нет. Будет много кода и много букв.

О стиле — служебные классы и метафункции используют имена в стиле STL и boost, пользовательские классы в стиле Qt, с которой я в основном и работаю.

Введение

Что из себя представляют иммутабельные данные? Иммутабельные данные — это наш старый знакомый const, только более строгий. В идеале иммутабельность означает контекстно-независиую неизменяемость ни при каких условиях.

По сути иммутабельные данные должны:

• обеспечивать физическую и логическую константность;
• запрещать присваивание нового значения на этапе компиляции;
  все операции должны проводиться над копией, а не над оригиналом.

Иммутабельные данные пришли из функционального программирования и нашли место в параллельном програмировании, т. к. гарантируют отсутсвие побочных эффектов.

Как можно реализовать иммутабельные данные в С++?
В С++ у нас есть (сильно упрощенно):

• значения — объекты фундаментальных типов, экземпляры классов (структур, объединений), перечислений;
• указатели;
  ссылки;
  массивы.

Функции и void не имеет смысл делать иммутабельными. Ссылки тоже не будем делать иммутабельными, для этого есть const reference_wrapper.

Что касается остальных вышеперечисленных типов, то для них можно сделать обертки (а точнее нестандартный защитный заместитель). Что будет в итоге? Цель сделать как-бы модификатор типа, сохранив естественную семантику для работы с объектами данного типа.

Immutable a(1), b(2);

qDebug() << (a + b).value()
         << (a + 1).value()
         << (1 + a).value();

int x[] = { 1, 2, 3, 4, 5 };
Immutable arr(x);
qDebug() << arr[0]

Интерфейс

Общий интерфейс прост — всю работу выполняет базовый класс, который выводится из характеристик (traits):

template 
class Immutable : public immutable::immutable_impl::type {
public:
    static_assert(!std::is_same::value,
                  "nullptr_t cannot used for immutable");
    static_assert(!std::is_volatile::value,
                  "volatile data cannot used for immutable");
    using ImplType = typename immutable::immutable_impl;
    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 
    struct immutable_impl {
        using Type = std::remove_reference_t;
        using type = std::conditional_t<
            std::is_array::value,
                array,
                std::conditional_t <
            std::is_pointer::value,
                pointer,
                std::conditional_t <
            is_smart_pointer::value,
                smart_pointer,
                immutable_value
            >
            >
            >;
        using value_type = typename type::value_type;
    };
}

В качестве ограничений явно запретив все операции присваивания (макросы помогают):

template 
constexpr
Immutable& operator Op=(Immutable &&, RhsType &&) = delete;

А теперь давайте рассотрим как реализованы отдельные компоненты.

Иммутабельные значения

Под значениями (далее value) понимаются объекты фундаментальных типов, экземпляры классов (структур, объединений), перечислений. Для value у на есть класс, который определяет является ли тип классом, структурой или объединением:

template ::value || std::is_union::value>
class immutable_value;

Если да, то для реализации используется используется CRTP:

template 
class immutable_value : 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 test(point);

test().setX(1000); // не поменяет исходный объект
qDebug() << test().isNull() << test().x() << test().y();

Если же тип является встроенным, то реализация будет один-в-один, за исключением базового класса (можно было бы изъвернуться, чтобы соответствовать DRY, но как-то не хотелось усложнять, тем более, что immutable_value делался после остальных…):

template 
class immutable_value
{
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 
    class array;

    template 
    struct array_traits;

    template 
    class array
    {
        typedef       Tp* pointer_type;
        typedef const Tp* const_pointer;
    public:
        using array_type = const Tp[Size];
        using value_type = typename array_traits::value_type;
        using size_type  = typename array_traits::size_type;

        using iterator               = array_iterator;
        using const_iterator         = array_iterator;
        using const_reverse_iterator = std::reverse_iterator;

        constexpr
        explicit
        array(array_type &&array)
            : m_array(std::forward(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 m_array;
    };
}

Для определения типа меньшей размерности используется класс характеристик:

namespace immutable {
    template 
    struct array_traits
    {
        using value_type = std::conditional_t::value == 1,
                                              ArrayType,
                                              array // immutable::array
                                             >;
        using size_type  = std::size_t;
    };
}

который для многомерных массивов для при индексировании возвращает иммутабельный массив меньшей размерности.

Операторы сравнения очень просты:

template
    inline bool
    operator==(const array& one, const array& two)
    {
        return std::equal(one.begin(), one.end(), two.begin());
    }

    template
    inline bool
    operator!=(const array& one, const array& two)
    {
        return !(one == two);
    }

    template
    inline bool
    operator<(const array& a, const array& b)
    {
        return std::lexicographical_compare(a.begin(), a.end(),
                                            b.begin(), b.end());
    }

    template
    inline bool
    operator>(const array& one, const array& two)
    {
        return two < one;
    }

    template
    inline bool
    operator<=(const array& one, const array& two)
    {
        return !(one > two);
    }

    template
    inline bool
    operator>=(const array& one, const array& two)
    {
        return !(one < two);
    }

Иммутабельный итератор

Для работы с иммутабельным массивом используется иммутабельный итератор array_iterator:

namespace immutable {
    template 
    class array;

    template 
    class array_iterator : public std::iterator {
    public:
        using element_type = std::remove_extent_t;

        using value_type = std::conditional_t<
            std::rank::value == 1,
            element_type,
            array
        >;

        using ptr_to_array_type = const element_type *;

        static_assert(std::is_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 
    inline constexpr
    array_iterator operator++(array_iterator &it, int)
    {
        auto res = it;
        ++it;
        return res;
    }

    template 
    inline constexpr
    array_iterator operator--(array_iterator &it, int)
    {
        auto res = it;
        --it;
        return res;
    }

    template 
    inline constexpr
    bool operator != (const array_iterator &a, const array_iterator &b)
    {
        return !(a == b);
    }
}
Отделение массивов от указателей сделано сознательно, несмотря на их близкое родство. 
В итоге, получим что-то вроде:

int x[5] = { 1, 2, 3, 4, 5 };
int y[5] = { 1, 2, 3, 4, 5 };

immutable::array a(x);
immutable::array b(y);

qDebug() << (a == b);

const char str[] = "abcdef";
immutable::array 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 b(y);
immutable::array 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 app(&a);
app->quit();

char c = 'A';
char *pc = &c;
char **ppc = &pc;
char ***pppc = &ppc;

immutable::pointer x(pppc);
qDebug() << ***x;

Кроме вышеперечисленного, immutable: pointer не поддерживает работы со строками в стиле С:

const char *cstr = "test";
immutable::pointer p(cstr);

while(*p++)
      qDebug() << *p;

Данный код будет работать не так как ожидается, т.к. immutable: pointer при инкременте возвращает новый immutable: pointer с другим адресом, а в условном выражении будет проверяться результат инкремента, т.е. значение второго символа строки.

Вернемся к реализации. Класс pointer предоставляет общий интерфейс и, в зависимости от того что из себя представляет Tp (указатель на указатель или прото указатель) использует конкретную реализации pointer_impl.

 template 
    class pointer
    {
    public:
        static_assert( std::is_pointer::value,
                       "Tp must be pointer");
        static_assert(!std::is_volatile::value,
                      "Tp must be nonvolatile pointer");
        static_assert(!std::is_void>::value,
                      "Tp can't be void pointer");

        typedef Tp                                source_type;
        typedef pointer_impl    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 operator*() const
        {
            return *value();
        }

        constexpr
        const pointer_type operator->() const
        {
            return value();
        }

        // добавим неоднозначности 
        template 
        constexpr
        operator T() = delete;

        template 
        constexpr
        operator T() const = delete;
    /**
     * @brief operator [] не реализован сознательно, чтобы не смешивать массивы
     * и указатели.
     *
     * Использование типов-аргументов по-умолчанию помогают компилятору
     * дать более короткое и конкретное сообщение об ошибке
     * (использовании удаленной функции)
     * @return
     */
        template , 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, true>, что можно изобразить так:

pointer_impl{
      pointer_impl
      {
          pointer_impl
          {
              const T *const
          }
      }
}

    template 
    class pointer_impl
    {
    public:
        typedef std::remove_pointer_t 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;

            static_assert(std::is_class::value || std::is_union::value ,
                          "-> used only for class, union or struct");
            return m_value;
        }

    private:
        const pointer_type m_value;
    };

    template 
    class pointer_impl
    {
    public:
        typedef std::remove_pointer_t             source_type;
        typedef pointer_impl pointer_type;
        typedef pointer_impl 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;
    };

namespace immutable
{
    // is_base_of<_Class, _Tp>
    template 
    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::value
                                && GET_SFINAE_RESULT(unref, Tp)
                                && GET_SFINAE_RESULT(raw, Tp);
    };
}

namespace immutable
{
    template 
    class smart_pointer {
    public:
        constexpr
        explicit
        smart_pointer(Type &&ptr) noexcept
            : m_value(std::forward(ptr))
        {

        }
        constexpr
        explicit
        smart_pointer(const Type &ptr)
            : m_value(ptr)
        {

        }

        constexpr
        const auto operator->() const
        {
            const auto res = value().operator->();
            return immutable::pointer(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;
    };
}

#define DECLARE_SFINAE_BASE(Name, ArgType, arg, testexpr)   \
    typedef char SuccessType;                               \
    typedef struct { SuccessType a[2]; } FailureType;       \
    template                              \
    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())) == \
                                       sizeof(typename Name::SuccessType))

    template 
    struct QNonConstOverload
    {
        template 
        Q_DECL_CONSTEXPR auto operator()(R (T::*ptr)(Args...)) const Q_DECL_NOTHROW -> decltype(ptr)
        { return ptr; }

        template 
        static Q_DECL_CONSTEXPR auto of(R (T::*ptr)(Args...)) Q_DECL_NOTHROW -> decltype(ptr)
        { return ptr; }
    };

    template 
    struct QConstOverload
    {
        template 
        Q_DECL_CONSTEXPR auto operator()(R (T::*ptr)(Args...) const) const Q_DECL_NOTHROW -> decltype(ptr)
        { return ptr; }

       template 
        static Q_DECL_CONSTEXPR auto of(R (T::*ptr)(Args...) const) Q_DECL_NOTHROW -> decltype(ptr)
        { return ptr; }
    };

    template 
    struct QOverload : QConstOverload, QNonConstOverload
    {
        using QConstOverload::of;
        using QConstOverload::operator();
        using QNonConstOverload::of;
        using QNonConstOverload::operator();

        template 
        Q_DECL_CONSTEXPR auto operator()(R (*ptr)(Args...)) const Q_DECL_NOTHROW -> decltype(ptr)
        { return ptr; }

        template 
        static Q_DECL_CONSTEXPR auto of(R (*ptr)(Args...)) Q_DECL_NOTHROW -> decltype(ptr)
        { return ptr; }
    };

QPoint point(100, 500);
Immutable test(point);

test().setX(1000); // не поменяет исходный объект
qDebug() << test().isNull() << test().x() << test().y();

int x[] = { 1, 2, 3, 4, 5 };
Immutable arr(x);
qDebug() << arr[0];

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

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

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

Immutable a(1), b(2);

qDebug() << (a + b).value()
         << (a + 1).value()
         << (1 + a).value();

template 
inline constexpr
bool operator==(const Immutable &a, const Immutable &b)
{
    return a.value() == b.value();
}

template 
inline constexpr
bool operator!=(const Immutable &a, const Immutable &b)
{
    return !(a == b);
}

template 
inline constexpr
bool operator>(const Immutable &a, const Immutable &b)
{
    return a.value() > b.value();
}

template 
inline constexpr
bool operator<(const Immutable &a, const Immutable &b)
{
    return b < a;
}

template 
inline constexpr
bool operator>=(const Immutable &a, const Immutable &b)
{
    return !(a < b);
}

template 
inline constexpr
bool operator<=(const Immutable &a, const Immutable &b)
{
    return !(b < a);
}