今天讲消息分发的一种编译期实现法。

编程是一门非常依赖逻辑的学科，逻辑分为形式逻辑和非形式逻辑，编程就属于形式逻辑。形式逻辑指的是用数学的方式去抽象地分析命题，它有一套严谨的标准和公理系统，对错分明；而日常生活中使用的是非形式逻辑，它不存在标准和公理，也没有绝对的对与错。

根据哲学家大卫·休谟在《人性论》中对于观念之间连接的分类，我们能够把逻辑关系分成三大类：相似关系、因果关系、承接关系。相似关系表示两个组件结构相同，去掉其中一个组件，也只会使功能不够全面，并不会影响程序；因果关系表示两个组件之间依赖性极强，没有第一个组件，就没有第二个组件，第二个组件依赖于第一个组件；承接关系表示两个组件都是局部，只有组合起来，才能构成一个整体。

消息分发就属于因果关系，我们需要依赖 A，去执行 B，没有 A 就没有 B。同样属于因果关系的术语还有逻辑分派、模式匹配、定制点的表示方式等等，它们本质都是在描述一类东西，只是有时候侧重点不同。

条件关系也属于因果关系的范畴，是编程中逻辑最重的关系。试想没有 if else，你还能写出多少程序？世界是复杂的，问题也是复杂的，因果关系必不可少。

消息分发，或称为逻辑分派，就是一种简化条件关系表达方式的技术。它适用于存在大量因果的情境，此时若是使用原始的 if else，则无法适应动态发展的世界。

C++ 中，最典型、也非常有用的一种方式就是采用 map，因作为 key，果作为 value，因是标识符，果是回调函数。由于这种方式发生于运行期，所以也称为动态消息分发。

本文要讲的，是 C++20 才得以实现的另外一种方式，发生于编译期的静态消息分发技术。

称为消息分发，一般是在网络通信的情境下。正常情境下，程序是顺序执行的，所以完全可以使用 if else 来实现因果逻辑，因为组件与组件之间距离较近，属于同一模块；而网络情境下，一个组件可以瞬间跳跃到距离非常远的另一个组件，这两个组件甚至不在同一台设备上，一台设备可能在上海，另一台在北京，此时如何让这两个组件进行沟通？也就是说，A 组件里面的某个函数执行条件不满足，如何简单地跳到 B、C、D、E…… 这些组件的某个函数中去处理？这种远距离的程序因果逻辑，通过消息分发组件能够非常丝滑地表示。

消息分发的标识符一般采用字符串表示，到了 C++20 支持 string literal NTTP 才得以在编译期实现一套可用的相关组件。

因此首先，我们得实现一个 string literal 以在编译期使用。

template <std::size_t N>
struct string_literal {
    // str is a reference to an array N of constant char
    constexpr string_literal(char const (&str)[N]) {
        std::copy_n(str, N, value);
    }

    char value[N];
};

通过这种方式，我们定义了编译期能够使用的字符串组件，它能够直接当作模板参数使用。

然后，定义我们的分发器。

template <string_literal... Cs>
struct dispatcher {
    template <string_literal C>
    constexpr auto execute_if(char const* cause) const {
        if (C == cause) handler<C>();
    }

    constexpr auto execute(char const* cause) const {
        (execute_if<Cs>(cause), ...);
    }
};

代码非常精简，分发器可以包含很多「因」，使用可变模板参数 Cs 进行表示。如果得到一个具体的「因」，我们需要找到对应的「果」，因此免不了遍历 Cs，借助 Fold expressions，一行代码优雅地搞定。通过 execute_if 来查找是否存在对应的「因」，也就是对比字符串是否相等，查找到则调用相应的「果」，也就是具体的处理函数 handler<C>()。

接着，需要定义一个默认的因果，即如果没有定义相应的处理函数时，所调用的一个默认处理函数。

// default implementation
template <string_literal C>
inline constexpr auto handler = [] { std::cout << "default effect\n"; };

因为是模板参数，所以它能够处理所有的「因」。

通过特化，我们能够在任何地方，定义任何因果。比如：

// opt-in customization points
template<> inline constexpr auto handler<"cause 1"> = [] { std::cout << "customization points effect 1\n"; };
template<> inline constexpr auto handler<"cause 2"> = [] { std::cout << "customization points effect 2\n"; };

