Visitor模式及其实现方式优劣比较

Visitor模式的使用情景以及与Iterator的比较见我以前的一篇文章
http://fuliang.iteye.com/blog/166142
这次主要讨论Visitor的两种实现方式及其优劣。
主要实现方式主要有两种：
方法一、节点类的accept方法负责遍历逻辑，visitor只负责访问的操作。
方法二、节点类负责调用visit自己，而visitor除了负责访问该节点外还accept子节点，也就是遍历逻辑。
第一种看起来很优美，因为它将访问操作和节点遍历分离开来，职责清晰，并且节点本身知道如何去遍历
子节点，事实上这也是GOF设计模式一书例子中使用的方法。缺点是遍历逻辑在节点中写死了，也就是说
如果我在节点中定义了一种遍历顺序，如果Visitor试图使用其他的遍历顺序变得不可能，另外如果我想在
遍历之前做一些事情，遍历之后做些事情也同时变得不可能，除非每个visit方法提供了提供previousVisit
和postVisit进行回调，然而这显然增加了api的复杂性。
第二种方法，很容易看到缺点，他混淆了访问和遍历的职责，这与单一职责原则相悖，后面会讨论如何避免这个缺点。但是它非常的灵活，
可以避免第一方法带来的缺点。
下面举一个简单的例子（这个例子来自于实际项目的一个精简）来说明一下上述两种实现方式，以及面临的问题，
我们先定义一个定义的节点类型，其定义了一种树形结构：
所有节点类要实现的接口，包含了accept方法。

package edu.jlu.fuliang.model;

import edu.jlu.fuliang.visitor.IVisitor;

public interface IModel {
	void accept(IVisitor visitor);
}

我们看看第一种方法实现visitor模式的代码：

package edu.jlu.fuliang.model;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import edu.jlu.fuliang.visitor.IVisitor;

public class JavaProject implements IModel {
	private String javaProjectName;
	private List<JavaPackage> javaPackages;

	public JavaProject() {
		javaPackages = new ArrayList<JavaPackage>();
	}

	public void addPackage(JavaPackage pkg) {
		javaPackages.add(pkg);
	}

	public List<JavaPackage> getJavaPackages() {
		return Collections.unmodifiableList(javaPackages);
	}

	public String getJavaProjectName() {
		return javaProjectName;
	}

	public void setJavaProjectName(String javaProjectName) {
		this.javaProjectName = javaProjectName;
	}

	@Override
	public void accept(IVisitor visitor) {
		visitor.visitProject(this);
                for (JavaPackage javaPackage : javaPackages) {
			javaPackage.accept(visitor);
		}
	}

}

package edu.jlu.fuliang.model;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import edu.jlu.fuliang.visitor.IVisitor;

public class JavaPackage implements IModel {
	private String packageName;
	private List<JavaClass> javaClasses;

	
	public JavaPackage() {
		javaClasses = new ArrayList<JavaClass>();
	}

	@Override
	public void accept(IVisitor visitor) {
		visitor.visitPackage(this);
		for (JavaClass javaClass : javaClasses) {
			javaClass.accept(visitor);
		}
	}

	public String getPackageName() {
		return packageName;
	}

	public void setPackageName(String packageName) {
		this.packageName = packageName;
	}

	public List<JavaClass> getJavaClasses() {
		return Collections.unmodifiableList(javaClasses);
	}
	
	public void addJavaClass(JavaClass javaClass){
		javaClasses.add(javaClass);
	}
	
}

package edu.jlu.fuliang.model;

import edu.jlu.fuliang.visitor.IVisitor;

public class JavaClass implements IModel{
	private String className;
	
	
	public JavaClass() {
	}

	public String getClassName() {
		return className;
	}


	public void setClassName(String className) {
		this.className = className;
	}


	@Override
	public void accept(IVisitor visitor) {
		visitor.visitClass(this);
	}
}

好了节点定义好了那么以及遍历逻辑我们都写好了。
现在我们来写Visitor:

package edu.jlu.fuliang.visitor;

import edu.jlu.fuliang.model.JavaClass;
import edu.jlu.fuliang.model.JavaPackage;
import edu.jlu.fuliang.model.JavaProject;


public interface IVisitor {
	public void visitProject(JavaProject project);
	public void visitPackage(JavaPackage pkg);
	public void visitClass(JavaClass klass);
}

