На этом шаге мы рассмотрим общую структуру этого шаблона и особенности его реализации.
Задача
Вам нужно написать код, который обрабатывает сложную структуру данных, состоящую из множества различных типов объектов, каждый из которых нужно
обрабатывать отдельным способом. Примером этого может послужить прохождение по древовидной структуре и выполнение различных действий в
зависимости от того, какие узлы дерева встречаются по пути.
Решение
Задача, которая решается этим рецептом, часто возникает в программах, которые строят структуры данных, состоящие из большого количества разнородных объектов. Чтобы проиллюстрировать это, предположим, что вы пытаетесь написать программу, которая представляет математические выражения. Чтобы сделать это, программа может использовать классы:
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
Эти классы могут в дальнейшем применяться для построения вложенных структур данных:
# Представление 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)
Проблема не в создании таких структур, а в написании кода, который будет их обрабатывать. Например, в таком выражении программа может захотеть выполнить любое количество операций (т. е. создать вывод, сгенерировать инструкции, выполнить перевод и т. п.).
При необходимости подключить обработку общего назначения обычное решение заключается в реализации паттерна "Посетитель" с использованием вот такого класса:
>>> 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__)) >>>
Чтобы использовать этот класс, программист наследует от него и реализует различные методы формы visit_Name(), где вместо Name подставляется тип узла. Например, если вы хотите выполнить выражение, вы можете написать это так:
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
В качестве совершенно другого примера приведем класс, который транслирует выражение в операции на простой стековой машине:
>>> 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',)]
>>>
Обсуждение
В этом рецепте две ключевые идеи. Первая - это стратегия проектирования, при которой код, который манипулирует сложной структурой данных, отделен от самой структуры данных. Здесь это применено так: ни один из различных классов Node не предоставляет никаких реализаций, которые что-то делают с данными. Вместо этого все манипуляции с данными выполняются специальными реализациями отдельного класса NodeVisitor. Это разделение делает код максимально общим, а не специализированным.
Вторая ключевая идея - реализация класса-посетителя как такового. В посетителе вы хотите переключаться между методами обработки в зависимости от некоторого значения, такого как тип узла. В элементарной реализации вы могли бы склониться к созданию огромного объявления if:
class NodeVisitor: def visit(self, node): nodetype = type(node).__name__ if nodetype == 'Number': return self.visit_Number(node) elif nodetype == 'Add': return self.visit_Add(node) elif nodetype == 'Sub': return self.visit_Sub(node) . . .
Однако быстро станет ясно, что на самом деле вам не стоит выбирать такой подход. Помимо того что он чрезвычайно многословен, он еще и медленно работает, а также его трудно поддерживать, если вы захотите добавить или изменить типы обрабатываемых узлов. Вместо этого лучше исполнить маленький фокус, при котором вы формируете имя метода и получаете его с помощью функции getattr(). Метод generic_visit() в показанном решении - это запасной вариант, который будет применен, если не будет найден подходящий метод обработки. В этом рецепте он возбуждает исключение, чтобы предупредить программиста о том, что встретился неожиданный тип узла.
В каждом классе-посетителе вычисления обычно вызываются рекурсивными вызовами метода visit(). Например:
class Evaluator(NodeVisitor): . . . def visit_Add(self, node): return self.visit(node.left) + self.visit(node.right)
Данная рекурсия заставляет класс-посетитель обходить всю структуру данных целиком. Вы вызываете visit() до тех пор, пока не достигнете некого конечного узла, такого как Number в приведенном выше примере. Точный порядок рекурсии и других операций полностью зависит от приложения.
Стоит отметить, что в этом конкретном приеме переключение на нужный метод - это также обычный способ эмуляции поведения условного выражения или выражения-переключателя (switch), которые можно встретить в других языках. Например, если вы пишете HTTP-фреймворк, то у вас могут получиться классы, которые выполняют похожую диспетчеризацию:
class HTTPHandler: def handle(self, request): methname = 'do_' + request.request_method getattr(self, methname)(request) def do_GET(self, request): . . . def do_POST(self, request): . . . def do_HEAD(self, request): . . .
Слабая сторона шаблона "Посетитель" - это привязка к рекурсии. Если вы попытаетесь применить его к глубоко вложенной структуре, есть возможность достигнуть лимита Python на рекурсию (см. sys.getrecursionlimit()). Чтобы обойти эту проблему, вы можете делать определенные выборы в ваших структурах данных. Например, вы можете использовать обычные списки Python вместо связанных списков или попытаться агрегировать больше данных в каждый узел, чтобы сделать структуру менее глубоко вложенной.
Вы также можете попытаться применить нерекурсивные алгоритмы обхода на основе генераторов или итераторов, как это рассматривается в следующем рецепте.
Использование шаблона "Посетитель" очень распространено в программах, связанных с парсингом или компилированием. Интересная реализация может быть найдена в модуле ast Python. В дополнение к возможности обхода древовидных структур он предоставляет вариант, который позволяет переписывать и трансформировать структуру данных по мере ее обхода (то есть добавлять или удалять узлы). Больше информации об этом вы найдете в исходном коде модуля ast.
На следующем шаге мы рассмотрим реализацию шаблона "Посетитель" без рекурсии.
