понедельник, 21 ноября 2011 г.

Что же такое type erasure?

В данном случае мне кажется, что проще привести пример, который обрисует проблему. Итак, предположим, нам необходим список, содержащий функции со следующей сигнатурой:
typedef int (* nullary_function_returning_int_t)();
_Winnie C++ Colorizer
Окей, скажем мы:
typedef std::list<nullary_function_returning_int_t> func_list_t;
_Winnie C++ Colorizer
Но, что если мы хотим хранить не только функции, но и объекты у которых есть оператор (), возвращающий int. В таком случае, мы могли бы сделать базовый класс:
class nullary_function_base { public:
 virtual ~nullary_function_base(){}

virtual int operator() () = 0; }; typedef std::list<nullary_function_base * > func_list_ptr_t;
_Winnie C++ Colorizer
Но в таком случае мы ограничены только теми объектами, которые являются наследниками класса nullary_function_base. Как быть с функторами, которые получаются, например, в результате использования std::bind1st и пр.? Ведь в этом случае мы уже не можем сделать его наследником nullary_function_base. Или если используется обобщенное программирование и тип функтора просто неизвестен (например, внутри шаблонного класса, функции)?
Вот как раз для решения такой проблемы и используется type erasure.
Итак, исходя из нашего примера, type erasure это нешаблонный объект, который позволяет в себе хранить объекты любого типа, которые удовлетворяют заданному интерфейсу. Это не совсем точное определение, однако оно вполне отражает суть.  В данном примере в качестве интерфейса выступает функция без параметров, возвращающая целое число.
Применим TDD для разработки данного класса. Так будет видно шаги, которые мы предпринимали для конструирования нашего класса.

Группа тестов для декларации интерфейса нашего класса

Итак, первый тест:
#include <gtest/gtest.h> #include <boost/function.hpp> #include "type_erasure.h" typedef boost::function<int ()> sample_signature; TEST(TypeErasure, DeclareInterface) { type_erasure t; sample_signature s(t); }
_Winnie C++ Colorizer
Итак, забегая вперед, скажу, что boost::function как раз и есть реализация того самого type erasure, и ее мы будем использовать для проверки нашей реализации. Итак, наш первый тест фейлится, потому-что наш класс type_erasure еще не имеет оператор (), добавим его, чтобы тест был успешен:
#ifndef TYPE_ERASURE_H #define TYPE_ERASURE_H class type_erasure { public: int operator ()() { } }; #endif // TYPE_ERASURE_H
_Winnie C++ Colorizer
Пишем следующий тест: наш класс должен иметь конструктор, принимающий обычную функцию:
int sample_function_for_test() { return 0; } TEST(TypeErasure, ExpectConstructorWithFunctionPointer) { type_erasure t(sample_function_for_test); }
_Winnie C++ Colorizer
Тест фейлится на этапе компиляции, исправляем: добавляем два конструктора (один для первого теста, один - для второго):
type_erasure() {} explicit type_erasure(nullary_function_returning_int_t /* unused */) {}
_Winnie C++ Colorizer

Делаем следующий тест: наш класс должен иметь конструктор, который принимает любой функтор с удовлетворяющей нас сигнатурой:
int sample_function_with_different_signature(int p1, int p2) { return p1 + p2; } TEST(TypeErasure, ExpectTemplateConstructorForFunctor) { type_erasure t(boost::bind(sample_function_with_different_signature, 42, 100500)); }
_Winnie C++ Colorizer
Здесь мы используем boost::bind, чтобы создать функтор, в принципе можно сделать аналогичный тест для std::bind1st и bind2nd, но это несущественно. И снова, реализация конструктора тривиальна:
template <typename FunctionType> explicit type_erasure(FunctionType /* func */) {}
_Winnie C++ Colorizer

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

Группа тестов для поведения нашего класса
Итак, самое интересное - теперь мы заставим наш класс вести себя как функция, но сначала - немного подготовительной работы. Что будет, если мы создадим объект, но не передадим ему никакой функтор? Естесственно, мы об этом должны сообщить - бросим исключение:
TEST(TypeErasure, ExpectExceptionOnEmptyObject) { type_erasure mustThrowOnCalling; EXPECT_THROW(mustThrowOnCalling(), std::runtime_error); }
_Winnie C++ Colorizer
Соответствующая реализация не менее тривиальна:
int operator ()() { throw std::runtime_error("type_erasure object is not initialised"); }
_Winnie C++ Colorizer

