Design Pattern

Visitor Design Pattern

Learned in CS247.

What problem does Visitor Pattern solve?

Write a method that depends on two polymorphic types (achieve Dynamic Dispatch).

Alternative solution?

Add behavior and functionality to classes, without changing the classes themselves (more on this below).

Example:

We might want different behaviours for each combination of these concrete classes.

class Weapon {
	public:
		virtual void strike(Enemy& e) = 0;
};

We can override this in Rock and Stick, but we don’t know which enemy we’re hitting. Same problem exists in reverse if we implement it inside of Enemy.

• Notice that dynamic casting can partially fix this issue, but not completely

Solution: Visitor Pattern - combine Overloading and Overriding.

class Enemy {
	public:
		virtual void beStruckBy(weapon& w) = 0;
		...
};
 
class Monster: public Enemy {
	public:
		void beStruckBy(Weapon& w) {
			w.strike(*this);
		}
};
 
 
class Turtle: public Enemy {
	public:
		void beStruckBy(Weapon& w) {
			w.strike(*this);
		}
};
 
class Weapon {
	public:
		virtual void strike(Monster& m) = 0;
		virtual void strike(Turtle& t) = 0;
};
 
class Rock: public Weapon {
	public:
		void strike(Monster& m) override {
			cout << "Rock vs. Monster" << endl;
		}
		void strike(Turtle& t) override {
			cout << "Rock vs. Tutrtle" << endl;
		}
}; // Stick looks similar
 
 
Enemy* e = ...;
Weapon* w = ...;
 
e->beStruckBy(*w);

1. beStruckBy is a virtual function $\to$ either calling Monster::beStruckBy or Turtle::beStruckBy (runtime)
2. Call w.strike on the Weapon&. Strike is virtual $\to$ Rock::strike or Stick::strike(runtime)
3. Are we calling Rock::strike(Turtle&) or Rock::strike(Monster&) ? We know the type of this. If this is a Turtle*, then use the Turtle version. If this is a Monster* , then use the Monster version (compile time)

Example: Compiler Design

2nd Use Case of Visitor Pattern

Another powerful use of the visitor pattern is to add behavior and functionality to classes, without changing the classes themselves.

Consider the following compiler design example.

I might want to collect info about my AST.

I could add a virtual method in ASTNode, override in concrete classes.

But: lots of changes are scattered over many classes. Difficult to understand, harder to implement incrementally.

Instead: provide nodes an accept method, taking in a polymorphic AstVisitor.

class AstNode { // like Enemy
	public:
		virtual void accept(AstVisitor& a) = 0; // like beStruckBy.
}
 
class IfStatement: public AstNode {
	public:
		void accept(AstVisitor& a) {
			a.visit(*this);
			// Call accept on subnodes in our ifStatement (boolean xpression, block of statements in ifStatement)
		}
};
 
class AstVisitor { // weapon
	public:
		virtual void visit(IfStatement& i) = 0;
		virtual void visit(WhileStatement& w) = 0;
		...
		// for each AstNode
}

Now, we can write different types of visitors to work on the parse tree. For example:

• String Visitor $\to$ collect string literals in program, that must go in the DATA segment
• Scope Visitor $\to$ match variables with associated scope
• CodeGeneration Visitor $\to$ generates assembly for each given node

Solution improves cohesiveness $\to$ all code for a particular visitor is located in one class. New visitor are easy to create, and can be made with 0 changes to the AST.

Complaint

The Visitor Pattern can result in lots of redundant code generated. We can improve this by using the Curiously Recurring Template Pattern.