Daniel's Blog

我最喜欢的 C++ 模式: X Macros

C++ Chapel Compilers 发布于 2023 年 10 月 14 日。

目录

• 应用 1: String Interning
• 应用 2: AST 类层级
  • Tags and Dynamic Casting
  • The Visitor Pattern without Double Dispatch
  • Generating a Python Class Hierarchy
• 应用 3: CPython 方法表和 Getters
• 讨论

当我刚加入 Chapel 团队时，其基于 C++ 的编译器中使用的一种模式给我留下了深刻的印象。 从那以后，我多次使用这种模式，并且对结果非常满意。 然而，感觉这种模式相对不为人所知，所以我想展示一下它，以及它在 Chapel compiler 中的一些应用。 为了简化演示，我对本文中直接展示的许多代码片段进行了稍微调整；如果您想查看完整版本，我包含了指向原始代码（可在 GitHub 上获得）的链接。

广义上讲，“X Macros”模式是关于生成代码的。 如果您需要编写_大量_重复代码（声明许多变量或类，执行许多非常相似的操作等），此模式可以节省大量时间，生成更易于维护的代码，并减少添加_更多_代码所需的工作量。

我将以最简单的形式介绍该模式，并以我的第一个例子：interning strings。

应用 1: String Interning

Chapel 编译器会 intern 大量的字符串。 这样，它可以减少将标识符保存在内存中的内存占用（每个字符串 "x" 实际上是_同一个_字符串），并使相等比较更快（您可以只执行指针比较！）。 通常，使用 Context 类来管理 interning 状态。 可以使用上下文对象以以下方式构造新的 interned string：

UniqueString::get(ctxPtr, "the string");

实际上，这会搜索当前存在的 unique strings。 如果不存在具有该内容（在本例中为 "the string"）的字符串，则会创建该字符串并在 Context 中注册。 否则，将返回现有字符串。 然而，有些字符串在编译器中出现了很多次，以至于每次都执行整个“查找或创建”操作效率很低。 其中一个例子是 "this" 字符串，它是一种标识符，在该语言中具有许多特殊行为（很像 Java 等语言中的 this）。 为了支持这种经常使用的字符串，编译器会初始化它们一次，并为每个字符串创建一个变量，可以访问该变量以获取该字符串的值。

这就是重复代码。 为每个字符串定义一个全新的变量，在编写本文时大约有 100 个字符串，这需要编写大量的样板代码。 此外，至少有两个地方需要添加代码：一次在变量的声明中，一次在初始化变量的代码中。 [note: 在编译器中的第三个用途实际上是一个在字符数组上定义的 variadic template。 该 template 的定义和专用化方式允许您通过其字符串内容引用变量（即，您可以编写 USTR("the string") 而不是 theStringVariable）。 ] 很容易意外地修改前者而不是后者，特别是对于不熟悉这些“常用字符串”如何实现的开发人员而言。

这就是 X Macros 的用武之地。 如果您查看编译器源代码，会发现一个头文件，其内容如下：

来自 all-global-strings.h，第 31 行左右

X(align     , "align")
X(atomic     , "atomic")
X(bool_     , "bool")
X(borrow     , "borrow")
X(borrowed    , "borrowed")
X(by       , "by")
X(bytes     , "bytes")
// 还有很多...

这个 X 是什么？ 就在那里，它是该模式的本质：宏 X 未在头文件中定义！ 实际上，all-global-strings.h 只是一个列表，我们可以“迭代”该列表，为它的每个元素生成一些代码，在任意多个位置。 我的意思是，我们可以编写如下代码：

来自 global-strings.h，第 76 行左右

  struct GlobalStrings {
#define X(field, str) UniqueString field;
#include "all-global-strings.h"#undef X
  };

在这种情况下，我们定义宏 X 来忽略字符串的值（我们只是在这里声明它），并创建一个新的 UniqueString 变量声明。 由于该声明位于 GlobalStrings 结构体内部，因此最终会创建一个字段。 就像这样，我们声明了一个包含 100 多个字段的类。 初始化同样简单：

来自 Context.cpp，第 49 行左右

  GlobalStrings globalStrings;
  Context rootContext;
  static void initGlobalStrings() {
#define X(field, str) globalStrings.field = UniqueString::get(&rootContext, str);
#include "chpl/framework/all-global-strings.h"#undef X
  }

