使用C++实现可编译期运行的内联状态机

状态机[1]是程序设计中常用的一种处理方法。以格式文本解析使用的状态机为例，一个最简单的，用于解析源代码中的字符串的状态机如下：

该状态机首先接收一个双引号，作为字符串的开始，然后持续接收字符，之后再遇到一个双引号时认为字符串结束。

代码中实现状态机的方法有很多种，比如C语言常使用状态转换表，它是一个二维表，类似这样：

Fsm fsm[] = {
    {ExpectStart, Quote, Ignore, ExpectChar},
    {ExpectChar, Character, Receive, ExpectChar},
    {ExpectChar, Quote, Ignore, EndState}
};

表中每行的四个元素分别表示：当前状态、事件（Event）、动作（Action）、下一个状态。每一次接收到新的事件时，处理代码查询这个转换表来决定要执行什么操作。动作（Action）在表中通常会用函数指针表示。

另一种常见的实现方法是用switch-case语句：

switch (currentState) {
    case EXPECT_START:
        if (c == '\"') {
            Ignore();
            currentState = EXPECT_CHAR;
        }
        break;
    case EXPECT_CHAR:
        if (c == '\"') {
            Ignore();
            currentState = END_STATE;
        } else {
            Receive(c);
        }
        break;
    case END_STATE:
        break;
}

此外，在面向对象语言中，还有一个经典设计模式——State模式[2]，专用于实现状态机。

以上这些实现方法主要专注于运行时功能的实现，它们会或多或少会产生一些额外运行开销，如：

1. 状态、事件查表的开销；函数指针调用的开销；
2. 状态保存为变量，变量值判断的开销；事件类型判断的开销；
3. 虚函数调用的开销。

本文尝试使用C++语言的模板元编程功能，实现一个完全消除所有运行开销的内联状态机。“内联”的意思指的是所有的状态判断都在编译期间完成，生成的运行时代码只包含动作（Action）本身的处理。同时，这种状态机还允许直接在编译期运行并得到结果（前提是状态机中的相关动作（Action）允许在编译期执行）。

本文中的所有代码基于C++17语言标准。

定义状态转换规则

定义Rule模板为一条规则，类似于二维转换表中的一行：

template<typename Src, typename Ev, typename Ac, typename Tar> struct Rule {
    using Source = Src;
    using Event = Ev;
    using Action = Ac;
    using Target = Tar;
};

定义编译期规则查找

给定若干条Rule后，可以使用变参模板递归的方法，查找指定的状态和事件所匹配的规则：

template<typename Src, typename Ev, typename Ru> struct Match {
    static constexpr bool value =
        is_same_v<Src, typename Ru::Source> && is_same_v<Ev, typename Ru::Event>;
};

template<typename Src, typename Ev, typename... Rules> struct Matcher {
    using Type = void;
};

template<typename Src, typename Ev, typename Ru, typename... Rules>
struct Matcher<Src, Ev, Ru, Rules...> {
    using Type = conditional_t<Match<Src, Ev, Ru>::value, Ru,
        typename Matcher<Src, Ev, Rules...>::Type>;
};

这里存在一种可能性：当前状态下收到的事件，对所有规则都匹配不上。这种情况通常被视为错误（比如上面字符串解析例子中，在ExpectStart状态下直接收到了Character）。这时候，查找出来的规则类型定义为void。

定义状态机类型和事件处理函数

通常来说，一个状态机对象需要记录当前所处的状态，记录方式一般用枚举值或者整型值。但是，一旦使用了运行时数据来记录状态，就不得不对该数据值进行判断，而这种判断通常会带来额外的运行时开销。

为了避免这种开销，本文实现的状态机不包含任何数据成员，是一个“无运行时状态的状态机”。这乍一看像是个悖论，但实际上可以通过模板元编程的方法实现：处理函数（Process）总是接收当前的状态作为入参，并返回下一个状态。在启动状态机时，传入起始状态作为入参，然后让编译器递归调用。

处理事件的动作（Action）可能会需要修改某些对象，因此处理函数在调用动作（Action）时，传递额外的入参（para）来传递可定制的对象。

struct EndState {};

template<typename... Rs>
class Fsm {
public:
    template<typename Src, typename Ev>
    using MatchedRule = typename Matcher<Src, Ev, Rs...>::Type;

    template<typename Src, typename Ev, typename... Para,
             typename Action = typename MatchedRule<Src, Ev>::Action,
             typename Target = typename MatchedRule<Src, Ev>::Target>
    static constexpr auto Process(Src srcState, Ev event, Para&&... para)
    {
        Action()(event, forward<Para>(para)...);
        return Target();
    }

    static constexpr EndState Process(...)
    {
        // 进行需要的错误处理……
        return EndState();
    }
};

注意在前面所说的无法找到对应规则的场景下，MatchedRule会成为void，这个时候Action和Target模板类型都无法获得，此时正好利用SFINAE[3]来让处理函数走到错误处理（下面的一个Process函数），并返回结束状态中止运行。

EndState是提前定义的结束状态，用于退出状态机。

字符串解析的处理示例

下面用开头所讲的字符串解析状态机作为一个例子，来看看如何使用上文定义的状态机。

在该例子中，Ignore动作忽略掉首尾的引号，Receive动作把字符串内容依次放到传入的容器中。最后把容器里的内容打印出来，观察状态机运行的结果。

// Event
struct Quote { char c; };
struct Character { char c; };

// Action
struct Ignore {
    template<typename... T> constexpr void operator()(T&&...) {}
};

struct Receive {
    template<typename Ev, typename Ctnr>
    constexpr void operator()(Ev event, Ctnr& container, size_t& pos)
    {
        container[pos++] = event.c;
    }
};

// State
struct ExpectStart {};
struct ExpectChar {};

using StringFsm = Fsm<Rule<ExpectStart, Quote, Ignore, ExpectChar>,
                      Rule<ExpectChar, Character, Receive, ExpectChar>,
                      Rule<ExpectChar, Quote, Ignore, EndState>>;

template<typename F, size_t I, typename... Para>
constexpr void StartFrom(EndState, Para&&... para) {}

template<typename F, size_t I, typename S, typename... Evs, typename... Para,
    typename = enable_if_t<!is_same_v<S, EndState>>>
constexpr void StartFrom(S s, tuple<Evs...> events, Para&&... para)
{
    auto nextState = F::Process(s, get<I>(events), forward<Para>(para)...);
    StartFrom<F, I + 1>(nextState, events, forward<Para>(para)...);
}

constexpr auto TestFsm()
{
    array<char, 10> output{};
    size_t pos = 0;
    StartFrom<StringFsm, 0>(ExpectStart(), make_tuple(
        Quote{'\"'}, Character{'r'}, Character{'e'}, Character{'d'}, Quote{'\"'}),
        output, pos);
    return output;
}

int main()
{
    constexpr auto output = TestFsm();
    printf(output.data());
    return 0;
}

启动状态机的函数是StartFrom，这里同样使用了SFINAE和函数重载，来让状态走到EndState时中止运行。

通常传给状态机的事件序列会使用数组、队列等方式来表达，但由于本文的状态机中各个事件是不同类型，无法放到一个数组或队列中，因此使用了std::tuple来表示。当然，这样做看起来带来了限制：事件序列必须在编译期已知。实际上，当事件未知时，可以通过对外部输入用条件分支生成不同类型事件来解决这个问题。

编译运行结果

读者可能已经注意到，上面示例中的输出结果是用constexpr定义的，这也就意味着所有计算都会在编译期完成。从实际生成的二进制也可以看出来，整个程序编完以后只有一个printf调用：

编译期状态机带来了一些有意思的想象应用：比如可以实现一个编译期编译器（多么绕口的名词），让用户的DSL代码在编译期就编译完成，提前发现错误并提升运行效率。

如果有些动作（Action）并不能在编译期执行会如何呢？只要把示例中Receive动作的处理改成别的（比如printf操作），并且去掉constexpr，就会看到编译出的结果只有需要执行的动作，所有的状态、事件判断全部被优化掉了：

可以说，这个状态机达到了真正的零开销，全内联，运行性能（几乎）最佳。

其他的状态机实现参考

虽然本文中的状态机有出色的运行时性能，但是毕竟模板递归调用的使用方式会有一些不便，更适合于文本解析这类可自动获取下一个事件的应用场景。如果希望在状态机执行时暂停下来去干别的，使用起来就不太容易了。

业界有一些其他的状态机实现，功能非常强大，在此也略作介绍：

Boost.Meta State Machine[4]：完整实现了UML所有状态机特性，包括Guard、Region等。该状态机库使用了大量模板编程技巧来提升性能，因此执行性能同样出色。但是由于实现内部使用了数组的方式来查询当前状态，以及用了函数指针来执行动作（Action），因此略有一些额外开销。

The Boost Statechart Library[5]：功能强大的状态机，接口简洁易用。内部使用了虚函数和条件判断，因此性能会差一些，适合于对性能要求不高，希望功能尽量齐全的场合。

Andrei Alexandrescu在2022年C++技术大会上展示的状态机[6]：这个状态机大量使用了C++20特性，因此接口和UML语言很接近，易用性很好。同时，实现内部用了Meta-Programming[7]库进行模板元编程，性能非常出色。但是由于状态机使用了整型数字来存储当前状态，一旦该数值判断无法被编译器优化掉，就会带来额外运行时开销。（当然，实际中这个开销小到几乎可以忽略不计）

尾注

[1] https://en.wikipedia.org/wiki/Finite-state_machine

[2] 见《Design Patterns - Elements of Reusable Object-Oriented Software》书中“State”一章

[3] https://en.cppreference.com/w/cpp/language/sfinae

[4] https://www.boost.org/doc/libs/1_80_0/libs/msm/doc/HTML/index.html

[5] https://www.boost.org/doc/libs/1_80_0/libs/statechart/doc/index.html

[6] https://godbolt.org/z/1TEoezq5c

[7] https://github.com/boost-ext/mp