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

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;}@Overridepublic 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>();}@Overridepublic 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;}@Overridepublic 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{@Overridepublic void visitClass(JavaClass klass) {System.out.println(klass.getClassName());}@Overridepublic void visitPackage(JavaPackage pkg) {System.out.println(pkg.getPackageName());}@Overridepublic 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);@Overridepublic void visitClass(JavaClass klass) {System.out.print(spacing);spacing.updateSpc(1);System.out.println(klass.getClassName());spacing.updateSpc(-1);}@Overridepublic 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);}@Overridepublic 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{@Overridepublic void visitClass(JavaClass klass) {}@Overridepublic void visitPackage(JavaPackage pkg) {List<JavaClass> javaClasses = pkg.getJavaClasses();for (JavaClass javaClass : javaClasses) {javaClass.accept(this);}}@Overridepublic 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);@Overridepublic void visitClass(JavaClass klass) {System.out.print(spacing);spacing.updateSpc(1);System.out.println(klass.getClassName());                super.visitClass(klass);spacing.updateSpc(-1);}@Overridepublic void visitPackage(JavaPackage pkg) {System.out.print(spacing);System.out.println(pkg.getPackageName());spacing.updateSpc(1);super.visitPackage(pkg);spacing.updateSpc(-1);}@Overridepublic void visitProject(JavaProject project) {System.out.print(project.getJavaProjectName());spacing.updateSpc(1);super.visitProject(project);spacing.updateSpc(-1);}}

结论：
显然第一种很符合面向对象的思想，如果在实际应用中你只需要一种遍历顺序，在访问的时候只对当前节点做操作，那么第一种实现可以优雅的满足你的需要。
第二种方法经过我们定义PreOrderDFS和PostOrderDFSVisitor，把遍历逻辑放在父类中，子类只需要负责访问的逻辑即可，既达到了灵活性，又实现了遍历和访问的分离，可以满足各种复杂的需求和扩展性。
@Overridepublic 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模式的实现方式的问题。 2 楼 fuliang 2009-05-24   RednaxelaFX 写道楼主对这两种方案有什么总结性的结论不？貌似是比较倾向于第二种？
刚刚补充了结论。

查看更多 下一篇