用访问者模式遍历树状结构

在写编译器和解释器的过程中，我们需要遍历抽象语法树并完成某些操作，比如生成目标代码。所有的语法类都继承自同一个基类，但对每个语法类的操作都不同。比如生成 if 语句目标代码的方法与生成 while 语句目标代码的方法就不一样。而且，这些操作还需要可扩展性。比如，我们除了生成目标代码，还希望写一个代码优化器。同样是遍历抽象语法树，代码优化器对语法类的操作显然与生成目标代码完全不同。

我们可以将这种访问模式抽象成一种通用的模型，它满足以下两点：

  1. 需要访问的一组类型有公共的基类；
  2. 对类型的访问操作必须是可以扩展的。

如果我们的访问模式符合这种类型，就可以使用访问者模式(Visitor Pattern)来实现。

访问者模式解决了什么问题

在 C++ 中，如果不使用 RTTI，我们无法在运行时知道某个对象的具体类型。即使可以使用 RTTI ，但因为编译器实现的原因，RTTI 的效率通常也难以接受。为了提供某种操作，通常的做法是在基类中提供一个纯虚函数接口，并且在子类中实现这个纯虚函数。

以抽象语法树为例。我们假设在某种语言中，只有整数节点 IntegerNode 和加法节点 SumNode 两种语法，它们都继承自公共基类 Node。为了支持求值(evaluation)操作，我们可以在公共基类 Node 中提供纯虚函数接口 Evaluate，并在整数节点和加法节点中分别实现求值方法。代码如下：

class Node {
 public:
  virtual ~Node() {}
  virtual int Evaluate() = 0;
};

class IntegerNode : public Node {
 public:
  Integer(int value) : value_(value) {}
  int Value() { return value_; }
  int Evaluate() override { 
    return Value();
  }
 private:
  int value_;
};

class SumNode : public Node {
 public:
  SumNode(Node* a, Node* b) : a_(a), b_(b) {}
  Node* A() { return a_; }
  Node* B() { return b_; }
  int Evaluate() override {
    return A().Evaluate() + B().Evaluate(); 
  }
 private:
  Node* a_;
  Node* b_;
};

在目前看来，虚函数机制已经很好地满足了我们的需求。然而，很快我们又有了新的需求：将抽象语法树打印出来。为此，我们可以提供一个新的接口 Print 来实现这个操作。增加的代码如下：

class Node {
 public:
  virtual void Print() = 0;
};

class IntegerNode : public Node {
 public:
  void Print() override {
    std::cout << Value();
  }
};

class SumNode : public Node {
 public:
  void Print() override {
    std::cout << "(";
    A().Print();
    std::cout << "+";
    B().Print();
    std::cout << ")";
  }
};

经过简单的修改，新的需求被满足了。然而好景不长，我们又有了新的需求：将抽象语法树存储到文件中。

在满足新的需求之前，请我们稍作停留，反思一下不断加虚函数的方式是否存在不足：

  1. 每次新增功能，都需要修改 Node 的接口，如果这样下去，最后 Node 和相关的具体类会变得臃肿不堪；
  2. 求值和打印操作实际上并不必须是 Node 的一部分，因为我们可以发现这两个函数仅仅使用抽象语法树提供的公共接口就完成了相应的功能。

这正是访问者模式所要解决的问题：

  1. 增加新的访问者（也就是新的功能）时不需要修改 Node 的接口；
  2. 访问者的实现和 Node 的实现分离。

访问者模式想要达到的效果是什么

在使用访问者模式重构我们的抽象语法树之前，请思考以下我们希望达到的效果是什么。我们可以脱离 C++ 的限制，假设有一种语言有我们想要的所有语法功能，在此条件下我们该如何写求值函数呢？

假设我们所用的 C++ 提供了判断某个对象是否是某个类型的操作符 instanceof ，一种实现求值函数的方法可能是：

int Evaluate(Node* node) {
  if (node instanceof IntegerNode) {
    return static_cast<IntegerNode*>(node)->Value();
  } else {
    SumNode* snode = static_cast<SumNode*>(node);
    return Evaluate(snode->A()) + Evaluate(snode->B());
  }
}

如果我们想要实现打印函数，也完全不需要修改 Node 的定义，而只需要新增一个 Print 函数，实现方法与 Evaluate 函数类似。

然而，现实的情况是我们并没有类似于 instanceof 的操作符来判断对象的类型。（RTTI 确实可以用于在运行时判断对象类型，但是 RTTI 的效率十分低下，而且有些工程会禁用 RTTI，因此我们只能另辟蹊径）

如何绕过 C++ 的这个限制呢？

如果继续从如何让 Evaluate 知道 node 的具体类型这个角度思考，我们总会走上实现一套粗糙而且错误百出的动态类型系统的道路。因此，不妨换个角度去想，那就是 node 所指向的对象在运行时永远知道自己是什么类型 ，这是显而易见的。如果能够让 node 所指向的对象去完成对应的操作，问题就解决了。那这样是不是又绕回文章刚开始处的实现方案了呢？

