测试环境:

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

实现原理如下:

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

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

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

使用例:

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

该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

实现原理如下:

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

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

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

使用例:

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

以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

实现原理如下:

↑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类型映射实现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

实现原理如下:

↑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的多态类型映射

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

缺点:

0. (暂无)

优点:

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，它的动名词语义是“遍历”。

实现原理如下:

↑经过封装的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实现。

CPO meta API优缺点分析

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

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

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