8.21 實(shí)現(xiàn)訪問者模式

問題

你要處理由大量不同類型的對象組成的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，每一個對象都需要需要進(jìn)行不同的處理。比如，遍歷一個樹形結(jié)構(gòu)，然后根據(jù)每個節(jié)點(diǎn)的相應(yīng)狀態(tài)執(zhí)行不同的操作。

解決方案

這里遇到的問題在編程領(lǐng)域中是很普遍的，有時候會構(gòu)建一個由大量不同對象組成的數(shù)據(jù)結(jié)構(gòu)。假設(shè)你要寫一個表示數(shù)學(xué)表達(dá)式的程序，那么你可能需要定義如下的類：

class Node:
    pass

class UnaryOperator(Node):
    def __init__(self, operand):
        self.operand = operand

class BinaryOperator(Node):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class Add(BinaryOperator):
    pass

class Sub(BinaryOperator):
    pass

class Mul(BinaryOperator):
    pass

class Div(BinaryOperator):
    pass

class Negate(UnaryOperator):
    pass

class Number(Node):
    def __init__(self, value):
        self.value = value

然后利用這些類構(gòu)建嵌套數(shù)據(jù)結(jié)構(gòu)，如下所示：

# Representation of 1 + 2 * (3 - 4) / 5
t1 = Sub(Number(3), Number(4))
t2 = Mul(Number(2), t1)
t3 = Div(t2, Number(5))
t4 = Add(Number(1), t3)

這樣做的問題是對于每個表達(dá)式，每次都要重新定義一遍，有沒有一種更通用的方式讓它支持所有的數(shù)字和操作符呢。這里我們使用訪問者模式可以達(dá)到這樣的目的：

class NodeVisitor:
    def visit(self, node):
        methname = 'visit_' + type(node).__name__
        meth = getattr(self, methname, None)
        if meth is None:
            meth = self.generic_visit
        return meth(node)

    def generic_visit(self, node):
        raise RuntimeError('No {} method'.format('visit_' + type(node).__name__))

為了使用這個類，可以定義一個類繼承它并且實(shí)現(xiàn)各種 visit_Name() 方法，其中Name是node類型。例如，如果你想求表達(dá)式的值，可以這樣寫：

class Evaluator(NodeVisitor):
    def visit_Number(self, node):
        return node.value

    def visit_Add(self, node):
        return self.visit(node.left) + self.visit(node.right)

    def visit_Sub(self, node):
        return self.visit(node.left) - self.visit(node.right)

    def visit_Mul(self, node):
        return self.visit(node.left) * self.visit(node.right)

    def visit_Div(self, node):
        return self.visit(node.left) / self.visit(node.right)

    def visit_Negate(self, node):
        return -node.operand

使用示例：

>>> e = Evaluator()
>>> e.visit(t4)
0.6
>>>

作為一個不同的例子，下面定義一個類在一個棧上面將一個表達(dá)式轉(zhuǎn)換成多個操作序列：

class StackCode(NodeVisitor):
    def generate_code(self, node):
        self.instructions = []
        self.visit(node)
        return self.instructions

    def visit_Number(self, node):
        self.instructions.append(('PUSH', node.value))

    def binop(self, node, instruction):
        self.visit(node.left)
        self.visit(node.right)
        self.instructions.append((instruction,))

    def visit_Add(self, node):
        self.binop(node, 'ADD')

    def visit_Sub(self, node):
        self.binop(node, 'SUB')

    def visit_Mul(self, node):
        self.binop(node, 'MUL')

    def visit_Div(self, node):
        self.binop(node, 'DIV')

    def unaryop(self, node, instruction):
        self.visit(node.operand)
        self.instructions.append((instruction,))

    def visit_Negate(self, node):
        self.unaryop(node, 'NEG')

使用示例：

>>> s = StackCode()
>>> s.generate_code(t4)
[('PUSH', 1), ('PUSH', 2), ('PUSH', 3), ('PUSH', 4), ('SUB',),
('MUL',), ('PUSH', 5), ('DIV',), ('ADD',)]
>>>

討論

剛開始的時候你可能會寫大量的if/else語句來實(shí)現(xiàn)，這里訪問者模式的好處就是通過 getattr() 來獲取相應(yīng)的方法，并利用遞歸來遍歷所有的節(jié)點(diǎn)：

def binop(self, node, instruction):
    self.visit(node.left)
    self.visit(node.right)
    self.instructions.append((instruction,))

還有一點(diǎn)需要指出的是，這種技術(shù)也是實(shí)現(xiàn)其他語言中switch或case語句的方式。比如，如果你正在寫一個HTTP框架，你可能會寫這樣一個請求分發(fā)的控制器：

class HTTPHandler:
    def handle(self, request):
        methname = 'do_' + request.request_method
        getattr(self, methname)(request)
    def do_GET(self, request):
        pass
    def do_POST(self, request):
        pass
    def do_HEAD(self, request):
        pass

訪問者模式一個缺點(diǎn)就是它嚴(yán)重依賴遞歸，如果數(shù)據(jù)結(jié)構(gòu)嵌套層次太深可能會有問題，有時候會超過Python的遞歸深度限制(參考 sys.getrecursionlimit() )。

可以參照8.22小節(jié)，利用生成器或迭代器來實(shí)現(xiàn)非遞歸遍歷算法。

在跟解析和編譯相關(guān)的編程中使用訪問者模式是非常常見的。Python本身的 ast 模塊值的關(guān)注下，可以去看看源碼。9.24小節(jié)演示了一個利用 ast 模塊來處理Python源代碼的例子。