Итак, самое простое осталось позади: мы задекларировали интерфейс и частично поведение класса. Теперь осталось заставить наш класс выполнять полезную деятельность, а именно вести себя как функция, возвращающая целое число - пишем тест:
TEST(TypeErasure, ExpectZeroOnCallingSampleFunction) { type_erasure x(sample_function_for_test); EXPECT_EQ(0, x()); }
_Winnie C++ Colorizer
Сделаем наивную реализацию: просто запомним указатель на функцию (напомню, в TDD, мы должны как можно скорее сделать тест зеленым):
explicit type_erasure(nullary_function_returning_int_t func): mImpl(func) {} /// ... int operator ()() { if (!mImpl) { throw std::runtime_error("type_erasure object is not initialised"); } return mImpl(); } private: nullary_function_returning_int_t mImpl;
_Winnie C++ Colorizer

В двух других конструкторах я инициализирую переменную mImpl нулем, поэтому они не представляют интереса.

Перед тем как написать тест к вызову функтора (аналогичный тесту ExpectTemplateConstructorForFunctor), давайте подумаем, каким образом мы можем спрятать функтор неизвестного типа в нешаблонном классе? Тут нам на помощь приходит наследование, вспомним класс nullary_function_base, мы можем написать любого наследника этого класса, в том числе и шаблонный класс. Аналогичным образом мы можем спрятать и обычную функцию, написав наследника класса nullary_function_base. Я приведу полную реализацию этого класса и двух его наследников: для обычной функции и функтора:
namespace internal { struct nullary_function_base { virtual ~nullary_function_base(){} virtual int operator () () = 0; }; struct simple_function_holder: public nullary_function_base { simple_function_holder(nullary_function_returning_int_t func): mFunc(func) {} virtual int operator() () { BOOST_ASSERT(mFunc && "function pointer is not properly initialised " "for simple_function_holder class"); return mFunc(); } private: nullary_function_returning_int_t mFunc; }; template <typename FunctionType> struct templated_function_holder: public nullary_function_base { templated_function_holder(FunctionType func): mFunc(func){} virtual int operator() () { return mFunc(); } private: FunctionType mFunc; }; }
_Winnie C++ Colorizer

И тут мы должны написать тесты для наших классов, иначе, какие мы TDD-шники :). В принципе, так как реализация всех классов тривиальна, напишем тест только для simple_function_holder: проверим, что assert срабатывает, делаем т.н. death test:
TEST(TypeErasure, ExpectAssertionFailureOnZeroFunctionPointer) { internal::simple_function_holder mustNeverCalled(0); ASSERT_DEATH(mustNeverCalled(), ".*function pointer is not properly initialised.*"); }
_Winnie C++ Colorizer

Я думаю теперь стало понятно, что мы будем хранить указатель на nullary_function_base, и обращаться к нему при вызове оператора (). Для того чтобы безопасно работать с указателем (с точки зрения исключений) логично обернуть указатель в smart_ptr. В принципе, для этого подойдут boost::scoped_ptr и std::unique_ptr, однако мы усложним себе задачу: класс type_erasure можно сделать копируемым, для этого необходимо добавить операторы присваивания и конструктор копирования (см. Правило трёх). Для написания копирующего конструктора и оператора присваивания есть стандартная техника: оператор присваивания пишется через копирующий конструктор и операцию swap. Соответственно, для хранения указателя нам необходим smart_ptr, который обладает семантикой копирования, тут как нельзя кстати оказывается boost::shared_ptr. Данный шаблонный класс предоставляет механизм для не эксклюзивного владения указателем несколькими владельцами. При этом он поддерживает операцию копирования и присваивания. Данный механизм основан на подсчете ссылок (ref-counting). Соответственно, при копировании увеличивается только число ссылок на объект, что делает операцию копирования дешевой. С другой стороны, мы получаем следующую особенность: может получиться ситуация, что для нескольких экземпляров класса type_erasure в памяти хранится один функтор. Это может нам принести неудобства, если функтор обладает каким-то состоянием, и это состояние изменяется, при каждом вызове оператора ().

Итак, с теорией покончено, пишем тесты:
TEST(TypeErasure, ExpectCallingCustomFunctor) { type_erasure t(boost::bind(sample_function_with_different_signature, 42, 100500)); EXPECT_EQ(100542, t()); }
_Winnie C++ Colorizer

Для данного теста я приведу полностью реализацию класса type_erasure (за исключением операторов присваивания и конструкторов копирования):
class type_erasure { public: type_erasure(): mImpl() {} explicit type_erasure(nullary_function_returning_int_t func) : mImpl(boost::make_shared<internal::simple_function_holder>(func)) {} template <typename FunctionType> explicit type_erasure(FunctionType func) : mImpl(boost::make_shared<internal:: templated_function_holder<FunctionType> >(func)) { } int operator ()() { if (!mImpl) { throw std::runtime_error("type_erasure object is not initialised"); } return (*mImpl)(); } private: typedef boost::shared_ptr<internal::nullary_function_base> impl_type; impl_type mImpl; };
_Winnie C++ Colorizer