默认版本和定制版本之间是相似关系，即便不提供定制版本，也会不影响程序的功能。

由于特化更加特殊，所以决议时会首先考虑这些因果对。但是，此时有巨大的重复，我们通过宏来自动生成重复代码：

#define _(name) template<> inline constexpr auto handler<#name>

// opt-in customization points
_(cause 1) = [] { std::cout << "customization points effect 1\n"; };
_(cause 2) = [] { std::cout << "customization points effect 2\n"; };

现在定制起来就更加方便、简洁。

最后，具体使用。

int main() {
    constexpr string_literal cause_1{ "cause 1" };
    constexpr dispatcher<cause_1, "cause 2", "cause 3"> dispatch;
    dispatch.execute(cause_1);
    dispatch.execute("cause 2");
    dispatch.execute("cause 3");
}

相比动态消息分发，这种方式有两个巨大的优势，其一是编译期，其二是定制时可以在任何地方。动态消息分发一般需要调用 dispatch.add_handler(cause, effect)，因为是成员函数，所以限制了定制地方，必须得在对象所在模块，而静态消息分发这种全局定义特化的方式，则没有这种限制。

目前其实还存在两个问题，第一是 C == cause 并没有相应的比较操作符，第二是 dispatch.execute(cause_1) 并不能直接传递，因为 char const* 和 string_literal 毕竟不是同一种类型。可以通过添加运算符重载和隐式转换来解决：

template <std::size_t N>
struct string_literal {
    // ...

    friend bool operator==(string_literal const& s, char const* cause) {
        return std::strncmp(s.value, cause, N) == 0;
    }

    operator char const*() const {
        return value;
    }

    // ...
};

现在以上静态消息分发组件就能够正常使用了。完整的代码如下：

template <std::size_t N>
struct string_literal {
    constexpr string_literal(char const (&str)[N]) {
        std::copy_n(str, N, value);
    }

    friend bool operator==(string_literal const& s, char const* cause) {
        return std::strncmp(s.value, cause, N) == 0;
    }

    operator char const*() const {
        return value;
    }

    char value[N];
};

// default implementation
template <string_literal C>
inline constexpr auto handler = [] { std::cout << "default effect\n"; };

#define _(name) template<> inline constexpr auto handler<#name>

// opt-in customization points
_(cause 1) = [] { std::cout << "customization points effect 1\n"; };
_(cause 2) = [] { std::cout << "customization points effect 2\n"; };

template <string_literal... Cs>
struct dispatcher {
    template <string_literal C>
    constexpr auto execute_if(char const* cause) const {
        if (C == cause) handler<C>();
    }

    constexpr auto execute(char const* cause) const {
        (execute_if<Cs>(cause), ...);
    }
};

int main() {
    constexpr string_literal cause_1{ "cause 1" };
    constexpr dispatcher<cause_1, "cause 2", "cause 3"> dispatch;
    dispatch.execute(cause_1);   // customization points effect 1
    dispatch.execute("cause 2"); // customization points effect 2
    dispatch.execute("cause 3"); // default effect
}

短短数十行代码，便实现了一个威力强大的静态消息分发组件，This is modern C++。

Update on Aug 20, 2023

两点优化。

第一是 std::strncmp 并不是一个编译期函数，但 C++17 的 string_view 提供有编译期的字符串比较运算符重载。因此，改成这样实现更好：

friend constexpr bool operator==(string_literal const& s, char const* cause) {
    // return std::strncmp(s.value, cause, N) == 0;
    return std::string_view(s.value) == cause;
}

第二是当前每次执行时都会进行一次线性查找，时间复杂度为 O(n)。变成 O(1) 也有办法，但是传入的参数就必须也得是编译期数据，否则使用不了。

像是这样：

template <auto> struct compile_time_param {};
template <string_literal Data> inline auto compile_time_arg = compile_time_param<Data>{};

template <string_literal... Cs>
struct dispatcher {
    // ...

    template<string_literal s>
    constexpr auto execute(compile_time_param<s>) const {
        handler<s>();
    }

};

_(cause 4) = [] { std::cout << "customization points effect 4\n"; };
_(cause 5) = [] { std::cout << "customization points effect 5\n"; };