有了这个，我们就完全自动化了声明和初始化所有 100 个 unique strings 的代码。 添加新字符串不需要开发人员知道实现此操作的所有位置：只需使用对 X 的新调用修改 all-global-strings.h 头文件，他们就可以添加一个新变量和用于初始化它的代码。 非常健壮！

应用 2: AST 类层级

虽然 interned strings 是一个极好的第一个例子，但它并不是我在 Chapel 编译器中遇到的 X Macros 的第一个用法。 除了字符串之外，编译器还使用 X Macros 来表示它使用的 abstract syntax tree (AST) 节点的整个类层级。 在这里，代码实际上更复杂一些；类层级不像字符串那样是_列表_；它本身就是一个树。 为了表示这样的结构，我们需要不止一个 X 宏；编译器选择了 AST_NODE、AST_BEGIN_SUBCLASSES 和 AST_END_SUBCLASSES。 如下所示：

来自 uast-classes-list.h，第 96 行左右

 // 上面还有其他 AST 节点...
 AST_BEGIN_SUBCLASSES(Loop)
   AST_NODE(DoWhile)
   AST_NODE(While)
  AST_BEGIN_SUBCLASSES(IndexableLoop)
   AST_NODE(BracketLoop)
   AST_NODE(Coforall)
   AST_NODE(For)
   AST_NODE(Forall)
   AST_NODE(Foreach)
  AST_END_SUBCLASSES(IndexableLoop)
 AST_END_SUBCLASSES(Loop)
 // 下面还有其他 AST 节点...

在此头文件（称为 uast-classes-list.h）中定义的类层级用于很多事情，无论是在编译器本身中还是在使用编译器的某些库中。 我将依次介绍用例。

Tags and Dynamic Casting

首先，为了处理 RTTI 的普遍缺失，层级头文件用于声明“tag”枚举。 每个 AST 节点都有一个与其类匹配的 tag；这允许我们检查 AST 并执行类似于 dynamic_cast 的安全强制转换。 请注意，对于父类（通过 BEGIN_SUBCLASSES 定义），我们实际上最终会创建_两个_ tag：一个 START_... 和一个 END_...。 这样做的原因稍后会清楚。

来自 AstTag.h，第 36 行左右

enum AstTag {
#define AST_NODE(NAME) NAME ,
#define AST_BEGIN_SUBCLASSES(NAME) START_##NAME ,
#define AST_END_SUBCLASSES(NAME) END_##NAME ,
#include "chpl/uast/uast-classes-list.h"#undef AST_NODE
#undef AST_BEGIN_SUBCLASSES
#undef AST_END_SUBCLASSES
 NUM_AST_TAGS,
 AST_TAG_UNKNOWN
};

上面的代码段使 AstTag 包含诸如 DoWhile、While、START_Loop 和 END_Loop 之类的元素。 为方便起见，我们还添加了其他几个元素：NUM_AST_TAGS，它会自动分配给我们生成的 tag 的数量，[note: 这是因为 C++ 依次将整数值分配给枚举元素，从零开始。 ] 以及一个通用的“未知 tag”值。

通过这种方式生成枚举元素后，我们可以编写查询函数。 这样，API 使用者可以编写 isLoop(tag) 而不是手动执行比较。 此处的代码生成实际上分为两种不同的“is bla”方法形式：用于具体 AST 节点（DoWhile、While）的方法和用于抽象基类（Loop）的方法。 这样做的原因很简单：只有 AstTag::DoWhile 表示 do-while 循环，但 DoWhile 和 While 都是 Loop 的实例。 因此，isLoop 应该对两者都返回 true。

这就是 START_... 和 END_... 枚举元素发挥作用的地方。 从上到下读取头文件，我们首先生成 START_Loop，然后生成 DoWhile 和 While，然后生成 END_Loop。 由于 C++ 依次将整数值分配给枚举，因此要检查 tag 是否“扩展”了基类，只需检查其值是否大于 START 标记，且小于 END 标记 – 这意味着它是在匹配的 BEGIN_SUBCLASSES 和 END_SUBCLASES 对中声明的。

来自 AstTag.h，第 59 行左右