Итак, как мы видим, реализация класса type_erasure довольно проста и понятна: в соответствующих конструкторах мы просто создаем объект shared_ptr с помощью функции make_shared. Этой функции мы указываем, какой объект необходимо создать (simple_function_holder или templated_function_holder), данная функция является наиболее правильным и рекомендованным способом создания shared_ptr. Как мы видим, от  предыдущей наивной реализации поменялось не так уж и много, и наш type_erasure полностью готов к использованию.

Однако, как я говорил чуть выше, мы сделаем наш класс копируемым, чтобы сымитировать поведение обычного указателя на функцию (обычный указатель на функцию можно копировать). Итак, тесты:
TEST(TypeErasure, ExpectCopyingCtor) { type_erasure t1(sample_function_for_test); type_erasure t2(t1); EXPECT_EQ(0, t2()); }
_Winnie C++ Colorizer

И, на удивление, данный тест проходит успешно, объясню почему. Если компилятор не находит определение копирующего конструктора, то он его генерирует автоматически, используя почленное копирование, а для shared_ptr копирующий конструктор генерируется автоматически, и он правильный (так говорят авторы библиотеки boost::smart_ptr, и у меня нет причин им не верить). Таким образом, копирующий конструктор мы получили автоматически. Но тут есть еще один нюанс, если бы t1 был бы не типа type_erasure, а например, boost::function, то вызвался бы шаблонный конструктор с одним аргументом. Как компилятор различает, что нужно вызывать правильный конструктор? Тут играет роль приоритет поиска подходящей функции (конструктора, в данном случае) из списка определенных. В данном случае шаблонный конструктор вообще никогда не будет использоваться для копирования. В общем случае механизм выбора нужной функций примерно таков:

  • Сначала ищется нешаблонная функция, которая совпадает по всем параметрам.
  • Затем ищутся все частичные специализации шаблонной функции, у которой типы в специализации совпадают с нужными.
  • В конце выбирается шаблонная функция.

Если же мы явно зададим копирующий конструктор в private секции, то мы получим ошибки компиляции в наших тестах, так как шаблонный конструктор не может быть копирующим у нешаблонного класса.

Итак, последние несколько тестов - на оператор присваивания:
TEST(TypeErasure, AssignSimpleFunction) { type_erasure t; t = sample_function_for_test; EXPECT_EQ(0, t()); } TEST(TypeErasure, AssignCustomFunctor) { type_erasure t; t = boost::bind(sample_function_with_different_signature, 42, 100500); EXPECT_EQ(100542, t()); } TEST(TypeErasure, AssignOtherTypeErasure) { type_erasure t1(sample_function_for_test); type_erasure t2; t2 = t1; EXPECT_EQ(0, t2()); EXPECT_EQ(0, t1()); } TEST(TypeErasure, AssignSameTypeErasure) { type_erasure t1(sample_function_for_test); t1 = t1; EXPECT_EQ(0, t1()); }
_Winnie C++ Colorizer

Здесь я позволил себе небольшое отступление от TDD, я написал сразу несколько тестов, и теперь напишу для них реализацию оператора присваивания:
template <typename FunctionType> type_erasure & operator = (FunctionType func) { type_erasure tmp(func); swap(tmp, *this); return *this; } friend void swap(type_erasure & left, type_erasure & right); /// Implementation goes out of class scope inline void swap(type_erasure & left, type_erasure & right); { swap(left.mImpl, right.mImpl); }
_Winnie C++ Colorizer
Для создания правильного оператора присваивания используется Copy-n-Swap idiom. Данный механизм обеспечивает сильную гарантию в случае возникновения исключения при операции присваивания. необходимо заметить, что в оператор присваивания мы передаем func по константной ссылке (вместо передачи по значению, как указано на stackoverflow), это связано с тем, что при различных параметрах шаблона FunctionType для tmp будут вызываться разные конструкторы! Если FunctionType == type_erasure, то вызовется автоматически сгенерированный копирующий конструктор, иначе, вызовется один из конструкторов с одним аргументом.

