第11章：Multimethods

为什么需要先问 What Are Multimethods?

What Are Multimethods? 普通 virtual method 只按一个 receiver 的 dynamic type 选择；multimethod 根据两个或更多 arguments 的 dynamic types 共同选择 operation。CLOS 等语言原生支持，C++ 需要 Visitor、RTTI registry 或 generated table 模拟。

collision 是典型例子：collide(GameObject&, GameObject&) 对 Ship/Asteroid、Ship/Station、Asteroid/Asteroid 的行为不同。把方法放进 lhs class 仍只 dispatch lhs，rhs 要再判断；把方法放进 operation object 也面临同样问题。

When Are Multimethods Needed?

When Are Multimethods Needed? 要同时满足：参与对象来自开放/多态 hierarchy；operation 真正依赖多个 dynamic types；把逻辑放进任一 class 都造成 cross-type coupling；组合数量足以让 hand-written conditionals 漂移。

如果一边类型集合很小且稳定，Visitor double dispatch 更简单；若数据本来是 closed variant, std::visit 可在 compile time 穷举组合；若行为主要由值/状态而非 type 决定，规则引擎或 ordinary branching 更合适。

Double Switch-on-Type：Brute Force

Double Switch-on-Type: Brute Force 对第一个 object 逐类 dynamic_cast，命中后再对第二个逐类 cast。N 种 types 最坏有 N² pairs，central function 知道所有 concrete classes。

void collide(GameObject& lhs, GameObject& rhs) {
    if (auto* ship = dynamic_cast<Ship*>(&lhs)) {
        if (auto* asteroid = dynamic_cast<Asteroid*>(&rhs)) {
            return collideShipAsteroid(*ship, *asteroid);
        }
        if (auto* station = dynamic_cast<Station*>(&rhs)) {
            return dockOrReject(*ship, *station);
        }
    }
    if (auto* asteroid = dynamic_cast<Asteroid*>(&lhs)) {
        if (auto* other = dynamic_cast<Asteroid*>(&rhs)) {
            return collideAsteroids(*asteroid, *other);
        }
    }
    throw UnknownCollision{};
}

优点是可读、无需 registry，compiler 能看见所有 branches；缺点是 extension 修改 central code、pair symmetry 重复、test coverage 与顺序容易漏。对少量 types 它可能正是 pragmatic baseline。

The Brute-Force Approach Automated

The Brute-Force Approach Automated 用 Typelist 与 template recursion 生成嵌套 type tests。算法按 list1 尝试 lhs，再按 list2 尝试 rhs，命中后调用 typed executor；列表末端走 error policy。

自动化保证 list 中每种 type 都进入结构，却不保证每个 pair 有合理语义。default executor、compile-time coverage matrix 或 explicit unsupported set 仍需定义。模板展开还会增加 code size 和 compile diagnostics。

Symmetry with the Brute-Force Dispatcher

Symmetry with the Brute-Force Dispatcher 处理 f(A,B) == f(B,A) 的 operation。dispatcher 可把 type pair canonicalize，例如按 type index 排序；若交换 inputs，还要在调用 typed handler 时恢复它期望的 argument roles。

不是所有碰撞都对称：Ship docking Station 与 Station docking Ship 可能角色不同；damage source/target 更明显。symmetry 是 operation property，不是 type pair property。同一个 pair 对 overlap test 可对称，对 apply-damage 可不对称。

The Logarithmic Double Dispatcher

The Logarithmic Double Dispatcher 用 ordered map，将 (type_info(lhs), type_info(rhs)) 映射到 callback。lookup O(log M)，M 是已注册 pairs；新增 concrete type/operation 通过 registration，不改 central chain。

using Key = std::pair<std::type_index, std::type_index>;
using Callback = std::function<void(GameObject&, GameObject&)>;
 
class Dispatcher {
public:
    template<class L, class R, class F>
    void add(F function) {
        table_[{typeid(L), typeid(R)}] =
            [fn = std::move(function)](GameObject& l, GameObject& r) {
                fn(dynamic_cast<L&>(l), dynamic_cast<R&>(r));
            };
    }
private:
    std::map<Key, Callback> table_;
};

registry lookup 命中后 adapter 仍做 checked cast，验证 key/object agreement。若 callback code 来自 plugin，registration entry、in-flight call 与 objects 都要持 module lease；问题与第 8 章 Factory 相同。

FnDispatcher and Symmetry

FnDispatcher and Symmetry 将 pair normalization 封装在 registration/lookup：对 symmetric operation，只注册 canonical key；调用顺序反转时，adapter 交换 objects 后再传 typed function。unknown pair 由 error function、default callback 或 no-op 处理。

