Чепурні мультиметоди для сучасного С++
Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Мультиметоди, або ж множинна диспетчеризація, це механізм вибору однієї з декількох функцій в залежності від динамічних типів або значень аргументів[1]. Потреба в такому механізмі виникає, наприклад, в архітектурних рішеннях, де численні класи взаємодіють між собою у специфічний для кожної пари спосіб. C++ на рівні мови не підтримує такий механізм а пропозиції щодо розширення C++ такими інструментами[2] (поки що?) не включені до попереднього плану C++23 [11].
Оскільки потреба в множинній диспетчеризації стара як світ програмування, створено чимало рішень з використанням існуючих інструментів C++ (див. [3], [4], [5], [6], [7], [8], [9], [10]). Проте жодне з них не має чепурного вигляду. Безперечно, чепурність — категорія суб’єктивна і, на думку автора, чепурне рішення це щось просте, сучасне, необтяжливе, неінтрузивне та структуроване. Тобто складність такого рішення відповідає складності задачі, його використання не привносить додаткових залежностей та не ускладнює підтримку коду, не вимагає істотних змін у дизайні проєкту, і кожен елемент рішення вирішує одну потребу[12] чи відповідає за один обов’язок[13].
Метою цієї статті не є просування готового рішення, що підійшло б усім і на усі випадки. Натомість у цій статті ми з вами розглянемо, які підходи можна використати для різних сценаріїв використання.
Для динамічної, часу виконання, диспетчеризації потрібно знати тип об’єкту. C++ має механізми RTTI які можна використати для тих проєктів, що вже використовують RTTI чи можуть собі дозволити таку залежність. Проте рішення не буде чепурним, якщо не надасть альтернативу для проектів, де використання RTTI було б занадто обтяжливим.
Традиційно, подвійна диспетчеризація виконується через віртуальний метод, у якому реалізована ручна диспетчеризація наступного рівня через оператори if
чи switch
. Хоча, з точки зору моделювання даних, ці методи переважно не є природною частиною класів, де вони реалізовані, а радше визначають зовнішні операції над класами об’єктів. То ж вони були б більш органічно представлені як функції[2]. Проте ми не будемо відкидати можливість використання методів.
Моделі даних. У цій статті ми будемо вправлятись на ієрархії фігур та ієрархії виразів калькулятора:
namespace shapes { struct Shape { virtual ~Shape() {} }; struct Rect : Shape { }; struct Circle : Shape {}; struct Square : Rect { }; } namespace calculus { struct Expression { virtual ~Expression() {} }; struct Constant : Expression {}; struct Integer : Constant {}; struct Float : Constant {}; }
Почнемо із моделі calculus. Припустимо, що визначені операції add
, sub
, і ці операції реалізовані як шаблонні функції:
шаблонні функції: template<class A, class B> Expression* add(const A&, const B&); template<class A, class B> Expression* sub(const A&, const B&);
Це дещо спростить перший крок, а ускладнювати будемо поступово.
Отже, наш мультиметод має з’ясувати фактичні типи аргументів, базуючись на цих типах вибрати потрібну функцію із наявних, та викликати обрану функцію. Тут ми окреслили три потреби. Розглянемо їх по черзі.
Вибір функції із наявних. Для створення списку цих функцій використаємо варіадичний шаблон із auto параметрами, щоб використати можна було таким чином:
multidispatcher< add<Integer, Integer>, add<Float, Integer>, add<Integer, Float>, add<Float, Float>>::dispatch(a,b);
Для такого використання наш шаблон має виглядати десь так:
template<auto Entry, auto ... Entries> struct multidispatcher { template<class ... Arguments> static auto dispatch(Arguments& ... arguments) { if (details::entry<Entry>::matches(arguments...)) { return details::entry<Entry>::call(arguments...); } if constexpr (sizeof...(Entries)>0) { return multidispatcher<Entries...>::dispatch(arguments...); } } };
У методі dispatch
ми делегували визначення фактичного типу та виклик функції іншому шаблону entry
, давайте його напишемо:
namespace details { template<auto Method> struct entry; template<class Return, class ... Parameter, Return (*Function)(Parameter...)> struct entry<Function> { template<class ... Argument> static constexpr bool matches(const Argument& ... argument) noexcept { return (expected<Parameter>::matches(argument) and ...); } template<class ... Argument> static Return call(Argument& ... argument) noexcept(noexcept(Function)) { return (*Function)((Parameter)(argument)...); } }; }
Шаблон expected, який ми тут використали, буде визначати тип фактичного аргументу та чи відповідає цей тип очікуваному. Таким чином повна реалізація набуде такого вигляду
namespace details { template<class Parameter> struct expected { template<class Argument> static constexpr bool matches(const Argument& argument) noexcept { return typeid(Parameter) == typeid(argument); } }; template<auto Method> struct entry; template<class Return, class ... Parameter, Return (*Function)(Parameter...)> struct entry<Function> { template<class ... Argument> static constexpr bool matches(const Argument& ... argument) noexcept { return (expected<Parameter>::matches(argument) and ...); } template<class ... Argument> static Return call(Argument& ... argument) noexcept(noexcept(Function)) { return (*Function)((Parameter)(argument)...); } }; } //namespace details template<auto Entry, auto ... Entries> struct multidispatcher { template<class ... Arguments> static auto dispatch(Arguments& ... arguments) { if (details::entry<Entry>::matches(arguments...)) { return details::entry<Entry>::call(arguments...); } if constexpr (sizeof...(Entries)>0) { return multidispatcher<Entries...>::dispatch(arguments...); } } };
Поекспериментувати із цією реалізацією можна за посиланням.
Реалізація вийшла доволі проста, проте, порівнюючи із open methods, вона має певні обмеження:
- довжина списку функцій обмежена максимальною глибиною рекурсії компілятора
- не підтримується коваріантність результату
- не підтримується коваріантність параметрів
- вибирається не найкраща як в open method, а перша-ліпша функція
- немає поділу на virtual та звичайні параметри — усі очікуються virtual
Через друге обмеження ми не можемо використати функцію що повертає коваріантний результат, наприклад таку: Float* sub(const Float&, const Float&)
. Третє, четверте та п’яте обмеження дещо звужують сферу сценаріїв використання. У одному із наступних розділів ми розглянемо як їх обійти. Поки що повернемось до більш критичних обмежень 1 та 2.
Щоб підтримати коваріантність результату нам необхідно задати найбільш загальний тип результату із усіх використаних у функціях. Створимо новий шаблон із додатковим параметром — типом результату:
template<typename ReturnType, auto ... Entries> struct multimethod;
Раз у нас вже є тип результату, ми можемо використати його також щоб замінити рекурсію на згортку параметрів шаблону:
template<typename ReturnType, auto ... Entries> struct multimethod { template<class ... Arguments> static auto dispatch(Arguments& ... arguments) { ReturnType value; if (((details::entry<Entries>::matches(arguments...) and ((value = details::entry<Entries>::call(arguments...)),true)) or ...)) return value; else throw std::logic_error("Missing dispatch entry"); } };
Лінк на модифікований приклад.
Зазначимо, що такий підхід потребує підтримки move семантики для типу результату. Для нашого прикладу це не суттєво, проте для інших сценаріїв використання слід враховувати цю особливість.
Допитливий читач можливо звернув увагу що в останньому прикладі не використовується перевантаження функції sub
:
Float* subf(const Float&, const Float&); Integer* subi(const Integer&, const Integer&);
Це через особливості C++ для перевантажених функцій. Щоб отримати адресу такої функції потрібно задати її тип: (Float* (*)(const Float&, const Float&))&sub
. Цей незручний синтаксис можна спробувати трохи підсолодити шаблоном resolve: resolve<Float*, const Float&, const Float&>{}(&sub)
.
Розглянемо тепер як можна обійти залежність від RTTI, що виникла через наше використання typeid. Для того щоб підтримати сценарії використання без RTTI, прикладна модель має реалізовувати якийсь механізм користувацької ідентифікації та інтроспекції типів (КІІТ). Наприклад, це може бути призначений вручну чи автогенерований числовий ID для кожного класу. Для автогенерації можна використати геш від __PRETTY_FUNCTION__:
template<class Class> constexpr auto class_hash() noexcept { return hash<>(std::string_view(__PRETTY_FUNCTION__)); }
Нажаль, std::hash ще не є constexpr
, тож доведеться написати і свою геш функцію (наприклад, таку як в [14]). Тепер ми можемо призначати ID нашим класам:
static constexpr auto classid = class_hash<Rect>();
Для доступу до classid
напишемо шаблонну функцію classinfo
:
using class_info = size_t; template<class Class> class_info classinfo() noexcept { return Class::classid; }
А для динамічної інтроспекції типів створимо віртуальний метод :
//Shape virtual bool instance_of(const class_info& expected) const noexcept { return classinfo<decltype(*this)>() == expected; } //Rect, Circle bool instance_of(const class_info& expected) const noexcept override { return classinfo<decltype(*this)>() == expected or Shape::instance_of(expected); }
А щоб його використання не створювало залежності від користувацького типу class_info
, заховаємо його за таким фасадом:
//Shape template<class Expected> bool instanceof() const noexcept { return instance_of(classinfo<Expected>()); }
Зверніть увагу, що ці методи не перевантажені. Це спростить допоміжний шаблон has_instanceof
.
Поки ми використовували RTTI, можна було ігнорувати відмінності між віртуальними і звичайними параметрами — typeid
працює із усіма типами, а додаткова перевірка на співпадіння статичних типів прибирається із вихідного коду оптимізатором. Проте із КІІТ нам слід вирішити як розпізнати невіртуальні параметри та як порівнювати типи для них. Для розпізнавання можна встановити таке правило: параметри поліморфічних типів, що передаються як lvalue reference є віртуальними, усі інші — не є такими:
template<class Class> struct is_virtual_parameter { static constexpr bool value = std::is_polymorphic_v<std::remove_reference_t<Class>> and std::is_reference_v<Class>; };
А для перевірки невіртуальних параметрів це може бути, наприклад, is_same, чи is_assignable. Виходячи з такого дизайну КІІТ, модифікуємо наш шаблон expected:
template<class Parameter> struct expected { using parameter_type = std::remove_reference_t<std::remove_cv_t<Parameter>>; template<class Argument> static constexpr bool matches(Argument&& argument) noexcept { if constexpr(has_instanceof<Argument>(0)) { return argument.template instanceof<parameter_type>(); } else { #if __cpp_rtti >= 199711 return typeid(Parameter) == typeid(argument); #else static_assert(not is_virtual_parameter_v<Parameter>, "No class info available"); return is_assignable_parameter_v<Parameter, Argument>; #endif } } };
Поки що наш multimethod шаблон підтримує лише функції. Напишемо підтримку для методів. Перше що необхідно — це відділити об’єкт від решти аргументів, наприклад створивши новий метод що б приймав об’єкт першим аргументом:
// multimethod template<class Target, class ... Arguments> static auto call(Target& target,Arguments& ... arguments) { ReturnType value; if (((details::entry<Entries>::matches(target, arguments...) and ((value = details::entry<Entries>::call(target, arguments...)),true)) or ...)) return value; else throw std::logic_error("Dispatcher failure"); }
Та додати спеціалізацію entry для методів:
template<class Target, class Return, class ... Parameter, Return (Target::*Method)(Parameter...)> struct entry<Method> { template<class Object, class ... Argument> static constexpr bool matches(Object& obj, Argument& ... argument) noexcept { return expected<Target>::matches(obj) and (expected<Parameter>::matches(argument) and ...); } template<class Object, class ... Argument> static Return call(Object& target, Argument& ... argument) { return ((Target&)(target).*Method)((Parameter&)(argument)...); } };
З методами трохи складніше ніж із функціями, бо їх сигнатура може включати також специфікатор const
. Тож знадобиться дві спеціалізації нашого entry, та два методи call. Код для цього прикладу доступний за посиланням.
Завдяки нашій реалізації КІІТ з викликом instance_of базового класу ми також вирішили проблему коваріантності параметрів. Проте щоб вона працювала як слід, першими у списку мають іти функції/методи із більш специфічними параметрами. Впорядкувати список під час компіляції не видається можливим. Натомість, можна додати перевірку часу компіляції — перевіряти чи далі по списку функцій відсутні такі що приймають породжений від поточного клас. Складність такої перевірки можна оцінити як O(kn²) де k кількість параметрів а n — кількість функцій. Слід зауважити, що на великих списках така перевірка може уповільнити компіляцію.
Крім того підтримка довгих списків функцій може стати занадто обтяжливою. Щоб спростити роботу із великою кількістю функцій можна розбити список на групи по однотипному першому параметру, наприклад так:
groupdispatcher< group<Expression*, add<Integer, Float>, add<Integer, Integer>>, group<Expression*, add<Float, Integer>, add<Float, Float>>>::dispatch(a,b);
Можна також повернутись до типового рішення подвійної диспетчеризації через віртуальні методи у якому використати наші чепурні шаблони для наступного рівня диспетчеризації.
Прикінцеві нотатки
- У прикладах, викладених на godbolt.org компілятор gcc генерує оптимізований код із статичною диспетчеризацією. Щоб була задіяна, динамічна диспетчеризація слід рознести test функції прикладів по різних одиницях компіляції.
- Приклади із цієї статті також доступні на gist.github.com:
calculus multidispatcher
calculus multifunction
shapes multimethod - Розглянуте рішення також доступне у вигляді include-only бібліотеки:
github.com/hutorny/multimethods
Перелік джерел
- Мультиметод. Вікіпедія.
https://uk.wikipedia.org/wiki/Мультиметод - P. Pirkelbauer, Y. Solodkyy, B. Stroustrup,
Open Multi-Methods for C++,
www.stroustrup.com/multimethods.pdf - Elsevier B.V.,
EVL: A framework for multi-methods in C++,
www.sciencedirect.com/...cle/pii/S0167642314003360 - D. Shopyrin,
MultiMethods in C++: Finding a complete solution,
www.codeproject.com/...nding-a-complete-solution - Loki Library, Multiple dispatcher,
sourceforge.net/projects/loki-lib Reference/MutiMethod.h - L. Bettini,
Doublecpp — double dispatch in C++,
doublecpp.sourceforge.net - J. Smith,
Draft proposal for adding Multimethods to C++,
www.open-std.org/...cs/papers/2003/n1529.html - stfairy,
Multiple Dispatch and Double Dispatch,
www.codeproject.com/...patch-and-Double-Dispatch - J. Smith,
Multimethods,
www.op59.net/...cu-2003-multimethods.html - D. Shopyrin,
Multimethods in C++ Using Recursive Deferred Dispatching
www.computer.org/...2006/03/s3062/13rRUxBa5ve - V. Voutilainen
To boldly suggest an overall plan for C++23
www.open-std.org/.../papers/2019/p0592r4.html - Wikipedia,
Separation of Concerns
en.wikipedia.org/...ki/Separation_of_concerns - Вікіпедія,
Принцип_єдиного_обов’язку,
https://uk.wikipedia.org/wiki/Принцип_єдиного_обов’язку - E. Hutorny,
FNV-1b hash function with extra rotation
225 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів