purecpp - a cool open source modern c++ community

C++: 通过对编译时ADL状态机进行封装为CPO提供易用的meta API库

编辑时间：2022-02-10 03:06:19 作者：loop 4条评论

出自：purecpp.cn

地址： www.purecpp.cn

转载请注明出处！

**测试环境:**

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*

[示例代码](http://purecpp.cn/detail?id=2252)

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

## CPO的定义

根据[Arthur O’Dwyer的文章](https://quuxplusone.github.io/blog/2018/03/19/customization-points-for-functions/)所述，CPO当且仅当程序在出现“动词名词化”的需求时才被需要。

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

CPO的这个行为与虚函数非常相似，正如[p2279](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2279r0.html)所述。
与虚函数不同的是，虚函数根据this类型产生不同的行为，CPO根据参数不同产生不同行为。

据此可以推知:

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

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

### RTTI方式实现CPO
**实现原理如下:**

![alt](http://purecpp.cn/static/5d60025d35584418bd47bc245013b671.png)

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

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

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

使用例:

![alt](http://purecpp.cn/static/9e3d77fde46c468487825839c7748567.png)

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

该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](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1895r0.pdf)中阐述的tag\_invoke设计模式使用首个参数类型作为ADL引导，以区分各种不同的CPO对象，本例采用这种设计模式。

### ADL/tag\_invoke方式实现CPO
**实现原理如下:**

![alt](http://purecpp.cn/static/eacf573548114bf0a6276af440912d55.png)

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

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

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

使用例:

![alt](http://purecpp.cn/static/ae3fda939a3e4156ad8c7afc42acfdab.png)

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

### 以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](http://purecpp.cn/static/10e91a4e3d9a4707ada5b72f638c2f5e.png)

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

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

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

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

使用例:

![alt](http://purecpp.cn/static/9c5a8c7097a54d98a273655ec214bb36.png)

↑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](http://purecpp.cn/static/7679eae2e33844db9628df413330fbae.png)

↑emplace方法中简单调用push()方法将新注册的实现类泛型接口压入对应的类型栈

在CPO调用时，通过top()方法取出相应的类型value，通过decltype(value)推导出其类型，之后调用即可。

每个\_Key类型映射的多个\_Value的栈高由ADL函数tag\_size()推导，由于编译器只对该函数进行一次实例化，所以需要\_Refresh模板参数刷新其实例化类型。

在tag\_size()推导过程中的sfinae参数中传递的if\_t和else\_t是[priority\_tag](https://quuxplusone.github.io/blog/2021/07/09/priority-tag/)在只有二值的情况下的简化形式。

在向tag\_size()传递\_Refresh参数前使用空模板类refresh<\>包装，是为了避免当\_Key与\_Value类型相同时刷新tag\_size()失败，这种潜在失败可能由编译器缓存了模板实例化结果导致。

更加一般的方法是将栈的读写方法定义为push(\_Lambda)和top(\_Lambda)，在调用时使用push<\_Key, \_Value\>([]{})或top<\_Key\>([]{})，之后将模板参数推导出的\_Lambda类型传递给tag\_size，保证总有新的lambda类型迫使编译器重新实例化被调用的模板函数。

使用例:

![alt](http://purecpp.cn/static/a8a196fad6764141a2a13276e13e3738.png)

↑cover\_t类型覆盖了std::string到string\_t的多态类型映射

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

0. (暂无)

优点:

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

由于前文所述实现缺陷已经被尽数修正，因此我们需要根据[p2279](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2279r0.html)中所罗列的要求额外提出当前实现的缺点。

额外的缺点:

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](http://purecpp.cn/static/74b9ff7893d94cf4b0875090f2223a9d.png)

↑经过封装的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](http://purecpp.cn/static/d8cd9a02cf4c4fbb90604eae69a2ce67.png)

↑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](http://purecpp.cn/static/6f2fd9a10f804de19633b85c8170d436.png)

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

使用例:

![alt](http://purecpp.cn/static/7f3c25fc11a444dbbb231f558aa8e4d8.png)

↑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](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2279r0.html)中提出的所有要求。

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

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

来说两句吧