Итого, финальная реализация всего класса:
#ifndef TYPE_ERASURE_H #define TYPE_ERASURE_H #include <stdexcept> #include <boost/smart_ptr/shared_ptr.hpp> #include <boost/smart_ptr/make_shared.hpp> typedef int (* nullary_function_returning_int_t)(); namespace internal { struct nullary_function_base { virtual ~nullary_function_base(){} virtual int operator () () = 0; }; template <typename FunctionType> struct templated_function_holder: public nullary_function_base { templated_function_holder(FunctionType func): mFunc(func){} virtual int operator() () { return mFunc(); } private: FunctionType mFunc; }; } class type_erasure { public: type_erasure(): mImpl() {} template <typename FunctionType> explicit type_erasure(FunctionType func) : mImpl(boost::make_shared<internal:: templated_function_holder<FunctionType> >(func)) {} template <typename FunctionType> type_erasure & operator = (const FunctionType & func) { type_erasure tmp(func); swap(tmp, *this); return *this; } friend void swap(type_erasure & left, type_erasure & right); int operator ()() { if (!mImpl) { throw std::runtime_error("type_erasure object is not initialised"); } return (*mImpl)(); } private: typedef boost::shared_ptr<internal::nullary_function_base> impl_type; impl_type mImpl; }; inline void swap(type_erasure & left, type_erasure & right) { swap(left.mImpl, right.mImpl); } #endif // TYPE_ERASURE_H
_Winnie C++ Colorizer
Теперь мы вполне можем написать следующий код:
#include "type_erasure.h" #include <list> #include <iostream> #include <boost/bind.hpp> typedef std::list<type_erasure> func_list_t; int func1() { return 1; } int func2(int x) { return x; } struct someStruct { int func3(int x, int y) { return x + y; } }; int main() { func_list_t funcList; funcList.push_back(type_erasure(func1)); funcList.push_back(type_erasure(boost::bind(func2, 5))); someStruct x; funcList.push_back(type_erasure(boost::bind(&someStruct::func3, x, 1, 2))); for (func_list_t::iterator it = funcList.begin(); it != funcList.end(); ++it) { std::cout << (*it)() << std::endl; } return 0; }
_Winnie C++ Colorizer

Если мы уберем explicit из обоих конструкторов type_erasure, то мы сможем избавиться от необходимости создания временного объекта type_erasure при вставке в контейнер, но это уже мелочи.

Итог:
Мы рассмотрели такое понятие как type_erasure, с чем его едят, и как его готовить. Также рассмотрели механизм написания корректного оператора присваивания. Более того, мы сами того не подозревая, использовали type_erasure при разработке нашего собственного type_erasure. Данный паттерн используется в shared_ptr при задании custom deleter. Если покопаться в реализации shared_ptr, то мы найдем класс boost::detail::sp_counted_base, который определяет интерфейс по управлению сырым указателем, и при создании shared_ptr конструируется тот или иной наследник: boost::detail::sp_counted_impl_p, boost::detail::sp_counted_impl_pd или boost::detail::sp_counted_impl_pda соответственно для обычного создания и удаления указателя (c использованием new и delete), с использованием custom deleter и наконец, с использованием custom deleter и custom allocator.

Ну и, конечно, boost::function (или std::function из C++11) представляет собой наиболее полноценную реализацию паттерна type_erasure, именно его следует использовать в разработке. А данный пример служит лишь для демонстрации паттерна type_erasure, ну и конечно TDD ))

Итог 2:
Ну и совсем напоследок - рефакторинг. Утверждается, что вместе с TDD рефакторинг проходит более безболезненно, чем без него))

Итак, мы можем заметить, что конструктор, принимающий nullary_function_returning_int_t не нужен, так как шаблонный конструктор с одним аргументом его прекрасно заменяет. Выкидываем указанный конструктор, и заодно реализацию класса simple_function_holder. Запускаем тесты, и видим, что сломался только один тест - как раз на класс simple_function_holder. В принципе мы можем пожертвовать одним assert-ом и одним тестом ради удаления дублирующего кода. С другой стороны, мы можем написать частичную специализацию для шаблона templated_function_holder для обычного указателя на функцию, и в нем оставить assert и немного модифицировать тест.




3 комментария:

  1. В статье на Хабре есть ошибка - templated_function_holder, это free_function_holder. Видимо, текст писался по старому коду.
    Хабрабыдло не оценит, напиши лучше на RSDN.ru, им нужен контент для журнала.

    ОтветитьУдалить
  2. В целях самообразование, скажите, а зачем FRIEND void swap? Функция вроде не статическая.

    ОтветитьУдалить
    Ответы
    1. Скорее всего, подразумевалась декларация свободной дружественной функции, а ее реализация должна быть вынесена из класса. По всей видимости я ошибся.

      Удалить