用stateful meta programming做cpo,并显式注册,可以克服ADL查找无法良好工作的情况,如(built-in types),很不错的思路。
请教一下,在每一个编译单元应该都需要做注册对吧。 那如何保证注册的顺序在所有编译单元都一样呢?
因为这种方案无法覆盖注册,所以会出现相同的key会有不同的注册结果。
网站首页> 文章专栏> C++: 通过对编译时ADL状态机进行封装为CPO提供易用的meta API库
测试环境:
MinGW-w64:
x86_64-8.1.0-posix-seh-rt_v6-rev0
i686-8.1.0-release-posix-dwarf-rt_v6-rev0
g++:
g++ 9.1.0
-std=c++17 -Wnon-template-friend
根据Arthur O’Dwyer的文章所述,CPO当且仅当程序在出现“动词名词化”的需求时才被需要。
“动词名词化”指仿函数或带有特定方法的类, 它通过对象(运行时)或类型(编译时)传递方法。“动词名词化”的需求往往在库的编写过程中产生,它的目的可以有两种,一是允许库先调用特定的方法却不知道其实现,二是向库外传递这个不知其实现的接口。
CPO的这个行为与虚函数非常相似,正如p2279所述。 与虚函数不同的是,虚函数根据this类型产生不同的行为,CPO根据参数不同产生不同行为。
据此可以推知:
由于虚函数的多态性被设计在运行时发挥,所以如果要使其针对参数的不同类型产生不同的行为,只好使用RTTI。
实现原理如下:
↑虽然运行时代价巨大,但上述实现演示了CPO所针对的问题的基本原理
它符合CPO的4项基本性质:
使用例:
↑虽然调用方式复杂,但完成了实现类的动态注册与“名词动词化”的仿函数传递
该CPO对象既可以被当做名词传递给std::for_each,又可以被std::for_each作为动词调用。
缺点:
优点:
由于泛型的多态性被设计在编译期发挥,所以其可以自然地针对不同参数产生不同的行为,但用户自定义接口实现的动态添加需要依赖ADL。
p1895中阐述的tag_invoke设计模式使用首个参数类型作为ADL引导,以区分各种不同的CPO对象,本例采用这种设计模式。
实现原理如下:
↑虽然牺牲了emplace方法,但保留了所有编译期信息
它符合CPO的4项基本性质:
使用例:
↑虽然无法注册基本类型为参数的接口实现,但完成了实现类的编译期跨命名空间注册与“名词动词化”的仿函数传递
缺点:
优点:
对于CPO的RTTI实现:
其优点是由于其emplace()方法依赖于状态机,这个状态就是std::unordered_map。它的状态变化必须发生在运行时。
其缺点是由于其接口调用必须在emplace()方法后,emplace()又发生在运行时,所以其多态必定发生在运行时,这导致了不可避免的类型擦除。
对于CPO的ADL实现:
其优点是由于其不依赖于状态机,所以避免了运行时开销,同时避免了类型擦除以保留所有类型信息。 其缺点是由于其发生于编译期,所以无法使用状态机,这导致所有运行时容器和显式注册的emplace()接口无法有效实现。
为使上述二者优点可以得兼,需要在编译期实现状态机,并进一步实现类型容器。
在此之前,可以首先实现最基础的ADL状态机,依靠constexpr function类型推导形成_Key类型到_Value类型的编译期映射。
实现原理如下:
↑emplace方法的返回类型推导过程中创建了一个save类型的实例
tag类既作为ADL函数tag_storage()的引导参数,又包含了ADL函数的声明,这保证该ADL函数总是可见,此时其返回类型不确定。
save类实例化时,会产生tag_storage(tag<_Key>)函数的唯一定义,确定了其返回值类型。此后ADL函数tag_storage的返回值类型就可以被推导出来了,该类型就是被存储的类型。
此时_Key类型与_Value类型完成了编译期映射,通过decltype()解析load()函数的返回值即可根据_Key获取动态映射的_Value。
使用例:
↑register_cpo()的功能有些不符合直觉,在编译期,其中的内容就已被执行了一次
register_cpo()无需被调用,其中对fake::save()的调用就在编译期隐式地完成了。为了规避这种反直觉的调用方式,可采用'template<typename = void> void register_cpo()'的定义方式刻舟求剑地显式调用。
这样当该函数被首次调用时,它将被实例化,进一步实例化其中的emplace调用,由emplace的返回值类型计算实例化save类,以完成编译期类型映射。
但实际即使这么做,该函数依旧只需被调用,无需被执行,便完成了工作。
这种ADL状态机技术允许对任意CPO传入参数进行按照类型的编译期多态接口查找,它允许CPO显式的实现emplace(),同时解决了ADL无法将基础类型作为参数类型的问题。
此外,该设计模式还允许将特定参数类型映射到泛型接口。在本例中,对int和double的接口实现就通过泛型合并在了一起。
缺点:
优点:
此种编译期ADL类型容器,其模仿的运行时容器为std::unrodered_map<std::type_index, std::type_index>,并且仅实现了它的emplace方法。
上述实现中的load方法等价于存在一个幻想中的语法'to_type()',使得decltype(to_type(some_type_index))允许由type_index在编译期反推出类型,同时仿佛这个哈希表可以在编译期任意运行。
不同于通过包含虚函数的对象实现CPO时,每个CPO需要自行维护一个哈希表,save和load方法相当于在编译期由编译器维护了一个全局类型哈希表。 编译器为了加速ADL查找过程,可能采取哈希表的形式存储参数类型信息。编译器也可能通过简单的遍历进行ADL查找,这种情况下,当注册类型较多时则会拖慢编译速度。
为了覆盖已注册的ADL接口对象,我们需要在编译期模仿std::unrodered_map<std::type_index, std::vector< std::type_index>>的行为。
在实现值为类型数组的类型哈希之前,我们需要先实现编译期计数器。这是由于std::vector中有变量size,模仿其行为必须以编译期size++语义成立为前提。递增操作本身也是一种状态机,也需要使用ADL来实现。
由于std::unrodered_map<std::type_index, std::vector< std::type_index>> table的查找方式是table[type][index],为方便实现,我们可以将下标合并。
这相当于std::unrodered_map<std::pair<std::type_index, std::size_t>, std::type_index>,下标std::size_t可以集成在原先实现的tag中。
由于要实现覆盖的功能只需关注某个_Key类型最后一次注册的映射类型,所以只需实现push()和top()接口。
实现原理如下:
↑emplace方法中简单调用push()方法将新注册的实现类泛型接口压入对应的类型栈
在CPO调用时,通过top()方法取出相应的类型value,通过decltype(value)推导出其类型,之后调用即可。
每个_Key类型映射的多个_Value的栈高由ADL函数tag_size()推导,由于编译器只对该函数进行一次实例化,所以需要_Refresh模板参数刷新其实例化类型。
在tag_size()推导过程中的sfinae参数中传递的if_t和else_t是priority_tag在只有二值的情况下的简化形式。
在向tag_size()传递_Refresh参数前使用空模板类refresh<>包装,是为了避免当_Key与_Value类型相同时刷新tag_size()失败,这种潜在失败可能由编译器缓存了模板实例化结果导致。
更加一般的方法是将栈的读写方法定义为push(_Lambda)和top(_Lambda),在调用时使用push<_Key, _Value>([]{})或top<_Key>([]{}),之后将模板参数推导出的_Lambda类型传递给tag_size,保证总有新的lambda类型迫使编译器重新实例化被调用的模板函数。
使用例:
↑cover_t类型覆盖了std::string到string_t的多态类型映射
缺点:
优点:
由于前文所述实现缺陷已经被尽数修正,因此我们需要根据p2279中所罗列的要求额外提出当前实现的缺点。
额外的缺点:
针对上述4个尚存的缺陷,需要补齐一些元语义,并对其进行一些简单的封装:
为方便充分阐述CPO meta API在CPO定义过程中的功能,例子将不再使用plus_one作为CPO demo。 本例将实现泛型的的for_each CPO,它的动名词语义是“遍历”。
实现原理如下:
↑经过封装的CPO meta API只包含2个接口emplace()和method()
emplace接口用于注册CPO类型-实现类映射。 接受_Key, _Value和_Trait三个参数:
@ _Key 为需要绑定的泛型键类型,具体类型由调用者(CPO的实现类注册方法)任意控制
@ _Value 为需要与_Key绑定的值类型,为_Key的CPO实现类,为CPO提供特定接口
@ _Trait 为向_Key类型压栈时的方式,可选值有override和final,语义与它们再类模型中时一致
其中_Key需要调用者在逻辑上区分special和generic语义,special对应非模板类型、完全偏特化或已经实例化的类型键,generic为泛型实现类,当CPO使用者传入参数类型在special实现中查找脱靶时,所有generic实现类将被遍历测试可用性。
method接口用于通过之前绑定的两类_Key获取可用的CPO实现类。 接受_Special,_Generic,_Policy,_Condition四个参数:
@ _Special 以第一优先级遍历当前已实例化的_Key类型映射的CPO实现类并从ADL状态机容器中返回符合_Condition要求的首个实现类
@ _Generic 以第二优先级遍历所有泛型接口CPO实现类并从ADL状态机容器中返回符合_Condition要求的首个实现类
@ _Policy 可选值为strict和relax,当选择strict时_Special类型栈顶实现类必须符合_Condition要求
@ _Condition 为用于检测泛型接口是否符合CPO调用要求的sfinae-lambda表达式
special先遍历,generic后遍历,二者都是从栈顶向栈底遍历。
policy的strict模式的设计目的是为了避免比如只实现了impl(type &)接口,但实际调用中调用者传递了const type&,导致_Condition进行接口可用性检测时失败,进而导致该实现类被跳过,而实现者对此一无所知的危险情况。
一旦采取strict模式获取method,那么一旦special映射注册者提供的key类型被匹配成功,meta API则要求其提供的接口必须能够通过_Condition检测,否则meta API将以static_assert失败的方式产生编译期错误。
_Condition的使用方式与boost::hana::is_valid()非常类似,这是在C++17环境下对concept的一种简陋的模仿。
emplace和method接口都显式或隐式地要求调用者向其提供lambda表达式作为参数。这是由于在模板成员函数中,参数列表的任意组合都会产生不同的匿名本地lambda类型。
由于ADL状态机完全不符合C++设计哲学,属于对编译器的恶意拷打,所以编译器没有义务保证ADL状态机的状态可以通过meta API 调用被良好的更新并返回。凭借每次实例化时类型都不同的lambda表达式,可以保证CPO meta API在每次编译期调用时,都可以通过使用[]{}作为皮鞭抽打编译器,迫使其迈出类型推导的步伐,以使得调用者获取最新的ADL状态机运行结果。
emplace要求显式地传入[]{}皮鞭类,method则直接使用_Condition参数鞭打编译器。当_Condtion参数为本地lambda表达式时,天生地具有独特的匿名类型,所以无需特殊处理,但不应人为地缓存_Condition的类型,该lambda必须在method方法的本地上下文中内联创建,否则编译器可能返回之前缓存的constexpr函数实例化运行结果。如果此时ADL状态机的状态已经发生变化,假设重新对constexpr函数进行求值,逻辑上应该得到新的结果。但由于编译器缓存了之前的constexpr求值结果,并且假设编译期状态机技术不存在,所以会跳过求值直接返回缓存的结果,导致错误。 因此只要按照例子中给出的方式调用,就不会出现错误。
for_each CPO定义如下:
↑foo::custom::for_each为CPO类型,foo::for_each为CPO实例
foo::custom::for_each提供了4个接口和1个默认实现。
接口:
emplace_special() 用于注册_Key到_Value的映射,既CPO参数类型到CPO实现类的映射。当CPO调用者传入_Key类型时尝试调用_Value::for_each(_Key, _Func)
emplace_generic() 用于注册泛型CPO实现类,当emplace_special注册的实现无法处理调用者传入的_Key类型时,从这些generic实现类中查询可用实现
is_valid() 用于检测对于特定参数类型,是否有已经注册且有效的的CPO实现类,被设计用以显式地构造sfinae友好常量
operator() 该CPO的主方法
在调用CPO meta API时,由for_each的CPO类自行维护special和generic语义,is_valid在此处依旧是对concept的模仿。
需要映射的类型animal:
↑for_each CPO由foo库提供,animal类由bar库提供,接下来user将在自己的程序上下文中向foo库注册bar库中animal类型的CPO meta信息
使用例:
↑foo::for_each是泛型CPO,它允许根据不同的_Tag定义不同的遍历策略组
user命名空间中用户定义了member和output两个tag,目的是分别注册用于序列化遍历和命令行输出的for_each策略组
animal_member_t类向foo::custom::for_each<member>类型注册了用于序列化遍历的bar::animal类的CPO实现类
animal_output_t类向foo::custom::for_each<output>类型注册了用于命令行输出的bar::animal类的CPO实现类
注释掉的animal_output_t::cover_cpo函数用于演示向final语义栈顶实现类注册其他实现类,因此引发编译期覆盖失败的情况
recur_each接受动态传入的for_each CPO,属于典型的 “动词名词化” ,for_each做参数时的语义为“遍历器”。
它根据CPO提供的meta接口is_valid()和if constexpr编译期分支,选择性地递归遍历可遍历的元素。
一旦一个类型注册了for_each CPO实现类,它的任何嵌套排列组合数据结构都将支持泛型递归遍历。
而且这个for_each策略是参数化的,本例演示了member策略组和output策略组,分别代表用于序列化和命令行输出的两种CPO实现。
依靠ADL状态机,CPO meta API基本满足了p2279中提出的所有要求。
美中不足的是,我们手中的皮鞭[]{}违反了C++的设计哲学,这种技术在各编译器间可移植性较差。
同时C++需要一种强制刷新template argument deduction的机制,用来显式地避免编译器偷懒、抄近道或者背答案。
地址: www.purecpp.cn
转载请注明出处!
用stateful meta programming做cpo,并显式注册,可以克服ADL查找无法良好工作的情况,如(built-in types),很不错的思路。
请教一下,在每一个编译单元应该都需要做注册对吧。 那如何保证注册的顺序在所有编译单元都一样呢?
因为这种方案无法覆盖注册,所以会出现相同的key会有不同的注册结果。
purecpp
一个很酷的modern c++开源社区
purecpp社区自2015年创办以来,以“Newer is Better”为理念,相信新技术可以改变世界,一直致力于现代C++研究、应用和技术创新,期望通过现代C++的技术创新来提高企业生产力和效率。
社区坚持只发表原创技术文章,已经累计发表了一千多篇原创C++技术文章;
组织了十几场的C++沙龙和C++大会,有力地促进了国内外C++开发者之间的技术交流;
开源了十几个现代C++项目,被近百家公司所使用,有力地推动了现代C++在企业中的应用。
期待更多的C++爱好者能参与到社区C++社区的建设中来,一起为现代C++开源项目添砖加瓦,一起完善C++基础设施和生态圈。
微信公众号:purecpp, 社区邮箱: purecpp@163.com
很棒的文章!cpo根据参数类型实现多态是一个新思路。这里有没有可能对cpo做一个扩展,让它也可以根据参数个数实现多态?
另外,文中很多元编程技巧值得学习,如果有源码链接也可以发出来供大家学习。