Привет, хабр.
Как-то раз, одним прекрасным воскресным днём писал я код одного своего проекта. Код выглядел как-то так, если упрощать:
const bool exists = WithObject (objectId, [] (const Media::IAudioSource*, const QModelIndex&) { return true; }, [] (const QModelIndex&) { return false; }); WithObject пытается найти некоторый объект по его ID и выполняет первый функтор, если он найден, иначе выполняет второй функтор, если объект не найден. При этом возвращается значение, которое вернул выполненный функтор (подразумевается, что возвращаемый тип второго функтора приводим к типу первого). Функторам при этом передаётся всякая разная полезная информация, полученная в ходе поиска (например, сам объект).
Вышеприведённый код, соответственно, просто проверяет существование объекта, и аргументы, которые WithObject передаёт функторам, оказываются не нужны. Так вот, подумалось мне, неплохо было бы написать такую функцию DropArgs(), чтобы вот такой код
const bool exists = WithObject (objectId, DropArgs ([] { return true; }), DropArgs ([] { return false; })); был корректным. Или, что то же самое, чтобы можно было писать DropArgs ([] { return false; }) (0, 3.14, "foobar");.
И, более того, чтобы ещё если нужны только первые N аргументов, остальные аналогично можно было не указывать: DropArgs ([] (int n) { return n; }) (0, 3.14, "foobar");.
Думать будем на C++14, по возможности пытаясь сохранить совместимость с C++11. На самом деле, из C++14 понадобится только вывод возвращаемого типа функций, да и, читаемости ради, всякие std::result_of_t<> вместо typename std::result_of<>::type, так что у нас есть все шансы.
Итак, начнём с самой функции DropArgs(). Разумно предположить, что функция должна принимать некоторый произвольный функтор и возвращать некоторую обёртку с переопределённым operator(), принимающим произвольное число аргументов. Сформулируем это:
namespace detail { template<typename F> class Dropper { F F_; public: Dropper (const F& f) : F_ (f) // можно было бы написать F_ { f }, но clang <3.6 обижается { } template<typename... Args> auto operator() (Args&&... args) { // вот тут должно происходить всё самое интересное } }; } template<typename F> detail::Dropper<F> DropArgs (const F& f) { return detail::Dropper<F> { f }; } Мы пока не знаем, как описать возвращаемый из operator() тип, поэтому просто оставим auto.
Что должно происходить в operator()? Пока что будем думать в терминах типов: массив Args по условию задачи делится на два подмассива InvokableArgs и Rest такие, что функтор F может быть вызван с аргументами с типами из InvokableArgs, ну а Rest — всё остальное. Например, для мотивирующего кода в начале статьи InvokableArgs пуст для обоих функторов, а Rest равен [const Media::IAudioSource*, QModelIndex] и [QModelIndex] соответственно (с точностью до CV-квалификации).
Обратим внимание, что типы, переданные в operator(), не обязаны полностью совпадать с типами, которые ожидает функтор (если таковые есть), преобразование типов тоже неплохо бы корректно поддерживать. Например если функтор принимает long, а в наш operator() передали int, то ничего страшного, InvokableArgs = [int].
Отметим, что если у функтора есть аргументы по умолчанию, то, вообще говоря, корректное разбиение Args на InvokableArgs и Rest не единственно: можно как передать их конкретные значения в функтор (и он будет вполне вызываем), так и проигнорировать их (при этом, собственно, подставятся аргументы по умолчанию):
auto func = [] (int n, double d, const std::string& s = "hello world", const std::vector<int>& v = {}) {}; auto dropped = DropArgs (func); dropped (1, 3.14); // в предыдущей строке у нас единственный вариант разбиения: // InvokableArgs = [int, double], Rest = [] dropped (1, 3.14, "bye cruel world", { 1, 2, 3 }); // один вариант разбиения: // InvokableArgs = [int, double, std::string, std::vector<int>], Rest = [] // func вызовется с параметрами n = 1, d = 3.14, s = "bye cruel world", v = { 1, 2, 3 } // // второй вариант разбиения: // InvokableArgs = [int, double, std::string], Rest = [std::vector<int>] // func вызовется с параметрами n = 1, d = 3.14, s = "bye cruel world", v = {} // // третий вариант разбиения: // InvokableArgs = [int, double], Rest = [std::string, std::vector<int>] // func вызовется с параметрами n = 1, d = 3.14, s = "hello world", v = {} По очевидным причинам имеет смысл стремиться выбирать разбиения с максимальным InvokableArgs (первый вариант в примере выше).
Так вот, в operator() попробуем выяснить максимальный InvokableArgs для данного Args.
Как это можно сделать? Можно пытаться вызвать наш функтор F с полным списком Args. Получилось — хорошо, не получилось — откусываем тип с конца списка и пробуем ещё раз, и так далее, пока не придём к успеху (или пока типы не кончатся, но это будет означать, что InvokableArgs не существует для данного Args, что есть ошибка).
Напишем вспомогательный класс-хранитель типов (хотя и std::tuple бы сошёл, но хочется гарантированно избежать оверхеда, сделав класс пустым):
namespace detail { template<typename...> struct Typelist {}; } Единственная цель и смысл жизни этого класса — хранить конкретный список типов, с которым он инстанциирован.
Откусывать тип с конца списка типов эффективно за O(1) инстанциирований, насколько мне известно, невозможно, самое оптимальное — O(logn), да и то требует некоторых дополнительных трюков и манипуляций, посему оставляется читателю в качестве упражнения, а мы реализуем тупой лобовой O(n)-алгоритм: развернём список, откусим у него первый элемент и развернём ещё раз. И пусть компилятор пыхтит!
Откусывать первый элемент легко и просто, так что начнём с функции, которую назовём Tail, в духе, приятном и понятном всем функциональщикам:
namespace detail { template<template<typename...> class List, typename H, typename... T> constexpr List<T...> Tail (List<H, T...>) { return {}; } } Обратим внимание, что возвращаемое значение, равно как и значение аргумента, нас совершеннейше не волнуют, имеют значение лишь их типы. Похожий паттерн будет преследовать нас на протяжении всей статьи. Кроме того, пожалуй, мы могли бы сразу договориться везде использовать конкретный Typelist вместо обобщённого аргумента шаблона List, но приведённый выше подход представляется более общным.
Для разворота списка нам сначала понадобится функция склейки двух списков типов:
namespace detail { template<template<typename...> class List, typename... Args1, typename... Args2> constexpr List<Args1..., Args2...> Concat (List<Args1...>, List<Args2...>) { return {}; } } Теперь можно и рекурсивно список развернуть, переложив на C++ следующий подозрительно похожий на Haskell псевдокод reverse [] = []; reverse (x:xs) = reverse xs ++ [x]:
namespace detail { template<template<typename...> class List> constexpr List<> Reverse (List<>) { return {}; } template<template<typename...> class List, typename Head, typename... Tail> constexpr auto Reverse (List<Head, Tail...>) -> decltype (Concat (Reverse (List<Tail...> {}), List<Head> {})) { return {}; } } Однако, тут не всё так гладко, если вдаваться в мелочи.
А в C++14 бы такой проблемы и не было, ибо мы могли бы вторую функцию переписать как
template<template<typename...> class List, typename Head, typename... Tail> constexpr auto Reverse (List<Head, Tail...>) { return Concat (Reverse (List<Tail...> {}), List<Head> {}); } и не знать вообще никаких проблем: компилятор сам выведет корректный тип.
Отлично, теперь мы готовы, наконец, выяснить максимальный список типов, с которым наш искомый функтор всё ещё может быть вызван. Для этого напишем функцию GetInvokablePart(), которая, будучи инстанциированной нашим функтором и списком типов Args из Dropper::operator(), будет иметь тип возвращаемый тип Typelist<InvokableArgs>, инстанциированный соответствующими аргументами.
template<typename F, template<typename...> class List, typename... Args> constexpr List<Args...> GetInvokablePartImpl (int, List<Args...>, typename std::result_of<F (Args...)>::type* = nullptr) { return {}; } template<typename F, template<typename...> class List> constexpr Typelist<> GetInvokablePartImpl (float, List<>) { return {}; } template<typename F, template<typename...> class List, typename... Args> constexpr auto GetInvokablePartImpl (float, List<Args...> list) -> decltype (GetInvokablePartImpl<F> (0, Reverse (Tail (Reverse (list))))) { return {}; } template<typename F, typename... Args> constexpr auto GetInvokablePart () -> decltype (GetInvokablePartImpl<F> (0, Typelist<Args...> {})) { return {}; } Что здесь вообще происходит и как это работает? А здесь происходит вполне себе обычное SFINAE.
Начнём с функции GetInvokablePart(). Её возвращаемый тип равен возвращаемому типу функции GetInvokablePartImpl(), вызванной с данным списком типов (пока что полным Args). Как можно видеть, функций GetInvokablePartImpl() три штуки, и вывод вызываемого списка типов спрятан как раз в логике выбора каждой конкретной перегрузки. В этой логике мы опираемся на два факта (если сильно упрощать правила выбора перегруженных функций и специфицировать их для нашего конкретного случая):
- Если для вызова подходят две функции, в остальном одинаково равные, но у одной тип первого аргумента —
int, а у второй —float, то при передаче значения 0 выберется перегрузка сint. - Первая функция (с
std::result_of) существует только тогда, когда существует типresult_of, а существует он только тогда, когда функторFможет быть вызван с аргументами типовArgs. Иначе эта перегрузка убирается из рассмотрения.
Иными словами, если с текущим набором Args функтор вызываем, то выбирается первая перегрузка, и тип возвращаемого значения GetInvokablePart() равен Typelist<Args...>. Иначе выбирается третья перегрузка (если Args непуст, иначе — вторая, и там по-хорошему надо показывать человекочитаемое сообщение об ошибке, ибо мы все аргументы пооткусывали уже, а функция всё ещё не вызывается). Третья перегрузка откусывает последний элемент списка типов и пробует снова, а её возвращаемый тип, соответственно, равен возвращаемому типу рекурсивно вызванной функции с меньшим списком типов, возвращаемый тип которой равен… В общем, таким образом мы либо встретим, наконец, последовательность Args, с которой функтор можно вызвать, и тип функции будет соответствовать этому типу, либо упрёмся во вторую перегрузку, и это ошибка.
Итак, таким нехитрым образом рекурсивно можно вывести возвращаемый тип GetInvokablePart(). Добавим это в наш operator():
template<typename... Args> auto operator() (Args&&... args) { auto invokableList = GetInvokablePart<F, Args...> (); } Если мы теперь попробуем использовать DropArgs() для любого разбиения с непустым Rest, то уже сейчас увидим, что gcc не может корректно использовать GetInvokablePart(). Почему?
Как я уже писал в спойлере чуть выше, объявление
template<typename F, template<typename...> class List, typename... Args> constexpr auto GetInvokablePartImpl (float, List<Args...> list) -> decltype (GetInvokablePartImpl<F> (0, Reverse (Tail (Reverse (list))))) не очень корректно с точки зрения C++: точкой объявления функции при наличии trailing return type specifier является, собственно, окончание trailing return type specifier, поэтому внутри него самого ссылаться на функцию нельзя (есть пропозалы на тему того, чтобы это исправить и считать точкой объявления функции символ ->, но пока что имеем то, что имеем). Есть два способа это починить:
- Забить на C++11 и писать на C++14 без всяких trailing return type’ов,
как-то так.template<typename F, template<typename...> class List, typename... Args> constexpr List<Args...> GetInvokablePartImpl (int, List<Args...>, typename std::result_of<F (Args...)>::type* = nullptr) { return {}; } template<typename F, template<typename...> class List> constexpr Typelist<> GetInvokablePartImpl (float, List<>) { return {}; } template<typename F, template<typename...> class List, typename... Args> constexpr auto GetInvokablePartImpl (float, List<Args...> list) { return GetInvokablePartImpl<F> (0, Reverse (Tail (Reverse (list)))); } template<typename F, typename... Args> constexpr auto GetInvokablePart () { return GetInvokablePartImpl<F> (0, Typelist<Args...> {}); } - Переписать третью перегрузку с костылями, так чтобы вынести ссылку функции на саму себя, «развязав» её с объявлением возвращаемого типа. Для этого добавим вспомогательную структуру, тип внутри которой будет равен типу соответствующей функции, а внутри самой функции будем ссылаться на эту структуру. Как-то так:
template<typename F, typename List> struct InvokableType; template<typename F, template<typename...> class List, typename... Args> constexpr auto GetInvokablePartImpl (float, List<Args...> list) -> typename InvokableType<F, decltype (Reverse (Tail (Reverse (list))))>::RetType_t { return {}; } template<typename F, typename List> struct InvokableType { using RetType_t = decltype (GetInvokablePartImpl<F> (0, List {})); };
Итак, что мы имеем на данный момент. У нас есть полный список аргументов Args, переданный в operator(), и некоторое его начало InvokableArgs. Что дальше? А дальше попробуем взять и передать этот список, в некоторую вспомогательную функцию, которая и будет заниматься вызовом функции. Наивно напишем подобный код внутри класса Dropper:
template<typename... Args> auto operator() (Args&&... args) { auto invokableList = GetInvokablePart<F, Args...> (); return Invoke (invokableList, std::forward<Args> (args)...); } private: template<typename... InvokableArgs, typename... Rest> auto Invoke (Typelist<InvokableArgs...>, InvokableArgs&&... args, Rest&&...) { return F_ (std::forward<InvokableArgs> (args)...); } понадеявшись, что компилятор достаточно умный, выведет InvokableArgs из первого аргумента шаблона, а Rest — из остатка. Однако, наши надежды не оправдаются.
Что ж, попробуем указать Rest руками. Как это лучше всего сделать? На самом деле, достаточно просто откусить с головы столько элементов, сколько содержится в InvokableArgs. Для этого нам понадобится функция подсчёта числа элементов в списке типов:
template<template<typename...> class List, typename... Args> constexpr size_t Length (List<Args...>) { return sizeof... (Args); } и функция отбрасывания первых N аргументов. Например:
template<int N, typename List> struct DropImpl { using Result_t = typename DropImpl<N - 1, decltype (Tail (List {}))>::Result_t; }; template<typename List> struct DropImpl<0, List> { using Result_t = List; }; template<int N, template<typename...> class List, typename... Args> constexpr typename DropImpl<N, List<Args...>>::Result_t Drop (List<Args...>) { return {}; }
Drop не через структуру, как здесь, а через рекурсивно вызываемые функции с постоянно уменьшающимся счётчиком, отбрасываемые по SFINAE при достижении счётчиком нуля, то gcc 4.9 уходит в очень забавный бесконечный цикл инстанциаций и не способен выйти из него самостоятельно. Похоже, проблема в том, что он инстанциирует возвращаемый тип функции до отбрасывания её по SFINAE в списке аргументов. Не уверен, впрочем, что это баг. С учётом вышесказанного, модифицируем наш Dropper следующим образом:
template<typename... Args> auto operator() (Args&&... args) { constexpr auto invokableList = GetInvokablePart<F, Args...> (); auto ignoreList = Drop<Length (invokableList)> (Typelist<Args...> {}); return Invoke (invokableList, ignoreList, std::forward<Args> (args)...); } private: template<typename... InvokableArgs, typename... Rest> auto Invoke (Typelist<InvokableArgs...>, Typelist<Rest...>, InvokableArgs&&... args, Rest&&...) { return F_ (std::forward<InvokableArgs> (args)...); } Не забываем constexpr у invokableList, иначе пришлось бы писать что-то вроде Drop<Length (decltype (invokableList) {})>.
Отлично! Кажется, это всё, работает!
На самом деле нет. gcc плюётся не очень информативной ошибкой:
prog.cc: In instantiation of 'void detail::Dropper<F>::operator()(Args&& ...) [with Args = {int&, double}; F = main()::<lambda(int)>]': prog.cc:147:35: required from here prog.cc:125:67: error: no matching function for call to 'detail::Dropper<main()::<lambda(int)> >::Invoke(const detail::Typelist<int&>&, detail::Typelist<double>&, int&, double)' Invoke (invokableList, ignoreList, std::forward<Args> (args)...); ^ prog.cc:125:67: note: candidate is: prog.cc:129:8: note: template<class ... InvokableArgs, class ... Rest> void detail::Dropper<F>::Invoke(detail::Typelist<InvokableArgs ...>, detail::Typelist<Rest ...>, InvokableArgs&& ..., Rest&& ...) [with InvokableArgs = {InvokableArgs ...}; Rest = {Rest ...}; F = main()::<lambda(int)>] void Invoke (Typelist<InvokableArgs...>, Typelist<Rest...>, InvokableArgs&&... args, Rest&&...) ^ prog.cc:129:8: note: template argument deduction/substitution failed: prog.cc:125:67: note: inconsistent parameter pack deduction with '' and '' Invoke (invokableList, ignoreList, std::forward<Args> (args)...); ^ Однако, судя по почему-то кажущемуся очень смешным отрывку inconsistent parameter pack deduction with '' and '', gcc снесло голову при попытке сматчить InvokableArgs из первого аргумента (который Typelist), и из остатка списка аргументов. Что же делать?
Обычно к моей печали, но к локальному счастью в данном случае, в C++ ещё не завезли многоуровневый вывод типов вроде Хиндли-Милнера, поэтому в данном конкретном случае можно просто запретить компилятору выводить типы из третьего и последующих аргументов, для чего их надо обернуть в специальную тупую обёртку. Начнём с обёртки, которая не делает вообще ничего:
template<typename T> struct Dumbifier { using Type_t = T; }; template<typename T> using Dumbify = typename Dumbifier<T>::Type_t; Тогда Dumbify<Args...> просто-напросто равно Args..., но компилятор не будет пытаться это выводить.
Осталось обновить Invoke:
template<typename... InvokableArgs, typename... Rest> auto Invoke (Typelist<InvokableArgs...>, Typelist<Rest...>, Dumbify<InvokableArgs>... args, Dumbify<Rest>...) { return F_ (args...); } Для полной совместимости с C++11 осталось лишь вручную указать возвращаемые типы operator() и Invoke, это вместе с анализом perfect forwarding-качеств приведённого решения остаётся пытливому читателю в качестве упражнения.
namespace detail { template<typename... Args> struct Typelist { }; template<template<typename...> class List, typename H, typename... T> constexpr List<T...> Tail (List<H, T...>) { return {}; } template<int N, typename List> struct DropImpl { using Result_t = typename DropImpl<N - 1, decltype (Tail (List {}))>::Result_t; }; template<typename List> struct DropImpl<0, List> { using Result_t = List; }; template<int N, template<typename...> class List, typename... Args> constexpr typename DropImpl<N, List<Args...>>::Result_t Drop (List<Args...>) { return {}; } template<template<typename...> class List, typename... Args1, typename... Args2> constexpr List<Args1..., Args2...> Concat (List<Args1...>, List<Args2...>) { return {}; } template<template<typename...> class List> constexpr List<> Reverse (List<>) { return {}; } template<template<typename...> class List, typename Head, typename... Tail> constexpr auto Reverse (List<Head, Tail...>) -> decltype (Concat (Reverse (List<Tail...> {}), List<Head> {})) { return {}; } template<typename F, template<typename...> class List, typename... Args> constexpr List<Args...> GetInvokablePartImpl (int, List<Args...>, typename std::result_of<F (Args...)>::type* = nullptr) { return {}; } template<typename F, template<typename...> class List> constexpr Typelist<> GetInvokablePartImpl (float, List<>) { return {}; } template<typename F, typename List> struct InvokableType; template<typename F, template<typename...> class List, typename... Args> constexpr auto GetInvokablePartImpl (float, List<Args...> list) -> typename InvokableType<F, decltype (Reverse (Tail (Reverse (list))))>::RetType_t { return {}; } template<typename F, typename List> struct InvokableType { using RetType_t = decltype (GetInvokablePartImpl<F> (0, List {})); }; template<typename F, typename... Args> constexpr auto GetInvokablePart () -> decltype (GetInvokablePartImpl<F> (0, Typelist<Args...> {})) { return GetInvokablePartImpl<F> (0, Typelist<Args...> {}); } template<template<typename...> class List, typename... Args> constexpr size_t Length (List<Args...>) { return sizeof... (Args); } template<typename T> struct Dumbifier { using Type_t = T; }; template<typename T> using Dumbify = typename Dumbifier<T>::Type_t; template<typename F, typename List> struct InvokableResGetter; template<typename F, template<typename...> class List, typename... Args> struct InvokableResGetter<F, List<Args...>> { using RetType_t = typename std::result_of<F (Args...)>::type; }; template<typename F> class Dropper { F F_; public: Dropper (const F& f) : F_ (f) { } template<typename... Args> auto operator() (Args... args) -> typename InvokableResGetter<F, decltype (GetInvokablePart<F, Args...> ())>::RetType_t { constexpr auto invokableList = GetInvokablePart<F, Args...> (); auto ignoreList = Drop<Length (invokableList)> (Typelist<Args...> {}); return Invoke (invokableList, ignoreList, std::forward<Args> (args)...); } private: template<typename... InvokableArgs, typename... Rest> auto Invoke (Typelist<InvokableArgs...>, Typelist<Rest...>, Dumbify<InvokableArgs>... args, Dumbify<Rest>...) -> typename std::result_of<F (InvokableArgs...)>::type { return F_ (std::forward<InvokableArgs> (args)...); } }; } template<typename F> detail::Dropper<F> DropArgs (const F& f) { return detail::Dropper<F> { f }; }
В качестве послесловия проведём небольшой анализ оверхеда решения.
Дизасм функции
int Bar () { return DropArgs ([] (int n) { return n * 2; }) (1, 2.5); } показывает, что все gcc 4.8+, похоже, достаточно умны, чтобы всю функцию свести к return 2, равно как и clang 3.3+. Молодцы. icc 13.0, к сожалению, код собрать не может.
Если же написать
int Bar () { volatile int n = 1; return DropArgs ([] (int n) { return n * 2; }) (n, 2.5); } то снова все компиляторы закономерно разворачивают это в что-то вроде
Bar(): movl $1, -4(%rsp) movl -4(%rsp), %eax addl %eax, %eax ret Придумать сходу случай, когда возникал бы существенный оверхед, мне не удалось.
ссылка на оригинал статьи http://habrahabr.ru/post/264157/
Добавить комментарий