网站首页> 文章专栏> C++: 通过对编译时ADL状态机进行封装为CPO提供易用的meta API库
C++: 通过对编译时ADL状态机进行封装为CPO提供易用的meta API库
编辑时间:2022-02-10 03:06:19 作者:loop 4条评论

测试环境:

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

示例代码

CPO自顶向下分析与各种实现原理阐述

CPO的定义

根据Arthur O’Dwyer的文章所述,CPO当且仅当程序在出现“动词名词化”的需求时才被需要。

“动词名词化”指仿函数或带有特定方法的类, 它通过对象(运行时)或类型(编译时)传递方法。“动词名词化”的需求往往在库的编写过程中产生,它的目的可以有两种,一是允许库先调用特定的方法却不知道其实现,二是向库外传递这个不知其实现的接口。

CPO的这个行为与虚函数非常相似,正如p2279所述。 与虚函数不同的是,虚函数根据this类型产生不同的行为,CPO根据参数不同产生不同行为。

据此可以推知:

  1. CPO为不同参数对外提供统一的虚接口
  2. CPO接口类不提供针对特定参数类型的实现而由用户注册
  3. CPO的行为类似单例
  4. CPO接口在被调用前应该已取得所有期望注册的实现类的实例或定义

CPO的虚函数对象实现

由于虚函数的多态性被设计在运行时发挥,所以如果要使其针对参数的不同类型产生不同的行为,只好使用RTTI。

RTTI方式实现CPO

实现原理如下:

alt

↑虽然运行时代价巨大,但上述实现演示了CPO所针对的问题的基本原理

它符合CPO的4项基本性质:

  1. 它通过全局仿函数类型'plus_one_cpo'提供虚接口
  2. 它的实现类可以通过emplace()函数进行动态注册
  3. 它的没有动态成员
  4. 它针对特定std::type_index相关类型的实现可以在接口被调用前完成注册

使用例:

alt

↑虽然调用方式复杂,但完成了实现类的动态注册与“名词动词化”的仿函数传递

该CPO对象既可以被当做名词传递给std::for_each,又可以被std::for_each作为动词调用。

以RTTI实现CPO优缺点分析

缺点:

  1. 无法直接接受带有类型信息的参数,需要to_poly()进行转换
  2. 运行时查询hash表,效率差
  3. 需要在运行时调用前提前注册CPO实现类
  4. 如参数类型不在已注册的实现类中,需要到运行时才能发现
  5. 其虚接口无法返回带有不同类型信息的返回值

优点:

  1. 可以实现emplace方法
  2. 如实现需要,可以对已存在的实现类映射关系进行覆盖(例子中未实现,既调用unordered_map的方法)

CPO的泛型接口对象实现

由于泛型的多态性被设计在编译期发挥,所以其可以自然地针对不同参数产生不同的行为,但用户自定义接口实现的动态添加需要依赖ADL。

p1895中阐述的tag_invoke设计模式使用首个参数类型作为ADL引导,以区分各种不同的CPO对象,本例采用这种设计模式。

ADL/tag_invoke方式实现CPO

实现原理如下:

alt

↑虽然牺牲了emplace方法,但保留了所有编译期信息

它符合CPO的4项基本性质:

  1. 它通过全局仿函数类型'plus_one_cpo'提供虚接口
  2. 它的实现类可以通过重载一般函数tag_invoke()进行动态注册
  3. 它的没有动态成员
  4. 它针对特定类型的实现可以在编译期完成注册

使用例:

alt

↑虽然无法注册基本类型为参数的接口实现,但完成了实现类的编译期跨命名空间注册与“名词动词化”的仿函数传递

以ADL/tag_invoke实现CPO优缺点分析

缺点:

  1. 无法注册处理基本类型的ADL接口函数
  2. 无法实现emplace方法
  3. 无法覆盖已注册的ADL接口函数

优点:

  1. 不丢失参数的不同类型信息
  2. 无运行时开销
  3. 无需运行时初始化注册接口
  4. 如参数类型不在已注册的实现类中,编译期即可发现
  5. 不丢失返回值的不同类型信息

造成上述2种CPO实现方式优缺点的实质原因

对于CPO的RTTI实现:

其优点是由于其emplace()方法依赖于状态机,这个状态就是std::unordered_map。它的状态变化必须发生在运行时。

其缺点是由于其接口调用必须在emplace()方法后,emplace()又发生在运行时,所以其多态必定发生在运行时,这导致了不可避免的类型擦除。

对于CPO的ADL实现:

其优点是由于其不依赖于状态机,所以避免了运行时开销,同时避免了类型擦除以保留所有类型信息。 其缺点是由于其发生于编译期,所以无法使用状态机,这导致所有运行时容器和显式注册的emplace()接口无法有效实现。

编译期状态机

为使上述二者优点可以得兼,需要在编译期实现状态机,并进一步实现类型容器。

编译期ADL简单类型映射

在此之前,可以首先实现最基础的ADL状态机,依靠constexpr function类型推导形成_Key类型到_Value类型的编译期映射。

ADL类型映射实现CPO

实现原理如下:

alt

↑emplace方法的返回类型推导过程中创建了一个save类型的实例

tag类既作为ADL函数tag_storage()的引导参数,又包含了ADL函数的声明,这保证该ADL函数总是可见,此时其返回类型不确定。

save类实例化时,会产生tag_storage(tag<_Key>)函数的唯一定义,确定了其返回值类型。此后ADL函数tag_storage的返回值类型就可以被推导出来了,该类型就是被存储的类型。

此时_Key类型与_Value类型完成了编译期映射,通过decltype()解析load()函数的返回值即可根据_Key获取动态映射的_Value。

使用例:

alt

↑register_cpo()的功能有些不符合直觉,在编译期,其中的内容就已被执行了一次

register_cpo()无需被调用,其中对fake::save()的调用就在编译期隐式地完成了。为了规避这种反直觉的调用方式,可采用'template<typename = void> void register_cpo()'的定义方式刻舟求剑地显式调用。

这样当该函数被首次调用时,它将被实例化,进一步实例化其中的emplace调用,由emplace的返回值类型计算实例化save类,以完成编译期类型映射。

但实际即使这么做,该函数依旧只需被调用,无需被执行,便完成了工作。

这种ADL状态机技术允许对任意CPO传入参数进行按照类型的编译期多态接口查找,它允许CPO显式的实现emplace(),同时解决了ADL无法将基础类型作为参数类型的问题。

此外,该设计模式还允许将特定参数类型映射到泛型接口。在本例中,对int和double的接口实现就通过泛型合并在了一起。

以ADL类型映射实现CPO优缺点分析

缺点:

  1. 无法覆盖已注册的ADL接口对象

优点:

  1. 显式的emplace方法
  2. 支持注册以基础类型作为参数的接口
  3. 支持泛型接口
  4. 由ADL实现的一般CPO的大部分优点(除参数泛型匹配)

此种编译期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>>的行为。

编译期ADL类型容器

在实现值为类型数组的类型哈希之前,我们需要先实现编译期计数器。这是由于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()接口。

类型映射栈实现CPO

实现原理如下:

alt

↑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类型迫使编译器重新实例化被调用的模板函数。

使用例:

alt

↑cover_t类型覆盖了std::string到string_t的多态类型映射

以类型映射栈实现CPO优缺点分析

缺点:

  1. (暂无)

优点:

  1. 可覆盖的多态类型映射
  2. 由ADL类型映射实现CPO的所有优点

由于前文所述实现缺陷已经被尽数修正,因此我们需要根据p2279中所罗列的要求额外提出当前实现的缺点。

额外的缺点:

  1. 无法提供默认实现
  2. 无法知悉是否已有实现被注册
  3. 无法提前诊断错误的实现
  4. 无法阻止当前实现被错误地覆盖

CPO meta API

针对上述4个尚存的缺陷,需要补齐一些元语义,并对其进行一些简单的封装:

尚需实现的额外实用功能

  1. 对_Key类型注册的实现类栈进行遍历的special/generic语义
  2. 对ill-formed进行sfinae封装以将其推导结果转换为特定类型的null_t语义
  3. 对实现类接口进行严格调用合法性检查的strict/relax语义
  4. 对实现类注册后提供禁止覆盖约定的final/override语义

CPO meta API实现

为方便充分阐述CPO meta API在CPO定义过程中的功能,例子将不再使用plus_one作为CPO demo。 本例将实现泛型的的for_each CPO,它的动名词语义是“遍历”。

实现原理如下:

alt

↑经过封装的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定义如下:

alt

↑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:

alt

↑for_each CPO由foo库提供,animal类由bar库提供,接下来user将在自己的程序上下文中向foo库注册bar库中animal类型的CPO meta信息

使用例:

alt

↑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实现。

CPO meta API优缺点分析

依靠ADL状态机,CPO meta API基本满足了p2279中提出的所有要求。

美中不足的是,我们手中的皮鞭[]{}违反了C++的设计哲学,这种技术在各编译器间可移植性较差。

同时C++需要一种强制刷新template argument deduction的机制,用来显式地避免编译器偷懒、抄近道或者背答案。


    出自:purecpp.cn

    地址: www.purecpp.cn

    转载请注明出处!


来说两句吧
登录才能发表评论。
最新评论
  • qicosmos
    qicosmos 2021-08-22 18:54:07

    很棒的文章!cpo根据参数类型实现多态是一个新思路。这里有没有可能对cpo做一个扩展,让它也可以根据参数个数实现多态?

    另外,文中很多元编程技巧值得学习,如果有源码链接也可以发出来供大家学习。

  • qicosmos
    madokakaroto 2021-08-22 19:04:04

    用stateful meta programming做cpo,并显式注册,可以克服ADL查找无法良好工作的情况,如(built-in types),很不错的思路。

    请教一下,在每一个编译单元应该都需要做注册对吧。 那如何保证注册的顺序在所有编译单元都一样呢?
    因为这种方案无法覆盖注册,所以会出现相同的key会有不同的注册结果。

  • qicosmos
    qicosmos 2021-08-23 10:59:19
    提一个建议,能否把cpo的合适的使用场景举一些例子,大家对于cpo了解得不多,如果有一些具体应用场景介绍就比较好理解了。
  • qicosmos
    fqbqrr 2021-08-24 08:26:00
    源码是图片,不爽.
Absolutely

purecpp

一个很酷的modern c++开源社区


[社区开源项目列表,点击前往]


purecpp社区自2015年创办以来,以“Newer is Better”为理念,相信新技术可以改变世界,一直致力于现代C++研究、应用和技术创新,期望通过现代C++的技术创新来提高企业生产力和效率。


社区坚持只发表原创技术文章,已经累计发表了一千多篇原创C++技术文章;


组织了十几场的C++沙龙和C++大会,有力地促进了国内外C++开发者之间的技术交流;


开源了十几个现代C++项目,被近百家公司所使用,有力地推动了现代C++在企业中的应用。


期待更多的C++爱好者能参与到社区C++社区的建设中来,一起为现代C++开源项目添砖加瓦,一起完善C++基础设施和生态圈。


微信公众号:purecpp, 社区邮箱: purecpp@163.com


友情链接