// 为叶节点和常规节点定义 is___
// （尚未为抽象父类定义）
#define AST_NODE(NAME) \
 static inline bool is##NAME(AstTag tag) { \
  return tag == NAME; \
 }
#define AST_BEGIN_SUBCLASSES(NAME)
#define AST_END_SUBCLASSES(NAME)
// 将上面的宏应用于 uast-classes-list.h
#include "chpl/uast/uast-classes-list.h"// 清除宏
#undef AST_NODE
#undef AST_BEGIN_SUBCLASSES
#undef AST_END_SUBCLASSES
// 为抽象父类定义 is___
#define AST_NODE(NAME)
#define AST_BEGIN_SUBCLASSES(NAME) \
 static inline bool is##NAME(AstTag tag) { \
  return START_##NAME < tag && tag < END_##NAME; \
 }
#define AST_END_SUBCLASSES(NAME)
// 将上面的宏应用于 uast-classes-list.h
#include "chpl/uast/uast-classes-list.h"// 清除宏
#undef AST_NODE
#undef AST_BEGIN_SUBCLASSES
#undef AST_END_SUBCLASSES

这些帮助程序非常方便。 以下是我们最终得到的一些示例：

isFor(AstTag::For)       // 返回 true；'for' 循环确实是 'for' 循环。
isIndexableLoop(AstTag::For)  // 返回 true；'for' 循环是“可索引的”（'for i in ...'）
isLoop(AstTag::For)      // 返回 true；'for' 循环是一个循环。
isFor(AstTag::While)      // 返回 false；'while' 循环不是 'for' 循环。
isIndexableLoop(AstTag::While) // 返回 false；'while' 循环使用布尔条件，而不是索引
isLoop(AstTag::While)     // 返回 true；'while' 循环是一个循环。

在顶级 AST 节点类上，我们为每个 AST 子类生成 isWhateverNode 和 toWhateverNode。 因此，用户代码能够使用普通方法检查 AST 并执行（已检查的）强制转换。 为了简洁起见，我省略了此处的 isWhateverNode（其定义非常简单），并且仅包含 toWhateverNode。

来自 AstNode.h，第 313 行左右

 #define AST_TO(NAME) \
  const NAME * to##NAME() const { \
   return this->is##NAME() ? (const NAME *)this : nullptr; \
  } \
  NAME * to##NAME() { \
   return this->is##NAME() ? (NAME *)this : nullptr; \
  }
 #define AST_NODE(NAME) AST_TO(NAME)
 #define AST_LEAF(NAME) AST_TO(NAME)
 #define AST_BEGIN_SUBCLASSES(NAME) AST_TO(NAME)
 #define AST_END_SUBCLASSES(NAME)
 // 将上面的宏应用于 uast-classes-list.h
 #include "chpl/uast/uast-classes-list.h" // 清除宏
 #undef AST_NODE
 #undef AST_LEAF
 #undef AST_BEGIN_SUBCLASSES
 #undef AST_END_SUBCLASSES
 #undef AST_TO

这些方法在编译器中被大量使用。 例如，这是我完全随机提取的一段代码：