canonical ordering 不能依赖 type_info::name()；同进程可用 std::type_index strict order 或内部 type IDs。若 IDs 来自 registration 顺序，多线程/plugin load order 会影响数值但不应影响语义。

Double Dispatch to Functors

Double Dispatch to Functors 用第 5 章 generalized Functor 取代裸函数指针：handler 可捕获 state、调用 member function、组合 logging/metrics。统一 erased signature 常为 Base&,Base&; registration adapter 保留 typed L&,R& target。

Functor 带来 heap/indirect call/copy semantics；dispatcher table 本身也有 allocation。operation 很重时可忽略，physics narrow phase 每秒百万次则应测 direct matrix、function pointer 与 inlined closed variant。

Converting Arguments：static_cast or dynamic_cast?

Converting Arguments: static_cast or dynamic_cast? 取决于 registry invariant 是否足以证明 object dynamic types 与 key 相同。dynamic_cast<L&> 检查并在 mismatch 抛 bad_cast; static_cast<L&> 在证明错误时产生 undefined behavior。

template<class L, class R, class F>
auto checkedAdapter(F fn) {
    return [fn = std::move(fn)](Base& left, Base& right) {
        auto* l = dynamic_cast<L*>(&left);
        auto* r = dynamic_cast<R*>(&right);
        if (!l || !r) throw DispatcherInvariantViolation{};
        return fn(*l, *r);
    };
}

可先在 debug/validation build 用 dynamic_cast，在 production 若 measurement 证明 cast 显著且 key 由 typeid(objects) 当场生成，可在封闭 adapter 内 static_cast；不要让 unsafe cast 扩散到 handlers。多重/虚继承还需要 pointer adjustment，static_cast from correct Base can perform it，但前提依旧是 dynamic type 确定。

Constant-Time Multimethods：Raw Speed

Constant-Time Multimethods: Raw Speed 为每个 concrete type 分配 dense integer ID，用二维 table handlers[idL][idR] 直接索引；或 unordered map pair 期望 O(1)。dense matrix 速度稳定，但 memory O(N²)，sparse operations 浪费大量 slots。

type ID 分配、table resize、plugin unload 和 concurrent registration 成为新成本。IDs 若复用，live objects 的旧 ID 会误命中新 type；需要 generation/version 或 process-lifetime non-reused IDs。matrix publish 可用 immutable snapshot 避免 lookup lock。

BasicDispatcher and BasicFastDispatcher as Policies

BasicDispatcher and BasicFastDispatcher as Policies 把 lookup engine 作为 Policy：前者可用 map/logarithmic storage，后者用 hash/dense table；外层 Multimethod 保持 register/go/error/symmetry API。其他 Policies 可定义 cast、callback、unknown 与 threading。

Policy compatibility 要求 key/callback/registration semantics 一致。Fast policy 若不支持 unregister 或 stable iterator，Host 不能假定这些能力；可用 concepts 表达 optional operations。切换 storage policy 不应改变 symmetric/default handler 等业务语义。

Looking Forward

Looking Forward 到现代 C++，closed type sets 可用 std::variant + std::visit 生成 compile-time Cartesian dispatch；open sets 可用 type_index registry；性能敏感 ECS 常用 explicit type IDs/tables；future language pattern matching 进一步改善 closed sum types。

先预测：8 types 的 dense matrix 只有 64 slots，constant-time 简单；500 plugin types 有 250,000 pairs，实际只注册 800 个，map/hash 更省内存。先量 N、M、dispatch frequency、operation cost 和 mutation frequency，再选 engine。

小结

• multimethod 根据多个动态参数类型 tuple 选择操作，适用于 cross-type behavior 无自然单一 owner 的场景
• brute-force double switch 是清楚 baseline，Typelist 可自动生成但仍有 O(N²) 测试/代码结构
• symmetry 属于 operation；canonical pair 必须在反转输入时保持 typed argument roles
• logarithmic dispatcher 用 type pair map，FnDispatcher/Functor 支持开放注册与 stateful callbacks
• argument conversion 应默认 checked，只有 key/object invariant 封闭可证明且测得收益时才考虑 static_cast
• constant-time matrix 用速度换 O(N²) memory 与 type-ID lifecycle；sparse open sets 更适合 map/hash
• BasicDispatcher/BasicFastDispatcher 将 lookup storage Policy 化，外层语义应保持一致
• closed sets 可用 variant visit，open plugin sets 可用 registry，ECS/热路径可用 dense IDs；先按 N、M、频率与扩展选择

名词解释