一个简单的Visitor：PrintVistor,我们想打印一些Java整个工程的信息：工程名，
下面有哪些包，以及包里面有哪些类。

package edu.jlu.fuliang.visitor;

import edu.jlu.fuliang.model.JavaClass;
import edu.jlu.fuliang.model.JavaPackage;
import edu.jlu.fuliang.model.JavaProject;

public class PrintVistor implements IVisitor{

	@Override
	public void visitClass(JavaClass klass) {
		System.out.println(klass.getClassName());
	}

	@Override
	public void visitPackage(JavaPackage pkg) {
		System.out.println(pkg.getPackageName());
	}

	@Override
	public void visitProject(JavaProject project) {
		System.out.println(project.getJavaProjectName());
	}
}

一切看起来很好，但是需求来了，打印出来的信息太ugly了，我们希望一种看起来格式很Pretty的信息：类似于IDE的那种
带缩进的有层次感的组织方式。
那我们如何实现这个PrettyPrintVisitor呢，我们似乎失去了时机：我们应该在访问子节点之前做点事情，在访问子节点
之后做点事情，才能满足我们的需求，当然这些事情每一个visit方法不一定做相同的事情。而现在的visitor只能对自己
做一些事情，可以增加previousVisitXx和postVisitXx之类的方法，但是这样许多像PrintVisitor那样的访问者根不不需要
在previousVisitXx和postVisitXx做事情，所以导致大量的空方法出现，代码非常的ugly.当然可以写一个VisitorAdpater
空实现所有的方法来避免，但这样复杂性增加，似乎并不是一件美好的事情。如果这样勉强可以实现的话，那么下面的需求
将导致第一种方式实现的Visitor无法完成：我们想以一种后序遍历的顺序来打印结果，那么这个将无法完成，事实上这样
的需求不是没有，例如语法树的打印可能是先序遍历，而中间代码的生成可能需要一种后序遍历的方式来分析。
这个致命的缺点是节点类硬编码的遍历的顺序，导致访问者只能按照既定的顺序来访问。
下面我们看看第二种方法实现PrettyPrintVisitor吧：
首先把遍历逻辑都从节点中转移到Visitor类中，然后加上我们的缩进功能：

package edu.jlu.fuliang.visitor;

import java.util.List;

import edu.jlu.fuliang.model.JavaClass;
import edu.jlu.fuliang.model.JavaPackage;
import edu.jlu.fuliang.model.JavaProject;

public class PrettyPrintVisitor implements IVisitor{

    private Spacing spacing = new Spacing(3);
	@Override
	public void visitClass(JavaClass klass) {
		System.out.print(spacing);
		spacing.updateSpc(1);
		System.out.println(klass.getClassName());
		spacing.updateSpc(-1);
	}

	@Override
	public void visitPackage(JavaPackage pkg) {
		System.out.print(spacing);
		System.out.println(pkg.getPackageName());
		spacing.updateSpc(1);
		List<JavaClass> javaClasses = pkg.getJavaClasses();
		for (JavaClass javaClass : javaClasses) {
			javaClass.accept(this);
		}
		spacing.updateSpc(-1);
	}

	@Override
	public void visitProject(JavaProject project) {
		System.out.print(project.getJavaProjectName());
		spacing.updateSpc(1);
		List<JavaPackage> javaPackages = project.getJavaPackages();
		for (JavaPackage javaPackage : javaPackages) {
			javaPackage.accept(this);
		}
		spacing.updateSpc(-1);
	}
}

一个辅助类：

package edu.jlu.fuliang.visitor;

public class Spacing {
	public final int INDENT_AMT;// 缩进的字数

	public String spc = " ";
	public String brunch = "|---->";
	public int indentLevel;// 缩紧的层次

	public Spacing(int indentAmount) {
		INDENT_AMT = indentAmount;
	}

	public String toString() {
		return spc;
	}

	public void updateSpc(int numIndentLvls) {
		if (spc.length() >= brunch.length())
			spc = spc.substring(0, spc.length() - brunch.length());

		indentLevel += numIndentLvls;
		if (numIndentLvls < 0) {
			spc = spc.substring(0, indentLevel * INDENT_AMT);
			spc += brunch;
		} else if (numIndentLvls > 0) {
			StringBuffer buf = new StringBuffer(spc);
			for (int i = 0; i < numIndentLvls * INDENT_AMT; ++i)
				buf.append(" ");
			buf.append(brunch);
			spc = buf.toString();
		}
	}
}

一种常用弥补第二种方法缺点的方法是定义好PreOrderDFS父类和PostOrderDFSVisitor父类，这些类来负责访问逻辑，子类只需要super.visitXxx即可

package edu.jlu.fuliang.visitor;

import java.util.List;

import edu.jlu.fuliang.model.JavaClass;
import edu.jlu.fuliang.model.JavaPackage;
import edu.jlu.fuliang.model.JavaProject;

public class PreOrderDFSVisitor implements IVisitor{

	@Override
	public void visitClass(JavaClass klass) {
		
	}

	@Override
	public void visitPackage(JavaPackage pkg) {
		List<JavaClass> javaClasses = pkg.getJavaClasses();
		for (JavaClass javaClass : javaClasses) {
			javaClass.accept(this);
		}
	}

	@Override
	public void visitProject(JavaProject project) {
		List<JavaPackage> javaPackages = project.getJavaPackages();
		for (JavaPackage javaPackage : javaPackages) {
			javaPackage.accept(this);
		}
	}
}

这样PrettyPrintVisitor 可以这么实现了：

package edu.jlu.fuliang.visitor;

import java.util.List;

import edu.jlu.fuliang.model.JavaClass;
import edu.jlu.fuliang.model.JavaPackage;
import edu.jlu.fuliang.model.JavaProject;

public class PrettyPrintVisitor extends PreOrderDFSVisitor{

    private Spacing spacing = new Spacing(3);
	@Override
	public void visitClass(JavaClass klass) {
		System.out.print(spacing);
		spacing.updateSpc(1);
		System.out.println(klass.getClassName());
                super.visitClass(klass);
		spacing.updateSpc(-1);
	}

	@Override
	public void visitPackage(JavaPackage pkg) {
		System.out.print(spacing);
		System.out.println(pkg.getPackageName());
		spacing.updateSpc(1);
		super.visitPackage(pkg);
		spacing.updateSpc(-1);
	}

	@Override
	public void visitProject(JavaProject project) {
		System.out.print(project.getJavaProjectName());
		spacing.updateSpc(1);
		super.visitProject(project);
		spacing.updateSpc(-1);
	}
}

结论：
显然第一种很符合面向对象的思想，如果在实际应用中你只需要一种遍历顺序，在访问的时候只对当前节点做操作，那么第一种实现可以优雅的满足你的需要。
第二种方法经过我们定义PreOrderDFS和PostOrderDFSVisitor，把遍历逻辑放在父类中，子类只需要负责访问的逻辑即可，既达到了灵活性，又实现了遍历和访问的分离，可以满足各种复杂的需求和扩展性。

楼主对这两种方案有什么总结性的结论不？貌似是比较倾向于第二种？

Visitor模式原本确实是很有“导航逻辑”与“业务逻辑”分离的作用。从这个角度看第二种就怪怪的，比较乱。
以前我在我的一个编译器的AST里也用到了Visitor模式。没有专门定义接口，而是直接以抽象类为继承层次的根（不算Object）。这个基类是用脚本来生成的，从源码中AST所在的目录抽取出所有concrete的AST类名，并为它们生成boolean visitXXX(XXX x)与void postVisitXXX(XXX x)这两个方法，其中前者的默认实现为return true;，后者的默认实现为空。visitXXX返回的值是用来判断是否要继续向深处遍历用的，所以一个accept的基本实现像这样：（以上面的JavaProject类为例）

@Override
public void accept(Visitor v) {
    if (v.visitJavaProject(this)) {
        for (JavaPackage p : javaPackages) {
            p.accept(v);
        }
    }
    v.postVisitJavaProject(this);
}

每次我build之前都会让脚本检查一下我的AST类的继承层次里有没有变化，有的话就重新生成基类，以此来保持源码的稳定，避免手动更新的麻烦。楼主说得没错，如果这部分全部都是手写的话非常痛苦也难以维护。但即便如此我还是不太倾向第二种方法。

话说回来，这也只是single-dispatch的语言才有的问题。如果有multimethod这根本就不是问题：不需要Visitor模式实现double-dispatch，所以也就不需要面对选择Visitor模式的实现方式的问题。

刚刚补充了结论。