Design Pattern : visitor implementation in Java


The source code of design patterns can be viewed and downloaded here :
https://github.com/ebundy/java-examples/tree/master/design-patterns

What is it ?

The visitor design pattern is a behavioral pattern.
The pattern splits the model data and its operations in distinct structures.

When using it ?

Multiple reasons :

1) We want to define new operations without changing the model at each time because the model doesn’t change often while operations change frequently.

2) We don’t want to couple model and behavior because we want to have a reusable model in multiple applications or we want to have an extensible model that allow client classes to define their behaviors with their own classes.

3) We have common operations that depend on the concrete type of the model but we don’t want to implement the logic in each subclass as that would explode common logic in multiple classes and so in multiple places.

4) We need a double dispatch.
We have variables declared with interface types and we want to be able to process them according their runtime type … of course without using if (myObj instanceof Foo) {} or any trick.
The idea is for example to pass these variables to methods that declares a concrete type of the interface as parameter to apply a specific processing. 
This way of doing is not possible  out of the box with languages relies on a single-dispatch because the chosen invoked at runtime depends only on the runtime type of the receiver.
Note that in Java, the method (signature) to call is chosen at compile time and it depends on the declared type of the parameters, not their runtime type.

The last point that is a reason to use the visitor is also a consequence because as you implement the visitor (of course for languages that doesn’t support multiple dispatch), you necessarily need to introduce a double dispatch implementation.

I propose you to explore the visitor around a chess game.

Our use case : piece moving for humans and bots in a chess game

Suppose we are developing a chess game and now we would like to define processing as player requests a piece moving.
Without the visitor pattern use, we could define piece moving behaviors directly in the pieces subclasses.
We could have for example a Piece interface such as :

public interface Piece{
 
	boolean checkMoveValidity(Coordinates coord);
 
	void performMove(Coordinates coord);
 
	Piece computeIfKingCheck();
 
}

Each Piece subclass would implement it such as :

public class Pawn implements Piece{
 
	@Override
	public boolean checkMoveValidity(Coordinates coord) {
		...
	}
 
	@Override
	public void performMove(Coordinates coord) {
		...
	}
 
	@Override
	public Piece computeIfKingCheck() {
		...
	}
 
}

And the same thing for all Piece subclasses.
Here is a diagram class that illustrates this design :

no-visitor-approach


This approach presents three important drawbacks :
– behaviors such as performMove() or computeIfKingCheck() will very probably use common logic.
For example whatever the concrete Piece, performMove() will finally set the current piece to a specific location and potentially takes the opponent piece.
Splitting related behaviors in multiple classes instead of gathering them defeats in a some way the single responsibility pattern. Making their maintainability harder.
– processing as checkMoveValidity() should not be something that the Piece subclasses may see or change.
It is check that goes beyond human or computer actions. This check is performed at each action requested by a player to ensure that the requested piece move is valid.
So we even don’t want to provide that in the Piece interface.
– In chess games challenging for bot developers, generally the application provides a standard API (Piece interfaces, subclasses, Board, common behaviors, etc…) and let developers enrich their bot strategy.
To be able to do that, we have to propose a model where data and behaviors are not coupled in the Piece implementations.

So let’s go to use the visitor pattern !

The participating structures of the pattern

We have two kinds of them :
– the model classes that accept to be visited (the pieces)
– the visitors that visit them (moving operations)

Here is a class diagram that illustrates the pattern :

chessWithNoBot1
In the upper part we have the visitors and in the lower part we have the model classes.

The double dispatch : the key of the visitor pattern

As explained, we don’t want to provide the moving behavior directly in Piece subclasses.
We want that each type of moving behavior be defined in a single class and that it handles every Piece subclass in a distinct method.
In a some way, the visitor pattern presents a similar approach as the anemic model where the model contains just data and let service classes perform the processing.
However we have a major difference : contrary to service classes, the visitor relies on a common interface to provide a extensible model.
Here is the PieceMovingVisitor interface (behavior specified for each kind of Piece) :

public interface PieceMovingVisitor {
 
	void visitPawn(Pawn pawn);
 
	void visitKing(King king);
 
	void visitQueen(Queen queen);
 