并不是这样。因为这一次，我们并不关注于某一种访问方式，而是尝试实现一套通用的访问方式。当我们提到某一种到通用的抽象的时候，继承就呼之欲出了。

访问者类型

我们首先引入访问者类型 NodeVisitor：

class NodeVisitor {
 public:
  virtual ~NodeVisitor();
  void Visit(Node* node) {
    node->Accept(this);
  }
  virtual void VisitImpl(IntegerNode* node) = 0;
  virtual void VisitImpl(SumNode* node) = 0;
};

访问者 NodeVisitor 提供了一个接口函数 Visit，用于访问一个 Node 对象。它还提供了两个纯虚函数，分别对应于访问 IntegerNode 和 SumNode 的具体实现，需要由子类提供具体的操作。

函数 Visit 将自己传递给了 Node 类型的 Accept 方法，这正是访问者模式的精妙之处：在 Accept 方法内部，Node 对象会明确地知道自己是什么类型，因此它能够反过来调用正确的访问方法。具体的实现如下：

class Node {
 public:
  virtual void Accept(NodeVisitor* visitor) = 0;
};

class IntegerNode : public Node {
 public:
  void Accept(NodeVisitor* visitor) override {
    // 调用的是 NodeVisitor::VisitImpl(IntegerNode*)
    visitor->VisitImpl(this);
  }
};

class SumNode : public Node {
 public:
  void Accept(NodeVisitor* visitor) override {
    // 调用的是 NodeVisitor::VisitImpl(SumNode*)
    visitor->VisitImpl(this);
  }
};

我们可以在访问者模式的基础上，实现 Evaluate 功能：

class EvaluateVisitor : public NodeVisitor {
 public:
  EvaluateVisitor() : result_(0) {}
  int Result() { return result_; }
  void VisitImpl(IntegerNode* node) {
    result_ = node->Value();
  }
  void VisitImpl(SumNode* node) {
    Visit(node->A());
    int a_result = result_;
    Visit(node->B());
    result_ += a_result;
  }
 private:
  int result_;
};

int Evaluate(Node* node) {
  EvaluateVisitor visitor;
  visitor.Visit(node);
  return visitor.Result();
}

其他的语言是如何处理这类问题的

我们之所以绕了一大圈，根本的原因是无法在运行时知道某个对象的具体类型。

在绝大多数动态类型语言中，因为可以在运行时判断对象类型，所以不会遇到此类问题。在 JavaScript 中，我们可以使用 obj instanceof Class 来判断 obj 是否是 Class 类型；在 Python 中，我们可以使用全局函数 isinstance(obj, Class) 来完成同样的功能。因为 Java 也支持 instanceof 操作符，所以也不会遇到问题。但考虑到 instanceof 常常不被建议使用，很多时候我们仍然会实现访问者模式。这类方法不被建议的原因是，instanceof 类的处理方式不是类型安全的。如果我们在写这个函数时忘记了某个子类，只有在程序执行的时候才会发现。而访问者模式会在编译时就因为某个纯虚函数没有在子类中被实现而报错。

在另一方面，现代的静态类型语言都对数据变体（Data Variant) 有各种各样的支持。数据变体与模式匹配(pattern matching)特性相结合后，可以非常漂亮地解决此类问题。所谓数据变体，指的正是抽象语法树这类数据类型。它们在本质上是同一种类型，即抽象语法树，但各自是不同的变体，即整数节点和加法节点。类似的例子还包括二叉树类型，它可以有两种变体，空节点和非空节点。模式匹配可以根据某个对象在运行时的实际类型来执行正确的操作。通过将数据变体与模式匹配结合，我们就可以写出类型安全的 instanceof 代码。

在经典的函数式编程语言 OCaml 中，我们可以将整个 Evaluate 简洁地写成这样（用 eval 代替长名字 evaluate）：

type node = 
  | Integer of int
  | Sum of node * node
;;

let rec eval n = match n with 
  | Integer i -> i
  | Sum (a, b) -> (eval a) + (eval b)
;;

对于完全不了解 OCaml 语法的人，也可以直观地猜测出这段代码的功能，这正是函数式编程直观性的体现。

总结

如果我们需要解决的设计难题满足以下两点，就可以使用访问者模式：

  1. 多个类型有公共基类；
  2. 每个类型的访问操作都不同，而且访问操作需要可扩展性。

访问者模式的实现分成三步：

  1. 定义访问者抽象基类，它提供一个对外的访问接口和一组接受具体类型的访问方法（与具体类型一一对应）；
  2. 公共基类提供接受访问者类型的接口，并且在子类中实现这一接口，每个子类反过来调用访问者的对应访问方法。
  3. 实现具体的访问者类型。
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,099评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,828评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,540评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,848评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,971评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,132评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,193评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,934评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,376评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,687评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,846评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,537评论 4赞 335
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,175评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,887评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,134评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,674评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,741评论 2赞 351