 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Visitor pattern" – news ·newspapers ·books ·scholar ·JSTOR(January 2022) (Learn how and when to remove this message) |
Avisitor pattern is asoftware design pattern that separates thealgorithm from theobject structure. Because of this separation, new operations can be added to existing object structures without modifying the structures. It is one way to follow theopen/closed principle inobject-oriented programming andsoftware engineering.
In essence, the visitor allows adding newvirtual functions to a family ofclasses, without modifying the classes. Instead, a visitor class is created that implements all of the appropriate specializations of the virtual function. The visitor takes the instance reference as input, and implements the goal throughdouble dispatch.
Programming languages withsum types andpattern matching obviate many of the benefits of the visitor pattern, as the visitor class is able to both easily branch on the type of the object and generate a compiler error if a new object type is defined which the visitor does not yet handle.
The Visitor[1]design pattern is one of the twenty-threeGang of Four design patterns.
When new operations are needed frequently and the object structure consists of many unrelated classes,it's inflexible to add new subclasses each time a new operation is requiredbecause "distributing all these operations across the various node classes leads to a system that's hard to understand, maintain, and change."[1]
This makes it possible to create new operations independently from the classes of an object structureby adding new visitor objects.
See also the UML class and sequence diagram below.
TheGang of Four defines the Visitor as:
Represent[ing] an operation to be performed on elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.
The nature of the Visitor makes it an ideal pattern to plug into public APIs, thus allowing its clients to perform operations on a class using a "visiting" class without having to modify the source.[2]
Moving operations into visitor classes is beneficial when
A drawback to this pattern, however, is that it makes extensions to the class hierarchy more difficult, as new classes typically require a newvisit method to be added to each visitor.
Consider the design of a 2Dcomputer-aided design (CAD) system. At its core, there are several types to represent basic geometric shapes like circles, lines, and arcs. The entities are ordered into layers, and at the top of the type hierarchy is the drawing, which is simply a list of layers, plus some added properties.
A fundamental operation on this type hierarchy is saving a drawing to the system's native file format. At first glance, it may seem acceptable to add local save methods to all types in the hierarchy. But it is also useful to be able to save drawings to other file formats. Adding ever more methods for saving into many different file formats soon clutters the relatively pure original geometric data structure.
A naive way to solve this would be to maintain separate functions for each file format. Such a save function would take a drawing as input, traverse it, and encode into that specific file format. As this is done for each added different format, duplication between the functions accumulates. For example, saving a circle shape in a raster format requires very similar code no matter what specific raster form is used, and is different from other primitive shapes. The case for other primitive shapes like lines and polygons is similar. Thus, the code becomes a large outer loop traversing through the objects, with a large decision tree inside the loop querying the type of the object. Another problem with this approach is that it is very easy to miss a shape in one or more savers, or a new primitive shape is introduced, but the save routine is implemented only for one file type and not others, leading to code extension and maintenance problems. As the versions of the same file grows it becomes more complicated to maintain it.
Instead, the visitor pattern can be applied. It encodes the logical operation (i.e. save(image_tree)) on the whole hierarchy into one class (i.e. Saver) that implements the common methods for traversing the tree and describes virtual helper methods (i.e. save_circle, save_square, etc.) to be implemented for format specific behaviors. In the case of the CAD example, such format specific behaviors would be implemented by a subclass of Visitor (i.e. SaverPNG). As such, all duplication of type checks and traversal steps is removed. Additionally, the compiler now complains if a shape is omitted since it is now expected by the common base traversal/save function.
The visitor pattern may be used for iteration overcontainer-like data structures just likeIterator pattern but with limited functionality.[3]: 288 For example,iteration over a directory structure could be implemented by a function class instead of more conventionalloop pattern. This would allow deriving various useful information from directories content by implementing a visitor functionality for every item whilereusing the iteration code. It's widely employed in Smalltalk systems and can be found in C++ as well.[3]: 289 A drawback of this approach, however, is that you can't break out of the loop easily or iterate concurrently (in parallel i.e. traversing two containers at the same time by a singlei variable).[3]: 289 The latter would require writing additional functionality for a visitor to support these features.[3]: 289
In theUMLclass diagram above, theElementA class doesn't implement a new operation directly.Instead,ElementA implements adispatching operationaccept(visitor) that "dispatches" (delegates) a request to the "accepted visitor object" (visitor.visitElementA(this)). TheVisitor1 class implements the operation (visitElementA(e:ElementA)).ElementB then implementsaccept(visitor) by dispatching tovisitor.visitElementB(this). TheVisitor1 class implements the operation (visitElementB(e:ElementB)).
TheUMLsequence diagramshows the run-time interactions: TheClient object traverses the elements of an object structure (ElementA,ElementB) and callsaccept(visitor) on each element.
First, theClient callsaccept(visitor) onElementA, which callsvisitElementA(this) on the acceptedvisitor object.The element itself (this) is passed to thevisitor so that it can "visit"ElementA (calloperationA()).
Thereafter, theClient callsaccept(visitor) onElementB, which callsvisitElementB(this) on thevisitor that "visits"ElementB (callsoperationB()).
The visitor pattern requires aprogramming language that supportssingle dispatch, as common object-oriented languages (such asC++,Java,Smalltalk,Objective-C,Swift,JavaScript,Python andC#) do. Under this condition, consider two objects, each of some class type; one is termed theelement, and the other isvisitor.
Thevisitor declares avisit method, which takes the element as an argument, for each class of element.Concrete visitors are derived from the visitor class and implement thesevisit methods, each of which implements part of the algorithm operating on the object structure. The state of the algorithm is maintained locally by the concrete visitor class.
Theelement declares anaccept method to accept a visitor, taking the visitor as an argument.Concrete elements, derived from the element class, implement theaccept method. In its simplest form, this is no more than a call to the visitor'svisit method.Composite elements, which maintain a list of child objects, typically iterate over these, calling each child'saccept method.
Theclient creates the object structure, directly or indirectly, and instantiates the concrete visitors. When an operation is to be performed which is implemented using the Visitor pattern, it calls theaccept method of the top-level element(s).
When theaccept method is called in the program, its implementation is chosen based on both the dynamic type of the element and the static type of the visitor. When the associatedvisit method is called, its implementation is chosen based on both the dynamic type of the visitor and the static type of the element, as known from within the implementation of theaccept method, which is the same as the dynamic type of the element. (As a bonus, if the visitor can't handle an argument of the given element's type, then the compiler will catch the error.)
Thus, the implementation of thevisit method is chosen based on both the dynamic type of the element and the dynamic type of the visitor. This effectively implementsdouble dispatch. For languages whose object systems support multiple dispatch, not only single dispatch, such asCommon Lisp orC# via theDynamic Language Runtime (DLR), implementation of the visitor pattern is greatly simplified (a.k.a. Dynamic Visitor) by allowing use of simple function overloading to cover all the cases being visited. A dynamic visitor, provided it operates on public data only, conforms to theopen/closed principle (since it does not modify extant structures) and to thesingle responsibility principle (since it implements the Visitor pattern in a separate component).
In this way, one algorithm can be written to traverse a graph of elements, and many different kinds of operations can be performed during that traversal by supplying different kinds of visitors to interact with the elements based on the dynamic types of both the elements and the visitors.
This example declares a separateExpressionPrintingVisitor class that takes care of the printing. If the introduction of a new concrete visitor is desired, a new class will be created to implement the Visitor interface, and new implementations for the Visit methods will be provided. The existing classes (Literal and Addition) will remain unchanged.
namespaceWikipedia.Examples;usingSystem;interfaceIVisitor{voidVisit(Literalliteral);voidVisit(Additionaddition);}classExpressionPrintingVisitor:IVisitor{publicvoidVisit(Literalliteral){Console.WriteLine(literal.Value);}publicvoidVisit(Additionaddition){doubleleftValue=addition.Left.GetValue();doublerightValue=addition.Right.GetValue();doublesum=addition.GetValue();Console.WriteLine($"{leftValue} + {rightValue} = {sum}");}}abstractclassExpression{publicabstractvoidAccept(IVisitorvisitor);publicabstractdoubleGetValue();}classLiteral:Expression{publicLiteral(doublevalue){this.Value=value;}publicdoubleValue{get;set;}publicoverridevoidAccept(IVisitorvisitor){visitor.Visit(this);}publicoverridedoubleGetValue(){returnValue;}}classAddition:Expression{publicAddition(Expressionleft,Expressionright){Left=left;Right=right;}publicExpressionLeft{get;set;}publicExpressionRight{get;set;}publicoverridevoidAccept(IVisitorvisitor){Left.Accept(visitor);Right.Accept(visitor);visitor.Visit(this);}publicoverridedoubleGetValue(){returnLeft.GetValue()+Right.GetValue();}}publicstaticclassProgram{publicstaticvoidMain(string[]args){// Emulate 1 + 2 + 3Additione=new(newAddition(newLiteral(1),newLiteral(2)),newLiteral(3));ExpressionPrintingVisitorprintingVisitor=new();e.Accept(printingVisitor);Console.ReadKey();}}
In this case, it is the object's responsibility to know how to print itself on a stream. The visitor here is then the object, not the stream.
"There's no syntax for creating a class. Classes are created by sending messages to other classes."WriteStreamsubclass:#ExpressionPrinterinstanceVariableNames:''classVariableNames:''package:'Wikipedia'.ExpressionPrinter>>write:anObject"Delegates the action to the object. The object doesn't need to be of any special class; it only needs to be able to understand the message #putOn:"anObjectputOn:self.^anObject.Objectsubclass:#ExpressioninstanceVariableNames:''classVariableNames:''package:'Wikipedia'.Expressionsubclass:#LiteralinstanceVariableNames:'value'classVariableNames:''package:'Wikipedia'.Literalclass>>with:aValue"Class method for building an instance of the Literal class"^selfnewvalue:aValue;yourself.Literal>>value:aValue"Setter for value"value:=aValue.Literal>>putOn:aStream"A Literal object knows how to print itself"aStreamnextPutAll:valueasString.Expressionsubclass:#AdditioninstanceVariableNames:'left right'classVariableNames:''package:'Wikipedia'.Additionclass>>left:aright:b"Class method for building an instance of the Addition class"^selfnewleft:a;right:b;yourself.Addition>>left:anExpression"Setter for left"left:=anExpression.Addition>>right:anExpression"Setter for right"right:=anExpression.Addition>>putOn:aStream"An Addition object knows how to print itself"aStreamnextPut:$(.leftputOn:aStream.aStreamnextPut:$+.rightputOn:aStream.aStreamnextPut:$).Objectsubclass:#PrograminstanceVariableNames:''classVariableNames:''package:'Wikipedia'.Program>>main|expressionstream|expression:=Additionleft: (Additionleft: (Literalwith:1)right: (Literalwith:2))right: (Literalwith:3).stream:=ExpressionPrinteron: (Stringnew:100).streamwrite:expression.Transcriptshow:streamcontents.Transcriptflush.
Go does not support method overloading, so the visit methods need different names. A typical visitor interface might be
typeVisitorinterface{visitWheel(wheelWheel)stringvisitEngine(engineEngine)stringvisitBody(bodyBody)stringvisitCar(carCar)string}
The following example is in the languageJava, and shows how the contents of a tree of nodes (in this case describing the components of a car) can be printed. Instead of creatingprint methods for each node subclass (Wheel,Engine,Body, andCar), one visitor class (CarElementPrintVisitor) performs the required printing action. Because different node subclasses require slightly different actions to print properly,CarElementPrintVisitor dispatches actions based on the class of the argument passed to itsvisit method.CarElementDoVisitor, which is analogous to a save operation for a different file format, does likewise.
packageorg.wikipedia.examples;importjava.util.List;interfaceCarElement{voidaccept(CarElementVisitorvisitor);}interfaceCarElementVisitor{voidvisit(Bodybody);voidvisit(Carcar);voidvisit(Engineengine);voidvisit(Wheelwheel);}classWheelimplementsCarElement{privatefinalStringname;publicWheel(finalStringname){this.name=name;}publicStringgetName(){returnname;}@Overridepublicvoidaccept(CarElementVisitorvisitor){/* * accept(CarElementVisitor) in Wheel implements * accept(CarElementVisitor) in CarElement, so the call * to accept is bound at run time. This can be considered * the *first* dispatch. However, the decision to call * visit(Wheel) (as opposed to visit(Engine) etc.) can be * made during compile time since 'this' is known at compile * time to be a Wheel. Moreover, each implementation of * CarElementVisitor implements the visit(Wheel), which is * another decision that is made at run time. This can be * considered the *second* dispatch. */visitor.visit(this);}}classBodyimplementsCarElement{@Overridepublicvoidaccept(CarElementVisitorvisitor){visitor.visit(this);}}classEngineimplementsCarElement{@Overridepublicvoidaccept(CarElementVisitorvisitor){visitor.visit(this);}}classCarimplementsCarElement{privatefinalList<CarElement>elements;publicCar(){this.elements=List.of(newWheel("front left"),newWheel("front right"),newWheel("back left"),newWheel("back right"),newBody(),newEngine());}@Overridepublicvoidaccept(CarElementVisitorvisitor){for(CarElementelement:elements){element.accept(visitor);}visitor.visit(this);}}classCarElementDoVisitorimplementsCarElementVisitor{@Overridepublicvoidvisit(Bodybody){System.out.println("Moving my body");}@Overridepublicvoidvisit(Carcar){System.out.println("Starting my car");}@Overridepublicvoidvisit(Wheelwheel){System.out.printf("Kicking my %s wheel%n",wheel.getName());}@Overridepublicvoidvisit(Engineengine){System.out.println("Starting my engine");}}classCarElementPrintVisitorimplementsCarElementVisitor{@Overridepublicvoidvisit(Bodybody){System.out.println("Visiting body");}@Overridepublicvoidvisit(Carcar){System.out.println("Visiting car");}@Overridepublicvoidvisit(Engineengine){System.out.println("Visiting engine");}@Overridepublicvoidvisit(Wheelwheel){System.out.printf("Visiting %s wheel%n",wheel.getName());}}publicclassVisitorDemo{publicstaticvoidmain(String[]args){Carcar=newCar();car.accept(newCarElementPrintVisitor());car.accept(newCarElementDoVisitor());}}
Visiting front left wheelVisiting front right wheelVisiting back left wheelVisiting back right wheelVisiting bodyVisiting engineVisiting carKicking my front left wheelKicking my front right wheelKicking my back left wheelKicking my back right wheelMoving my bodyStarting my engineStarting my car
(defclassauto()((elements:initarg:elements)))(defclassauto-part()((name:initarg:name:initform"<unnamed-car-part>")))(defmethodprint-object((pauto-part)stream)(print-object(slot-valuep'name)stream))(defclasswheel(auto-part)())(defclassbody(auto-part)())(defclassengine(auto-part)())(defgenerictraverse(functionobjectother-object))(defmethodtraverse(function(aauto)other-object)(with-slots(elements)a(dolist(eelements)(funcallfunctioneother-object))));; do-something visitations;; catch all(defmethoddo-something(objectother-object)(formatt"don't know how ~s and ~s should interact~%"objectother-object));; visitation involving wheel and integer(defmethoddo-something((objectwheel)(other-objectinteger))(formatt"kicking wheel ~s ~s times~%"objectother-object));; visitation involving wheel and symbol(defmethoddo-something((objectwheel)(other-objectsymbol))(formatt"kicking wheel ~s symbolically using symbol ~s~%"objectother-object))(defmethoddo-something((objectengine)(other-objectinteger))(formatt"starting engine ~s ~s times~%"objectother-object))(defmethoddo-something((objectengine)(other-objectsymbol))(formatt"starting engine ~s symbolically using symbol ~s~%"objectother-object))(let((a(make-instance'auto:elements`(,(make-instance'wheel:name"front-left-wheel"),(make-instance'wheel:name"front-right-wheel"),(make-instance'wheel:name"rear-left-wheel"),(make-instance'wheel:name"rear-right-wheel"),(make-instance'body:name"body"),(make-instance'engine:name"engine")))));; traverse to print elements;; stream *standard-output* plays the role of other-object here(traverse#'printa*standard-output*)(terpri);; print newline;; traverse with arbitrary context from other object(traverse#'do-somethinga42);; traverse with arbitrary context from other object(traverse#'do-somethinga'abc))
"front-left-wheel""front-right-wheel""rear-left-wheel""rear-right-wheel""body""engine"kicking wheel "front-left-wheel" 42 timeskicking wheel "front-right-wheel" 42 timeskicking wheel "rear-left-wheel" 42 timeskicking wheel "rear-right-wheel" 42 timesdon't know how "body" and 42 should interactstarting engine "engine" 42 timeskicking wheel "front-left-wheel" symbolically using symbol ABCkicking wheel "front-right-wheel" symbolically using symbol ABCkicking wheel "rear-left-wheel" symbolically using symbol ABCkicking wheel "rear-right-wheel" symbolically using symbol ABCdon't know how "body" and ABC should interactstarting engine "engine" symbolically using symbol ABC
Theother-object parameter is superfluous intraverse. The reason is that it is possible to use an anonymous function that calls the desired target method with a lexically captured object:
(defmethodtraverse(function(aauto));; other-object removed(with-slots(elements)a(dolist(eelements)(funcallfunctione))));; from here too;; ...;; alternative way to print-traverse(traverse(lambda(o)(printo*standard-output*))a);; alternative way to do-something with;; elements of a and integer 42(traverse(lambda(o)(do-somethingo42))a)
Now, the multiple dispatch occurs in the call issued from the body of the anonymous function, and sotraverse is just a mapping function that distributes a function application over the elements of an object. Thus all traces of the Visitor Pattern disappear, except for the mapping function, in which there is no evidence of two objects being involved. All knowledge of there being two objects and a dispatch on their types is in the lambda function.
Python does not support method overloading in the classical sense (polymorphic behavior according to type of passed parameters), so the "visit" methods for the different model types need to have different names.
"""Visitor pattern example."""fromabcimportABCMeta,abstractmethodfromtypingimportNoReturnNOT_IMPLEMENTED:str="You should implement this."classCarElement(metaclass=ABCMeta):@abstractmethoddefaccept(self,visitor:CarElementVisitor)->NoReturn:raiseNotImplementedError(NOT_IMPLEMENTED)classBody(CarElement):defaccept(self,visitor:CarElementVisitor)->None:visitor.visit_body(self)classEngine(CarElement):defaccept(self,visitor:CarElementVisitor)->None:visitor.visit_engine(self)classWheel(CarElement):def__init__(self,name:str)->None:self.name=namedefaccept(self,visitor:CarElementVisitor)->None:visitor.visit_wheel(self)classCar(CarElement):def__init__(self)->None:self.elements:list[CarElement]=[Wheel("front left"),Wheel("front right"),Wheel("back left"),Wheel("back right"),Body(),Engine()]defaccept(self,visitor):forelementinself.elements:element.accept(visitor)visitor.visit_car(self)classCarElementVisitor(metaclass=ABCMeta):@abstractmethoddefvisit_body(self,element:CarElement)->NoReturn:raiseNotImplementedError(NOT_IMPLEMENTED)@abstractmethoddefvisit_engine(self,element:CarElement)->NoReturn:raiseNotImplementedError(NOT_IMPLEMENTED)@abstractmethoddefvisit_wheel(self,element:CarElement)->NoReturn:raiseNotImplementedError(NOT_IMPLEMENTED)@abstractmethoddefvisit_car(self,element:CarElement)->NoReturn:raiseNotImplementedError(NOT_IMPLEMENTED)classCarElementDoVisitor(CarElementVisitor):defvisit_body(self,body:Body)->None:print("Moving my body.")defvisit_car(self,car:Car)->None:print("Starting my car.")defvisit_wheel(self,wheel:Wheel)->None:print(f"Kicking my{wheel.name} wheel.")defvisit_engine(self,engine:Engine)->None:print("Starting my engine.")classCarElementPrintVisitor(CarElementVisitor):defvisit_body(self,body:Body)->None:print("Visiting body.")defvisit_car(self,car:Car)->None:print("Visiting car.")defvisit_wheel(self,wheel:Wheel)->None:print(f"Visiting{wheel.name} wheel.")defvisit_engine(self,engine:Engine)->None:print("Visiting engine.")if__name__=="__main__":car:Car=Car()car.accept(CarElementPrintVisitor())car.accept(CarElementDoVisitor())
Visiting front left wheel.Visiting front right wheel.Visiting back left wheel.Visiting back right wheel.Visiting body.Visiting engine.Visiting car.Kicking my front left wheel.Kicking my front right wheel.Kicking my back left wheel.Kicking my back right wheel.Moving my body.Starting my engine.Starting my car.
Using Python 3 or above allows to make a general implementation of the accept method:
classVisitable:defaccept(self,visitor:Visitor)->Any:lookup:str=f"visit_{self.__qualname__.replace(".","_")}"returngetattr(visitor,lookup)(self)
One could extend this to iterate over the class's method resolution order if they would like to fall back on already-implemented classes. They could also use the subclass hook feature to define the lookup in advance.
{{cite web}}: CS1 maint: url-status (link)