	void visitKnight(Knight knight);
 
	void visitRook(Rook rook);
 
	void visitBishop(Bishop bishop);
 
}

Now, the question is : How to pass a variable declared with the Piece interface to a Visitor subclasses method ?
For example, this will not work :

Piece piece = selectPiece();
PieceMovingVisitor pieceMovingVisitor = createVisitor();
// Which method invoke ?
pieceMovingVisitor.visit???

Even by changing the PieceMovingVisitor methods to use overloaded versions of a visit() method, we would have the same issue.

public interface PieceMovingVisitor {
 
	void visit(Pawn pawn);
 
	void visit(King king);
 
	void visit(Queen queen);
 
	void visit(Knight knight);
 
	void visit(Rook rook);
 
	void visit(Bishop bishop);
 
}

Piece piece = selectPiece();
PieceMovingVisitor pieceMovingVisitor = createVisitor();
pieceMovingVisitor.visit(piece); // will not compile

The last statement could not compile because a variable declared with Piece type cannot be passed to a method accepting subclasses of Piece.
Even if the variable is bound to be a Piece subclass at runtime, the Java compiler doesn’t matter as the method selection is done at compile time on the declared type of the argument, never the runtime type.
It is the single dispatch issue.
Go on. We will see how the model class can  bypass this limitation by performing a double dispatch. Here is the Piece interface (data but no behavior) :

public interface Piece {
 
	void accept(PieceMovingVisitor pieceVisitor);
 
	Coordinates getCoordinates();
 
	void setCoordinates(Coordinates coordinates);
 
}

Its key method is

void accept(PieceMovingVisitor pieceVisitor);

It provides the first dispatch : a invocation based on the Piece receiver.
At compile time, the method is bound to the accept() method of the Piece interface and at runtime, the bounded method will be invoked on the runtime Piece class.
And it is the accept() method implementation that will perform a second dispatch.

Indeed, each Piece subclass that wants to be visited by a PieceMovingVisitor object invokes the PieceMovingVisitor.visit() method by passing as argument itself.
In this way, the compiler bounds as soon as the compile time, the type of the declared parameter with the concrete type.
There is the second dispatch.
Here is the Bishop subclass that illustrates that (Note that AbstractPiece is just a base class that provides common implementation for any Piece subclasses) :

public class Bishop extends AbstractPiece {
 
	public Bishop(Game game, Coordinates coord) {
		super(game, coord);
	}
 
	@Override
	public void accept(PieceMovingVisitor pieceVisitor) {
		pieceVisitor.visitBishop(this);
	}
 
}

We could see that Queen uses a similar logic :

public class Queen  extends AbstractPiece {
 
	public Queen(Game game, Coordinates coord) {
		super(game, coord);
	}
 
	@Override
	public void accept(PieceMovingVisitor pieceVisitor) {
		pieceVisitor.visitQueen(this);
	}
 
}

In the accept() method, as we pass this as argument to the pieceVisitor variable, we use the context of the current class known at compile time to perform the binding of the parameter with the subclass
Implementations of a chess game processings are both long and complex. It is not our matter.
So we will use a skeleton  implementation for them.
Here is the MoveCheckingVisitor class :

public class MoveCheckingVisitor implements PieceMovingVisitor {
 
	private Coordinates targetCoordinates;
	private boolean isValid;
 
	public MoveCheckingVisitor(Coordinates targetCoordinates) {
		this.targetCoordinates = targetCoordinates;
	}
 
	@Override
	public void visitPawn(Pawn pawn) {
              ...
	}
 
	@Override
	public void visitKing(King king) {
              ...
	}
 
	@Override
	public void visitQueen(Queen queen) {
              ...
	}
 
	@Override
	public void visitKnight(Knight knight) {
              ...
	}
 
	@Override
	public void visitRook(Rook rook) {
              ...
	}
 
	@Override
	public void visitBishop(Bishop bishop) {
              ...
	}
 
 
	public boolean isValid() {
		return isValid;
	}
 
}

That is a more relevant part : the visitor input and output.
The visitor is not a stateless object.
Another difference with the service pattern.