来自 Resolver.cpp，第 1161 行左右

 if (auto var = decl->toVarLikeDecl()) {
  // 根据以下内容确定变量类型：
  // * 变量声明中的类型
  // * 变量声明中的初始化表达式
  // * 来自 split-init 的初始化表达式
  auto typeExpr = var->typeExpression();
  auto initExpr = var->initExpression();
  if (auto var = decl->toVariable())
   if (var->isField())
    isField = true;

因此，添加新 AST 节点的开发人员无需手动实现 isWhatever、toWhatever 和其他函数。 此功能和相当多的其他 AST 功能（我将在下一小节中介绍）是使用 X Macros 自动生成的。

您实际上并没有展示如何声明 AST 节点类，而只展示了 tag。 似乎不太可能使用相同的策略生成它们 – 每个 AST 节点不是都有自己不同的方法和实现代码吗？ 您是对的。 AST 节点类是“照常”定义的，它们的构造函数必须显式地将其 tag 字段设置为相应的 AstTag 值。 定义新类的开发人员还必须扩展他们承诺在 uast-classes-list.h 中扩展的节点。 这似乎是出现 bug 的机会。 没有什么可以阻止开发人员返回错误的 tag，这会破坏自动强制转换行为。 是的，它不是万无一失的。 不久前，一个团队成员发现 一个 bug，其中一个节点被列为继承自 AstNode，但实际上继承自 NamedDecl。 即使它继承自该类，toNamedDecl 方法也不会在该节点上起作用。 尽管如此，此模式为 Chapel 编译器提供了很多价值； 我将在下一小节中展示更多用例，就像承诺的那样。

The Visitor Pattern without Double Dispatch

访问者模式通常非常重要，但对于我们编译器开发人员来说，它无处不在。 它有助于避免在 AST 节点类中膨胀执行各种操作所需的的方法和状态。 它通常还可以使我们免于编写 AST 遍历代码。

从本质上讲，与其将每个新操作（例如，转换为字符串、计算类型、分配 ID）作为每个 AST 节点类上的方法添加，不如我们将此代码提取到每个操作的_访问者_中。 此访问者是一个类，它具有在 AST 节点上实现自定义行为的方法。 visit(WhileLoop*) 方法可以用于对“while”循环执行操作，而 visit(ForLoop*) 可以对“for”循环执行相同的操作。 AST 节点本身只有 traverse 方法，该方法接受访问者（无论它是什么）并调用相应的 visit 方法。 这样，AST 节点实现保持简单且相对稳定。

作为一个非常简单的例子，假设您想计算程序中使用的循环数量（出于未指明的原因）。 您可以添加一个 countLoops 方法，但是您已经为 AST 节点 API 引入了一个方法，用于可能是一次性的、可丢弃的操作。 使用访问者模式，您不需要这样做； 您只需创建一个新类：

struct MyVisitor {
  int count = 0;
  void visit(const Loop*) { count += 1; }
  void visit(const AstNode*) { /* 对其他节点不执行任何操作 */ }
}
int countLoops(const AstNode* root) {
  MyVisitor visitor;
  root->traverse(visitor);
  return visitor.count;
}

traverse 方法是一个很好的 API，不是吗？ 在不修改语法树的情况下，可以很容易地添加对语法树进行操作的操作。 但是，仍然有一个重要的开放问题：traverse 如何知道调用正确的 visit 函数？

如果 traverse 仅在 AstNode* 上定义，并且它只是调用 visit(this)，那么我们始终最终调用 visit 函数的 AstNode 版本。 这是因为 C++ 不会根据方法参数的类型进行动态分派。 [note: 显然，C++ 能够根据_接收者_的运行时类型选择正确的方法：这只是 virtual 函数和 vtable。 ] 从静态的角度来看，调用显然接受 AstNode，没有更具体的类型。 因此，编译器选择该版本的 visit 方法。

在像 C++ 或 Java 这样的语言中解决此问题的“传统”方法称为_双重分派_。 使用我们的示例作为参考，这涉及使_每个_ AST 节点类都有自己的 traverse 方法。 这样，对 visit(this) 的调用具有更具体的类型信息，并且会被解析为适当的重载。 但这需要更多的样板代码：每个新的 AST 节点都需要有一个 virtual traverse 方法，该方法如下所示：

void MyNode::traverse(Visitor& v) {
 v.visit(this);
}

它还需要所有访问者都从 Visitor 扩展。 所以现在你有：

• 每个 AST 节点上的样板代码看起来相同，但需要重复
• 父 Visitor 类必须为该语言中的每个 AST 节点都有一个 visit 方法（以便子类可以覆盖它）。
• 为了更容易编写像上面的 MyVisitor 这样的代码，Visitor 中的 visit 方法必须编写成默认情况下 visit(ChildNode*) 调用 visit(ParentNode*)。 否则，Loop 重载不会被 DoWhile 重载调用（例如）。

因此，有相当多的繁琐样板代码，并且在添加 AST 节点时需要手动修改更多代码：您必须去用新的 visit 存根调整 Visitor 类。

所有这些都是必要的，因为每个人（包括我自己）通常都认为像以下这样的代码通常是一个坏主意：

struct AstNode {
 void traverse(Visitor& visitor) {
  if (auto forLoop = toForLoop()) {
   visitor.visit(forLoop);
  } else if (auto whileLoop = toWhileLoop()) {
   visitor.visit(whileLoop);
  } else {
   // 还有 100 行像这样...
  }
 }
}

毕竟，当您添加新的 AST 节点时会发生什么？ 您仍然需要修改此列表，并且由于一切仍然扩展 Visitor，因此您仍然需要在此处添加新的 visit 存根。 但是如果没有基类怎么办？ 相反，如果 traverse 是一个 template 怎么办？

struct AstNode {
 template <typename VisitorType>
 void traverse(VisitorType& visitor) {
  if (auto forLoop = toForLoop()) {
   visitor.visit(forLoop);
  } else if (auto whileLoop = toWhileLoop()) {
   visitor.visit(whileLoop);
  } else {
   // 还有 100 行像这样...
  }
 }
}

请注意，如果在 C++ 中 visit 是 virtual 方法，则无法编写此代码； 您听说过 virtual template 吗？ 对于这样的代码，VisitorType 不需要定义_每个_重载，只要它有 AstNode 的版本即可。 此外，如果不存在 DoWhile 的更具体的版本，C++ 的常规重载解析规则将负责调用 Loop 重载。

剩下的唯一问题是有 100 行的 if-else（可能是 switch，几乎没有美学上的好处）。 但这正是 X Macro 模式再次发挥作用的地方！ 我们已经有所有 AST 节点类的列表，并且用于调用它们的代码几乎相同。 因此，Chapel 编译器有一个 doDispatch 函数（由 traverse 使用），如下所示：

来自 AstNode.h，第 377 行左右

  static void doDispatch(const AstNode* ast, Visitor& v) {
   switch (ast->tag()) {
    #define CONVERT(NAME) \
     case chpl::uast::asttags::NAME: \
     { \
      v.visit((const chpl::uast::NAME*) ast); \
      return; \
     }
    #define IGNORE(NAME) \
     case chpl::uast::asttags::NAME: \
     { \
      CHPL_ASSERT(false && "这段代码不应该运行"); \
     }
    #define AST_NODE(NAME) CONVERT(NAME)
    #define AST_BEGIN_SUBCLASSES(NAME) IGNORE(START_##NAME)
    #define AST_END_SUBCLASSES(NAME) IGNORE(END_##NAME)
    #include "chpl/uast/uast-classes-list.h"    IGNORE(NUM_AST_TAGS)
    IGNORE(AST_TAG_UNKNOWN)
    #undef AST_NODE
    #undef AST_BEGIN_SUBCLASSES
    #undef AST_END_SUBCLASSES
    #undef CONVERT
    #undef IGNORE
   }
   CHPL_ASSERT(false && "这段代码不应该运行");
  }

就是这样。 我们已经自动生成了遍历代码，允许我们以我认为非常优雅的方式使用访问者模式。 假设添加新 AST 节点的开发人员更新了 uast-classes-list.h 头文件，遍历逻辑将自动修改为正确处理新节点。

生成 Python 类层级

这很有趣。 有一段时间，在我的业余时间里，我一直在开发 Chapel 的 Python bindings。 这些 bindings 面向开发语言工具：用 Python 而不是 C++ 编写语言 linter、自动格式化程序，甚至可能是语言服务器感觉容易得多。 使用 Python 开发处理 Chapel 程序的 throwaway 脚本肯定更容易，这是 Chapel 团队的开发人员经常做的事情。

我决定让 Python AST 节点类层级与 C++ 版本匹配。 这在很多方面都很方便，包括能够包装父 AST 节点上的方法并使它们可以通过子 AST 节点使用，并且让 isinstance 正常工作。 从概念简单性的角度来看，它也很有利。 但是，我非常不想编写 CPython API 代码来定义 Chapel 语言中提供的许多 AST 节点类。

再次，uast-classes-list.h 头文件在这里发挥了作用。 我只需稍作努力，即可为类层级中的每个 AST 节点自动生成 PyTypeObject：

来自 chapel.cpp，第 563 行左右

#define DEFINE_PY_TYPE_FOR(NAME, TAG, FLAGS)\
 PyTypeObject NAME##Type = { \
  PyVarObject_HEAD_INIT(NULL, 0) \
  .tp_name = #NAME, \
  .tp_basicsize = sizeof(NAME##Object), \
  .tp_itemsize = 0, \
  .tp_flags = FLAGS, \
  .tp_doc = PyDoc_STR("A Chapel " #NAME " AST node"), \
  .tp_methods = (PyMethodDef*) PerNodeInfo<TAG>::methods, \
  .tp_base = parentTypeFor(TAG), \
  .tp_init = (initproc) NAME##Object_init, \
  .tp_new = PyType_GenericNew, \
 };
#define AST_NODE(NAME) DEFINE_PY_TYPE_FOR(NAME, chpl::uast::asttags::NAME, Py_TPFLAGS_DEFAULT)
#define AST_BEGIN_SUBCLASSES(NAME) DEFINE_PY_TYPE_FOR(NAME, chpl::uast::asttags::START_##NAME, Py_TPFLAGS_BASETYPE)
#define AST_END_SUBCLASSES(NAME)
#include "chpl/uast/uast-classes-list.h"#undef AST_NODE
#undef AST_BEGIN_SUBCLASSES
#undef AST_END_SUBCLASSES

您可能已经注意到我在上面的代码中偷偷地使用了 template。 这样做的动机是避免为每个 AST 节点写出（通常为空）的 Python 方法表。 特别是，我有一个 template，默认情况下，它提供一个空方法表，可以针对每个节点进行专用化，以便在必要时添加方法。 此细节对于下面的应用 3 很有用，但对于理解此处 X Macros 的使用不是必需的。

我使用了相同的 < 和 > 技巧来为每个 tag 生成 parentTypeFor：

来自 chapel.cpp，第 157 行左右

static PyTypeObject* parentTypeFor(chpl::uast::asttags::AstTag tag) {
#define AST_NODE(NAME)
#define AST_LEAF(NAME)
#define AST_BEGIN_SUBCLASSES(NAME)
#define AST_END_SUBCLASSES(NAME) \
 if (tag > chpl::uast::asttags::START_##NAME && tag < chpl::uast::asttags::END_##NAME) { \
  return &NAME##Type; \
 }
#include "chpl/uast/uast-classes-list.h"#include "chpl/uast/uast-classes-list.h"#undef AST_NODE
#undef AST_LEAF
#undef AST_BEGIN_SUBCLASSES
#undef AST_END_SUBCLASSES
 return &AstNodeType;
}

再次调用 uast-classes-list.h 宏几次，我就有了一个正常工作的类层级。 我没有显式地提及任何 AST 节点； 一切都源自 Chapel 编译器头文件。 这也意味着随着语言的变化和 AST 类层级的开发，Python bindings 的代码不需要更新。 只要使用最新版本的头文件进行编译，该层级就会与语言中存在的层级匹配。

这允许在 Python 中编写如下代码：

def print_decls(mod):
  """
  打印此 Chapel 模块中声明的所有内容。
  """
  for child in mod:
    if isinstance(child, NamedDecl):
      print(child.name())

应用 3: CPython 方法表和 Getters

Chapel Python bindings 再次使用了 X Macro 模式。 就像我之前提到的那样，我使用 template specialization 来减少声明 Python 对象所需的样板代码量。 特别是，有一个通用的方法表声明如下：

来自 chapel.cpp，第 541 行左右

template <chpl::uast::asttags::AstTag tag>
struct PerNodeInfo {
 static constexpr PyMethodDef methods[] = {
  {NULL, NULL, 0, NULL} /* 哨兵 */
 };
};

然后，当我需要添加方法时，我通过编写如下内容来使用 template specialization：

template <>
struct PerNodeInfo<TheAstTag> {
 static constexpr PyMethodDef methods[] = {
  {"method_name", TheNode_method_name, METH_NOARGS, "文档字符串"},
  // ... 更多类似以上内容 ...
  {NULL, NULL, 0, NULL} /* 哨兵 */
 };
};

在查看一个 PR 时，该 PR 将更多方法添加到 Python bindings（通过定义新的 TheNode_methodname 函数，然后将它们包含在方法表中），我注意到在该 PR 中，开发人员添加了一些方法，但忘记将它们放入各自的表中，导致 Python 客户端代码无法使用它们。 这伴随着另一个观察结果，即在声明 C++ 函数，然后将它们列在表格中时，存在适度的重复。 该名称（代码中的 method_name）出现了多次