《产生式元编程》第二章 自复用代码生成技

衔引

原理毕，复用续。历观编程概念，避及重复，提其不变，于迭代与递归为甚。产生式元编程，乃欲自动产生百千代码，迭代递归，自是重要组件，不可不备。

本章以 FOR_EACH 为例，渐次派生问题，引出技术要点，实现强大组件。

迭代

FOR_EACH 用来迭代数据集合，依次取出数据，后调用函数处理。参数易定，一个回调函数加上可变参数。代码表示：

#define FOR_EACH(call, ...)

// Invoke
FOR_EACH(Foo, 1, 2, 3)

实现需逐个取出可变宏参数，调用 Foo() 处理。上章已讲解重载之实现法，此乃条件逻辑在宏中的表示法。无循环时，递归思想便是拆解参数包的唯一方式，将重载实现法与递归思想结合起来，即可达逐个取参数之效。

遂可如此表示：

#define _FOR_EACH_1(call, x) call(x)
#define _FOR_EACH_2(call, x, ...) call(x) _FOR_EACH_1(call, __VA_ARGS__)
#define _FOR_EACH_3(call, x, ...) call(x) _FOR_EACH_2(call, __VA_ARGS__)
#define _FOR_EACH_4(call, x, ...) call(x) _FOR_EACH_3(call, __VA_ARGS__)
#define _FOR_EACH_5(call, x, ...) call(x) _FOR_EACH_4(call, __VA_ARGS__)

#define FOR_EACH(call, ...) \
    OVERLOAD_INVOKE(_FOR_EACH, COUNT_VARARGS(__VA_ARGS__))(call, __VA_ARGS__)

OVERLOAD_INVOKE() 在上章的基础上已部分优化，如今的实现变为：

#define CONCAT_HELPER(a, b) a ## b
#define CONCAT(a, b) CONCAT_HELPER(a, b)

#define OVERLOAD_INVOKE_1(call, v1) CONCAT(CONCAT(call, _), v1)
#define OVERLOAD_INVOKE_2(call, v1, v2) CONCAT( CONCAT(OVERLOAD_INVOKE_1(call, v1), _), v2 )
#define OVERLOAD_INVOKE_3(call, v1, v2, v3) CONCAT( CONCAT(OVERLOAD_INVOKE_2(call, v1, v2), _), v3)
#define OVERLOAD_INVOKE_4(call, v1, v2, v3, v4) CONCAT( CONCAT(OVERLOAD_INVOKE_3(call, v1, v2, v3), _), v4)
#define OVERLOAD_INVOKE_5(call, v1, v2, v3, v4, v5) CONCAT( CONCAT(OVERLOAD_INVOKE_4(call, v1, v2, v3, v4), _), v5)
#define OVERLOAD_INVOKE(call, ...) CONCAT( OVERLOAD_INVOKE_, COUNT_VARARGS(__VA_ARGS__) )(call, __VA_ARGS__)

因其使用太过广泛，太过频繁，于是提前重新封装成更适用的函数。它基于 COUNT_VARARGS() 实现，而在上章 COUNT_VARARGS() 又依赖于 OVERLOAD_INVOKE()，造成循环依赖。为解决此问题，将原本的重载调用功能，抽象为 CONCAT() 函数，如此一来，COUNT_VARARGS() 和 OVERLOAD_INVOKE() 都可以基于 CONCAT() 实现。

宏函数并非真的支持重载，而是进行分发调用，模拟重载。分发版本可能很多，为 OVERLOAD_INVOKE() 定义多个版本的实现，更易使用。

FOR_EACH() 就是以 OVERLOAD_INVOKE() 来调用不同的重载函数，不同的重载函数之间又利用递归思维，复用已有实现，以达到预想效果。

对于空包，在实现 COUNT_VARARGS() 时是个大问题，但此处并不会实际使用该参数，对结果没有任何影响，故不是问题。只需如此实现便可：

#define _FOR_EACH_0(call, ...)

更进一步，可以像第一章那样，以强制展开来让实现可以跨平台，此处省略。

使用例子：

void foo(int x) {
    printf("x: %d\n", x);
}

#define Foo(x) foo(x);
FOR_EACH(Foo, 0, 1, 2)

/**
 * Output:
 * x: 1
 * x: 2
 * x: 3
*/

这里也是为 foo() 的传递提供了一个中间件 Foo()。由于 FOR_EACH() 的实现中，call(x) 后面并没有添加 ;，直接传递 foo 难以增加该 ;，中间件能够延迟生成，为处理提供缓冲时间。传递之时名称为 Foo，而非 Foo(arg)，仅是一个普通名称，直到将 call(x) 替换为 Foo(x) 时，才真正开始生成代码，最终替换为 foo(x);。

当然也可以在实现中直接写成 call(x);，但会降低 FOR_EACH() 的通用性。

序列

调用 FOR_EACH(Foo, 0, 1, 2) 时，其中包含序列，相当于 C++ 中的 std::index_sequence<0, 1, 2>，数量较少时还可以手动写，数量一多便异常麻烦。C++ 通过 std::make_index_sequence<N> 来自动生成序列，简化了写法。

我们也来提供一个宏版本的 MAKE_INDEX_SEQUENCE(N), 自动生成序列。

同样利用重载加递归思想，很轻松地就能实现该需求。

#define MAKE_INDEX_SEQUENCE_0() 0
#define MAKE_INDEX_SEQUENCE_1() MAKE_INDEX_SEQUENCE_0(), 1
#define MAKE_INDEX_SEQUENCE_2() MAKE_INDEX_SEQUENCE_1(), 2
#define MAKE_INDEX_SEQUENCE_3() MAKE_INDEX_SEQUENCE_2(), 3
#define MAKE_INDEX_SEQUENCE_4() MAKE_INDEX_SEQUENCE_3(), 4
#define MAKE_INDEX_SEQUENCE_5() MAKE_INDEX_SEQUENCE_4()
#define MAKE_INDEX_SEQUENCE(index) OVERLOAD_INVOKE(MAKE_INDEX_SEQUENCE, DEC(index))()

举个例子，调用 MAKE_INDEX_SEQUENCE(5)，将生成 0, 1, 2, 3, 4。实现过程中，需要调用次一版本的重载，5 需要减少一，代码中另外声明了 DEC() 函数，用于实现数字自减。

DEC() 的实现原理也是重载，没有难度。

// DEC(Decrement by 1)
#define DEC_1() 0
#define DEC_2() 1
#define DEC_3() 2
#define DEC_4() 3
#define DEC_5() 4
#define DEC_6() 5
#define DEC_7() 6
#define DEC_8() 7
#define DEC_9() 8
#define DEC_10() 9
#define DEC(value) OVERLOAD_INVOKE(DEC, value)()

同理可以实现自增运算。

// INC(Increment by 1)
#define INC_0() 1
#define INC_1() 2
#define INC_2() 3
#define INC_3() 4
#define INC_4() 5
#define INC_5() 6
#define INC_6() 7
#define INC_7() 8
#define INC_8() 9
#define INC_9() 10
#define INC(value) OVERLOAD_INVOKE(INC, value)()

虽有 MAKE_INDEX_SEQUENCE(N) 生成序列，但却无法指定区间，只能生成 [0, N) 的序列。若想生成 [a, b) 的序列，如何实现呢？

判等

问题的关键在于结束条件的判断，满足结束条件立即停止生成，否则继续生成。

先写出区间函数原型，逐步实现。

#define RANGE(begin, end) OVERLOAD_INVOKE(RANGE, begin)(end)
#define RANGE_0(end) 0 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(0, DEC(end)))(1, end)
#define RANGE_1(end) 1 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(1, DEC(end)))(2, end)
#define RANGE_2(end) 2 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(2, DEC(end)))(3, end)

宏只有替换这一个功能，一切需求皆得回归原理思考。我们需要条件判断，而已有重载函数这把称手兵器，这并非问题。

两个地方需要用到条件。一是当前索引是否递归到末尾，如 [a = 0, b = 2) 中 a 从 RANGE_0() 开始生成，若是当前索引 a == DEC(b)，则返回 1，否返回 0。二是根据条件一返回的结果，分发处理，1 则停止生成，2 则继续生成下一个数字。

条件一通过 IS_EQUAL_INT(a, DEC(end)) 实现，初步代码为：

#define IS_EQUAL_INT_0_0() 1
#define IS_EQUAL_INT_1_1() 1
#define IS_EQUAL_INT_2_2() 1
#define IS_EQUAL_INT_3_3() 1
#define IS_EQUAL_INT_4_4() 1
#define IS_EQUAL_INT_5_5() 1
#define IS_EQUAL_INT_6_6() 1
// ...

#define IS_EQUAL_INT(a, b) OVERLOAD_INVOKE(IS_EQUAL_INT, a, b)()

对于相等的情况，通过重载非常好写，问题在于，如何表示不相等的情况？每个数字都要比较，穷举法自然无法穷尽，此时须得另辟蹊径。

根据第一章的结论 1.1，对于无法解决的问题，能够通过增加一个间接层来解决。是以考虑把结果再单独添加一个 IS_EQUAL_INT_RESULT() 表示，结果非 0 即 1。

如何产生非 0 即 1 的效果？在第一章中，以实现 COUNT_VARARGS() 展示了无数宏原理和技术，技术虽多，只取一瓢即够。方式就是当时所用的以 , 将空包变为多参的技巧，我们只需使得 IS_EQUAL_INT_X_X() 返回的参数个数不同，再借助 COUNT_VARARGS() 来分发结果便能达到目的。

怎么让返回的参数个数不等？, 便有此妙用。于是实现变为：

#define IS_EQUAL_INT_0_0() ,
#define IS_EQUAL_INT_1_1() ,
#define IS_EQUAL_INT_2_2() ,
#define IS_EQUAL_INT_3_3() ,
#define IS_EQUAL_INT_4_4() ,
#define IS_EQUAL_INT_5_5() ,
#define IS_EQUAL_INT_6_6() ,
// ...

#define IS_EQUAL_INT_RESULT_2() 1
#define IS_EQUAL_INT_RESULT_1() 0
#define IS_EQUAL_INT_RESULT(...) OVERLOAD_INVOKE(IS_EQUAL_INT_RESULT, COUNT_VARARGS(__VA_ARGS__))()
#define IS_EQUAL_INT(a, b) IS_EQUAL_INT_RESULT( OVERLOAD_INVOKE(IS_EQUAL_INT, a, b)() )

条件一目的达成。

死路

条件二通过 RANGE_GEN_WHEN_X() 实现，根据 IS_EQUAL_INT() 返回的结果调用不同的版本。

代码为：

#define RANGE_GEN_WHEN_1(cur, end)
#define RANGE_GEN_WHEN_0(cur, end) , OVERLOAD_INVOKE(RANGE, cur)(end)

#define RANGE(begin, end) OVERLOAD_INVOKE(RANGE, begin)(end)
#define RANGE_0(end) 0 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(0, DEC(end)))(1, end)
#define RANGE_1(end) 1 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(1, DEC(end)))(2, end)
#define RANGE_2(end) 2 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(2, DEC(end)))(3, end)
#define RANGE_3(end) 3 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(3, DEC(end)))(4, end)

当返回结果为 1 时，表示序列生成结束，什么也不必做；当结果为 0 时，表示需要接着生成序列，于是再次调用 RANGE_X 的新版本。循此往复。

测试一下：

0 , 1 RANGE_GEN_WHEN_0(2, 3)

想法很完美，现实很骨感。展开成了：

0 , 1 RANGE_GEN_WHEN_0(2, 3)

于是遂步分析一下，检查是否存在问题。

RANGE(0, 3) ->
1. OVERLOAD_INVOKE(RANGE, 0)(3)
2. RANGE_0(3)
3. 0 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(0, DEC(3)))(1, 3)
4. 0 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(0, 2))(1, 3)
5. 0 OVERLOAD_INVOKE(RANGE_GEN_WHEN, 0)(1, 3)
6. 0 RANGE_GEN_WHEN_0(1, 3)
7. 0 , OVERLOAD_INVOKE(RANGE, 1)(3)
8. 0 , RANGE_1(3)
9. 0 , 1 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(1, DEC(3)))(2, 3)
10. 0 , 1 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(1, 2))(2, 3)
11. 0 , 1 OVERLOAD_INVOKE(RANGE_GEN_WHEN, 0)(2, 3)
12. 0 , 1 RANGE_GEN_WHEN_0(2, 3)

如今停在第 12 步，换成 RANGE(0, 1)、RANGE(0, 2)、RANGE(1, 2)、RANGE(1, 3) 得到却的是正确的结果。也就是说，调用层次不能多于二层，二层之后若是调用 RANGE_GEN_WHEN_1()，能够得到正确的结果；若是调用 RANGE_GEN_WHEN_0() 便无法进一步展开。

这其实并非是思路的问题，而是宏自身的问题。宏并非是一套图灵完备的系统，它并不支持真正的递归。而二层以上，RANGE_GEN_WHEN_0() 又再次调用了自身，此时不会进一步展开。

这条路走死了。

递归

为了深入分析死路原因，我们将实现进一步简化，去除多个重载版本，直接基于 RANGE() 递归。

#define RANGE_GEN_WHEN_1(cur, end)
#define RANGE_GEN_WHEN_0(cur, end) , RANGE(cur, end)

#define RANGE(begin, end) begin OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(begin, end)) (INC(begin), end)

代码思路依旧未变，只不过前面一直采用多个函数重载来模拟递归，所以一直没有出现问题，这里直接使用递归。如果能将其实现，则前面的很多功能实现都可得到极大简化。

依旧调用 RANGE(0, 3)，展开结果为：

0 , RANGE(1, 3)

过程和之前相同，只是递归调用提前，替换也就提前停止。

RANGE(0, 3) ->
1. 0 OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(0, 3)) (INC(0), 3)
2. 0 OVERLOAD_INVOKE(RANGE_GEN_WHEN, 0) (1, 3)
3. 0 RANGE_GEN_WHEN_0 (1, 3)
4. 0 , RANGE(1, 3)

术语上来说，RANGE() 扫描展开后，便会创建一个禁用上下文（disabling context），禁用上下文会导致引用当前扩展宏的 token 被标记为 painted blue，任何方式都无法再展开。

不过禁用上下文只在一次扫描期间存在，因此可以避免引用当前扩展宏，将它延迟到下一轮扫描期间，便可以解决这个问题。延迟操作同样是通过增加间接性来实现。

#define EMPTY()
#define DEFER(id) id EMPTY()

#define RANGE_GEN_WHEN_1(cur, end)
#define RANGE_GEN_WHEN_0(cur, end) , DEFER(RANGE_INDIRECT)()(cur, end)

#define RANGE_INDIRECT() RANGE
#define RANGE(begin, end) begin OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(begin, end)) (INC(begin), end)

DEFER() 的作用就是延迟宏展开。例如：

#define Bar() 1
Bar() --> 1
DEFER(Bar)() --> Bar()

由于延迟展开，Bar 在当前没有彻底展开成 1。

于是，以 DEFER() 为工具，加用 RANGE_INDIRECT() 为 RANGE() 增加一层间接性，最后生成的结果为：

RANGE(0, 3) ->
0 , RANGE_INDIRECT ()(1, 3)

这里 RANGE 不会再被标记为 painted blue，由此可以开启新一轮的扫描，这个操作可以通过强制展开来完成。

#define EXPAND(...) __VA_ARGS__

EXPAND( RANGE(0, 3) ) ->
0 , 1 , RANGE_INDIRECT ()(2, 3)

EXPAND(EXPAND( RANGE(0, 3) )) ->
0 , 1 , 2 , RANGE_INDIRECT ()(3, 3)

EXPAND(EXPAND(EXPAND( RANGE(0, 3) ))) ->
0 , 1 , 2 , 3

每次手动调用新一轮的扫描较为麻烦，可以预先定义多轮扫描。

#define EXPAND(...)  EXPAND1(EXPAND1(EXPAND1(__VA_ARGS__)))
#define EXPAND1(...) EXPAND2(EXPAND2(EXPAND2(__VA_ARGS__)))
#define EXPAND2(...) EXPAND3(EXPAND3(EXPAND3(__VA_ARGS__)))
#define EXPAND3(...) EXPAND4(EXPAND4(EXPAND4(__VA_ARGS__)))
#define EXPAND4(...) EXPAND5(EXPAND5(EXPAND5(__VA_ARGS__)))
#define EXPAND5(...) __VA_ARGS__

于是调用可以得到预想结果。

EXPAND( RANGE(0, 3) ) ->
0 , 1 , 2 , 3

这便是宏递归的实现之法。

应用

可以再把 RANGE() 封装一下，简化使用接口。

#define RANGE_IMPL(begin, end) begin OVERLOAD_INVOKE(RANGE_GEN_WHEN, IS_EQUAL_INT(begin, end)) (INC(begin), end)
#define RANGE(begin, end) EXPAND( RANGE_IMPL(begin, end) )

#define RANGE_INDIRECT() RANGE_IMPL

配合 FOR_EACH() 使用，可以批量生成序列变量，比如：

#define DECLARE_VARIABLES(var) int variable_ ## var;
FOR_EACH(DECLARE_VARIABLES, RANGE(2, 5))

将自动生成如下代码：

int variable_2; int variable_3; int variable_4; int variable_5;

同样也可以批量生成类，如：

#define DECLARE_CLASS(cls) class cls{};
FOR_EACH(DECLARE_CLASS, Bar, Duck)

生成如下代码：

class Foo{}; class Bar{};

再比如，批量生成命名空间：

#define START_NS(ns) namespace ns {
#define END_NS(ns) }
#define MY_NAMESPACE System, Net, Http
FOR_EACH(START_NS, MY_NAMESPACE)
int X = 42;
FOR_EACH(END_NS, MY_NAMESPACE)

生成如下代码：

namespace System { namespace Net { namespace Http {
int X = 42;
} } }

借助这些工具，自动生成成百上千行代码，亦不在话下。

总结

本章以宏的核心原理进行扩展，开发 FOR_EACH 工具，迭代与递归技术穿插其中，再辅以很多小工具的实现手法，最终实现强大的代码生成组件。

灵活技巧，几近涵盖，巧妙手法，未有藏漏。还请大家多多支持本系列，在看、点赞、分享…… 后续章节更加精彩。