Input information :
The visitor creation and the visitor use are always performed at distinct times.
During the creation, we may pass input parameters that provide contextual information to perform the operation.
The model passed as parameter in visit() is indeed not always enough to perform the task.
Providing the parameters in constructors instead of the visit() method provides a more flexible and extensible model : each subclass may define its own required input information.
We have an example here where the constructor accepts as argument the target coordinates for the Piece :

public MoveCheckingVisitor(Coordinates targetCoordinates) {
     this.targetCoordinates = targetCoordinates; 
}


Output information :
The visitor processing may create side effects on the model class that it visits.
But in some cases, it doesn’t create side effect.
Instead, it computes an information that clients class want to retrieve to take their decisions.
So in some cases, visitors must also define output information, generally these are private fields accessible via getters.
It is the case of MoveCheckingVisitor that provides the information whether the move is valid or not :
public boolean isValid() { return isValid; }
To be exhaustive, here is the AbstractPiece class :

public abstract class AbstractPiece implements Piece {
 
	private Game game;
	private Coordinates coordinates;
 
	public AbstractPiece(Game game, Coordinates initialCoordinates) {
		this.game = game;
		coordinates = initialCoordinates;
	}
 
	public Game getGame() {
		return game;
	}
 
	@Override
	public Coordinates getCoordinates() {
		return coordinates;
	}
 
	@Override
	public void setCoordinates(Coordinates coordinates) {
		this.coordinates = coordinates;
	}
 
}

The visitor pattern may reduce or break the encapsulation of domain objects

We previously saw that in some cases, it is desirable that the visitor conveys its result via public accessors.
In some other cases, using this way creates a helpless indirection as the visitor has all required information to provoke the side effect on the domain objects. It is the case for example for MovePerformingVisitor.
We expect that the visitor performs the task by moving the requested piece.
As the Visitor class needs to set the coordinates of the actual piece, the Piece interface has to provide a way to do that :

void setCoordinates(Coordinates coordinates);

The responsibility of Piece coordinates changes is now open to other classes than Piece subclasses.
Moving the processing performed by the visitor in the Piece subclasses is not an option either.
It will indeed create another issue as the Piece.accept() accepts any visitor implementation. It doesn’t know what the visitor performs and so no idea about whether and how to change the Piece state.
A way to identify the visitor would be to perform a post processing in Piece.accept() according to the visitor implementation. It would be a very bad idea as it would create a high coupling between Visitor implementations and Piece subclasses and besides it would probably require to use trick as getClass(), instanceof or any marker identifying the Visitor implementation.

Example of how to use the pattern

Here is a way to use the presented visitor pattern :

// 1. Player requests a move for a specific piece
Piece piece = selectPiece();
Coordinates coord = selectCoordinates();
 
// 2. We check with MoveCheckingVisitor that request is valid
final MoveCheckingVisitor moveCheckingVisitor = new MoveCheckingVisitor(coord);
piece.accept(moveCheckingVisitor);
 
// 3. If the move is valid, MovePerformingVisitor performs the move
if (moveCheckingVisitor.isValid()) {
     piece.accept(new MovePerformingVisitor(coord));
}

In step 1, we manipulate a Piece declared with the Piece interface.
In step 2, the accept() method of the Pawn class is invoked.
And thanks to the double dispatch (by passing this as argument to invoke the visitor method), the visitPawn() method invoked expects to have a Pawn class or subclass of it as parameter :

@Override
public void accept(PieceMovingVisitor pieceVisitor) {
	pieceVisitor.visitPawn(this);
}

So

MoveCheckingVisitor.visitPawn(Pawn pawn)

is bounded as soon as the compile time.

In step 3, we use the output of MoveCheckingVisitor to decide whether the Piece should be moved.
Note that MovePerformingVisitor doesn’t have any output as it is a always successful operation  and  it produces no result but what the client requested : a piece moving.

Go further with the visitor Pattern : implementing Bot move computations.

This part is interesting as it shows the extensibilty  provided by the visitor pattern.
In bot move computations, we will also see how the visitor allows to iterate on Pieces instances to apply specific behaviors without forcing the Piece interface to declare these specific behaviors.
TODO

Ce contenu a été publié dans Non classé. Vous pouvez le mettre en favoris avec ce permalien.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *