在寫(xiě)編譯器和解釋器的過(guò)程中履磨，我們需要遍歷抽象語(yǔ)法樹(shù)并完成某些操作诵冒，比如生成目標(biāo)代碼。所有的語(yǔ)法類都繼承自同一個(gè)基類仑濒，但對(duì)每個(gè)語(yǔ)法類的操作都不同。比如生成 if 語(yǔ)句目標(biāo)代碼的方法與生成 while 語(yǔ)句目標(biāo)代碼的方法就不一樣偷遗。而且墩瞳，這些操作還需要可擴(kuò)展性。比如氏豌，我們除了生成目標(biāo)代碼喉酌，還希望寫(xiě)一個(gè)代碼優(yōu)化器。同樣是遍歷抽象語(yǔ)法樹(shù)泵喘，代碼優(yōu)化器對(duì)語(yǔ)法類的操作顯然與生成目標(biāo)代碼完全不同泪电。
我們可以將這種訪問(wèn)模式抽象成一種通用的模型，它滿足以下兩點(diǎn)：
- 需要訪問(wèn)的一組類型有公共的基類纪铺；
- 對(duì)類型的訪問(wèn)操作必須是可以擴(kuò)展的相速。
如果我們的訪問(wèn)模式符合這種類型，就可以使用訪問(wèn)者模式(Visitor Pattern)來(lái)實(shí)現(xiàn)鲜锚。
訪問(wèn)者模式解決了什么問(wèn)題
在 C++ 中和蚪，如果不使用 RTTI止状，我們無(wú)法在運(yùn)行時(shí)知道某個(gè)對(duì)象的具體類型。即使可以使用 RTTI 攒霹，但因?yàn)榫幾g器實(shí)現(xiàn)的原因怯疤，RTTI 的效率通常也難以接受。為了提供某種操作催束，通常的做法是在基類中提供一個(gè)純虛函數(shù)接口集峦，并且在子類中實(shí)現(xiàn)這個(gè)純虛函數(shù)。
以抽象語(yǔ)法樹(shù)為例抠刺。我們假設(shè)在某種語(yǔ)言中塔淤，只有整數(shù)節(jié)點(diǎn) IntegerNode 和加法節(jié)點(diǎn) SumNode 兩種語(yǔ)法，它們都繼承自公共基類 Node速妖。為了支持求值(evaluation)操作高蜂，我們可以在公共基類 Node 中提供純虛函數(shù)接口 Evaluate，并在整數(shù)節(jié)點(diǎn)和加法節(jié)點(diǎn)中分別實(shí)現(xiàn)求值方法罕容。代碼如下：
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_;
};
在目前看來(lái)备恤，虛函數(shù)機(jī)制已經(jīng)很好地滿足了我們的需求。然而锦秒，很快我們又有了新的需求：將抽象語(yǔ)法樹(shù)打印出來(lái)露泊。為此，我們可以提供一個(gè)新的接口 Print 來(lái)實(shí)現(xiàn)這個(gè)操作旅择。增加的代碼如下：
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 << ")";
}
};
經(jīng)過(guò)簡(jiǎn)單的修改惭笑，新的需求被滿足了。然而好景不長(zhǎng)生真，我們又有了新的需求：將抽象語(yǔ)法樹(shù)存儲(chǔ)到文件中沉噩。
在滿足新的需求之前，請(qǐng)我們稍作停留柱蟀，反思一下不斷加虛函數(shù)的方式是否存在不足：
- 每次新增功能屁擅，都需要修改 Node 的接口，如果這樣下去产弹，最后 Node 和相關(guān)的具體類會(huì)變得臃腫不堪；
- 求值和打印操作實(shí)際上并不必須是 Node 的一部分弯囊，因?yàn)槲覀兛梢园l(fā)現(xiàn)這兩個(gè)函數(shù)僅僅使用抽象語(yǔ)法樹(shù)提供的公共接口就完成了相應(yīng)的功能痰哨。
這正是訪問(wèn)者模式所要解決的問(wèn)題：
- 增加新的訪問(wèn)者（也就是新的功能）時(shí)不需要修改 Node 的接口；
- 訪問(wèn)者的實(shí)現(xiàn)和 Node 的實(shí)現(xiàn)分離匾嘱。
訪問(wèn)者模式想要達(dá)到的效果是什么
在使用訪問(wèn)者模式重構(gòu)我們的抽象語(yǔ)法樹(shù)之前斤斧，請(qǐng)思考以下我們希望達(dá)到的效果是什么。我們可以脫離 C++ 的限制霎烙，假設(shè)有一種語(yǔ)言有我們想要的所有語(yǔ)法功能撬讽，在此條件下我們?cè)撊绾螌?xiě)求值函數(shù)呢蕊连？
假設(shè)我們所用的 C++ 提供了判斷某個(gè)對(duì)象是否是某個(gè)類型的操作符 instanceof ，一種實(shí)現(xiàn)求值函數(shù)的方法可能是：
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());
}
}
如果我們想要實(shí)現(xiàn)打印函數(shù)游昼，也完全不需要修改 Node 的定義甘苍，而只需要新增一個(gè) Print 函數(shù)，實(shí)現(xiàn)方法與 Evaluate 函數(shù)類似烘豌。
然而载庭，現(xiàn)實(shí)的情況是我們并沒(méi)有類似于 instanceof 的操作符來(lái)判斷對(duì)象的類型。（RTTI 確實(shí)可以用于在運(yùn)行時(shí)判斷對(duì)象類型廊佩，但是 RTTI 的效率十分低下囚聚，而且有些工程會(huì)禁用 RTTI，因此我們只能另辟蹊徑）
如何繞過(guò) C++ 的這個(gè)限制呢标锄？
如果繼續(xù)從如何讓 Evaluate 知道 node 的具體類型這個(gè)角度思考顽铸，我們總會(huì)走上實(shí)現(xiàn)一套粗糙而且錯(cuò)誤百出的動(dòng)態(tài)類型系統(tǒng)的道路。因此料皇，不妨換個(gè)角度去想谓松，那就是 node 所指向的對(duì)象在運(yùn)行時(shí)永遠(yuǎn)知道自己是什么類型 ，這是顯而易見(jiàn)的瓶蝴。如果能夠讓 node 所指向的對(duì)象去完成對(duì)應(yīng)的操作毒返，問(wèn)題就解決了。那這樣是不是又繞回文章剛開(kāi)始處的實(shí)現(xiàn)方案了呢舷手？
并不是這樣拧簸。因?yàn)檫@一次，我們并不關(guān)注于某一種訪問(wèn)方式男窟，而是嘗試實(shí)現(xiàn)一套通用的訪問(wèn)方式盆赤。當(dāng)我們提到某一種到通用的抽象的時(shí)候，繼承就呼之欲出了歉眷。
訪問(wèn)者類型
我們首先引入訪問(wèn)者類型 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;
};
訪問(wèn)者 NodeVisitor 提供了一個(gè)接口函數(shù) Visit牺六，用于訪問(wèn)一個(gè) Node 對(duì)象。它還提供了兩個(gè)純虛函數(shù)汗捡，分別對(duì)應(yīng)于訪問(wèn) IntegerNode 和 SumNode 的具體實(shí)現(xiàn)淑际，需要由子類提供具體的操作。
函數(shù) Visit 將自己傳遞給了 Node 類型的 Accept 方法扇住，這正是訪問(wèn)者模式的精妙之處：在 Accept 方法內(nèi)部春缕，Node 對(duì)象會(huì)明確地知道自己是什么類型，因此它能夠反過(guò)來(lái)調(diào)用正確的訪問(wèn)方法艘蹋。具體的實(shí)現(xiàn)如下：
class Node {
public:
virtual void Accept(NodeVisitor* visitor) = 0;
};
class IntegerNode : public Node {
public:
void Accept(NodeVisitor* visitor) override {
// 調(diào)用的是 NodeVisitor::VisitImpl(IntegerNode*)
visitor->VisitImpl(this);
}
};
class SumNode : public Node {
public:
void Accept(NodeVisitor* visitor) override {
// 調(diào)用的是 NodeVisitor::VisitImpl(SumNode*)
visitor->VisitImpl(this);
}
};
我們可以在訪問(wèn)者模式的基礎(chǔ)上锄贼，實(shí)現(xiàn) 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();
}
其他的語(yǔ)言是如何處理這類問(wèn)題的
我們之所以繞了一大圈，根本的原因是無(wú)法在運(yùn)行時(shí)知道某個(gè)對(duì)象的具體類型女阀。
在絕大多數(shù)動(dòng)態(tài)類型語(yǔ)言中宅荤，因?yàn)榭梢栽谶\(yùn)行時(shí)判斷對(duì)象類型屑迂，所以不會(huì)遇到此類問(wèn)題。在 JavaScript 中冯键，我們可以使用 obj instanceof Class 來(lái)判斷 obj 是否是 Class 類型惹盼；在 Python 中搭盾，我們可以使用全局函數(shù) isinstance(obj, Class) 來(lái)完成同樣的功能谱仪。因?yàn)?Java 也支持 instanceof 操作符服爷，所以也不會(huì)遇到問(wèn)題陆赋。但考慮到 instanceof 常常不被建議使用愚隧，很多時(shí)候我們?nèi)匀粫?huì)實(shí)現(xiàn)訪問(wèn)者模式们妥。這類方法不被建議的原因是拥刻，instanceof 類的處理方式不是類型安全的潭辈。如果我們?cè)趯?xiě)這個(gè)函數(shù)時(shí)忘記了某個(gè)子類所袁，只有在程序執(zhí)行的時(shí)候才會(huì)發(fā)現(xiàn)盏档。而訪問(wèn)者模式會(huì)在編譯時(shí)就因?yàn)槟硞€(gè)純虛函數(shù)沒(méi)有在子類中被實(shí)現(xiàn)而報(bào)錯(cuò)。
在另一方面燥爷，現(xiàn)代的靜態(tài)類型語(yǔ)言都對(duì)數(shù)據(jù)變體（Data Variant) 有各種各樣的支持蜈亩。數(shù)據(jù)變體與模式匹配(pattern matching)特性相結(jié)合后，可以非常漂亮地解決此類問(wèn)題前翎。所謂數(shù)據(jù)變體稚配，指的正是抽象語(yǔ)法樹(shù)這類數(shù)據(jù)類型。它們?cè)诒举|(zhì)上是同一種類型港华，即抽象語(yǔ)法樹(shù)道川，但各自是不同的變體，即整數(shù)節(jié)點(diǎn)和加法節(jié)點(diǎn)立宜。類似的例子還包括二叉樹(shù)類型冒萄，它可以有兩種變體，空節(jié)點(diǎn)和非空節(jié)點(diǎn)橙数。模式匹配可以根據(jù)某個(gè)對(duì)象在運(yùn)行時(shí)的實(shí)際類型來(lái)執(zhí)行正確的操作尊流。通過(guò)將數(shù)據(jù)變體與模式匹配結(jié)合，我們就可以寫(xiě)出類型安全的 instanceof 代碼灯帮。
在經(jīng)典的函數(shù)式編程語(yǔ)言 OCaml 中崖技，我們可以將整個(gè) Evaluate 簡(jiǎn)潔地寫(xiě)成這樣（用 eval 代替長(zhǎng)名字 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)
;;
對(duì)于完全不了解 OCaml 語(yǔ)法的人，也可以直觀地猜測(cè)出這段代碼的功能钟哥，這正是函數(shù)式編程直觀性的體現(xiàn)迎献。
總結(jié)
如果我們需要解決的設(shè)計(jì)難題滿足以下兩點(diǎn)，就可以使用訪問(wèn)者模式：
- 多個(gè)類型有公共基類瞪醋；
- 每個(gè)類型的訪問(wèn)操作都不同，而且訪問(wèn)操作需要可擴(kuò)展性装诡。
訪問(wèn)者模式的實(shí)現(xiàn)分成三步：
- 定義訪問(wèn)者抽象基類银受，它提供一個(gè)對(duì)外的訪問(wèn)接口和一組接受具體類型的訪問(wèn)方法（與具體類型一一對(duì)應(yīng)）践盼；
- 公共基類提供接受訪問(wèn)者類型的接口，并且在子類中實(shí)現(xiàn)這一接口宾巍，每個(gè)子類反過(guò)來(lái)調(diào)用訪問(wèn)者的對(duì)應(yīng)訪問(wèn)方法咕幻。
- 實(shí)現(xiàn)具體的訪問(wèn)者類型。