int main() {
    constexpr string_literal cause_1{ "cause 1" };
    constexpr dispatcher<cause_1, "cause 2", "cause 3"> dispatch;
    dispatch.execute(cause_1);
    dispatch.execute("cause 2");
    dispatch.execute("cause 3");

    const char cause_5[] = "cause 5";

    dispatch.execute(compile_time_arg<cause_1>);   // OK
    dispatch.execute(compile_time_arg<"cause 4">); // OK
    dispatch.execute(compile_time_arg<cause_5>);   // Error
}

这样虽然能够达到 O(1)，但灵活性很差。因为实际的数据往往是程序运行之后才产生的，根本就不可能是编译期，所以毫无用武之地。

但是提供这么一个重载，也算是多了一种选择，它既能支持运算期，又能支持编译期。

Update on Aug 25, 2023

前面分别提供了 O(n) 和 O(1) 两种接口，前者既可发生于编译期，也可发生于运行期，后者则强制发生于编译期。对于前者，使用 constexpr 修饰相关接口，以使这些接口既能够在编译期，也能够在运行期使用；对于后者，则可以将接口直接改为 consteval 修饰，这样保证性更强，接口也能更加一目了然。

另外一个优化点在于，fold expressions 纵然是匹配成功了，也还是会一直匹配下去。可以借助逻辑运算符 && 或 || 来打断 fold expressions，从而提高性能。

最终的优化代码如下(Compiler Explorer)：

template <std::size_t N>
struct string_literal {
    constexpr string_literal(char const (&str)[N]) {
        std::copy_n(str, N, value);
    }

    friend constexpr bool operator==(string_literal const& s, char const* cause) {
        return std::string_view(s.value) == cause;
    }

    constexpr operator char const*() const {
        return value;
    }

    char value[N];
};

// default implementation
template <string_literal C>
inline constexpr auto handler = [] { std::cout << "default effect\n"; };

#define _(name) template<> inline constexpr auto handler<#name>

// opt-in customization points
_(cause 1) = [] { std::cout << "customization points effect 1\n"; };
_(cause 2) = [] { std::cout << "customization points effect 2\n"; };

template <auto> struct compile_time_param {};
template <string_literal Data> inline auto compile_time_arg = compile_time_param<Data>{};

template <string_literal... Cs>
struct dispatcher {
    template <string_literal C>
    constexpr auto execute_if(char const* cause) const {
        return C == cause ? handler<C>(), true : false;
    }

    // compile-time and run time interface, O(n)
    constexpr auto execute(char const* cause) const {
        (!execute_if<Cs>(cause) && ...);
    }

    // compile-time interface, O(1)
    template<string_literal s>
    consteval auto execute(compile_time_param<s>) const {
        handler<s>();
    }
};

_(cause 4) = [] { /* compile time statements*/ };
_(cause 5) = [] { /* compile time statements*/ };

int main() {
    constexpr string_literal cause_1{ "cause 1" };
    constexpr dispatcher<cause_1, "cause 2", "cause 3"> dispatch;
    dispatch.execute(cause_1);   // customization points effect 1
    dispatch.execute("cause 2"); // customization points effect 2
    dispatch.execute("cause 3"); // default effect

    constexpr string_literal cause_4{ "cause 4" };
    const char cause_5[] = "cause 5";

    dispatch.execute(compile_time_arg<cause_4>);   // OK
    dispatch.execute(compile_time_arg<"cause 5">); // OK
    // dispatch.execute(compile_time_arg<cause_5>);   // Error
}

4 thoughts on “Compile time dispatching in C++20”

  2. 有一个想法，如果让 execute_if 返回 bool 表示是否已找到匹配的 handler，是否 fold expression 可以用 || 替换掉 , 运算符，减少不必要的判断的执行？

    constexpr void execute(const char* name) const noexcept
    {
        (execute_if(name) || ...);
    }
    template
constexpr bool execute_if(const char* name) const noexcept
{
    if (C == name) {
        execution();
        return true;
    }

    return false;
}
    Reply

  3. 在仅这样定义时
    constexpr dispatcher dispatch;

    这样的4和5
    (cause 4) = [] { std::cout << "customization points effect 4\n"; };
    (cause 5) = [] { std::cout << "customization points effect 5\n"; };

    就无法通过编译了，如果一定要似乎意义不大。

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You can use the Markdown in the comment form.