诊断 Java 代码: 深度优先访问器和中断的分派

设计模式最多只能对快速集中到一个项目的简单设计提供很大帮助。 但是，在一个特定环境中实现一种设计模式的最简单方法并不一定是显而易见的 ― 要做到这一点，有许多种方法。 这个月，我们将讨论应用公共设计模式来产生简单、简短且健壮的代码的一些方法。

首先，让我们看一下两种模式，它们适用于许多不同的环境。 在 设计模式（Erich Gamma 等，也称为“四从组（Gang of Four）”著， 它介绍了该主题的一些基础知识（请参阅 参考资料））中讨论的所有设计模式中，我发现可最广泛应用的是 Composite 和 Visitor 模式。

让我们进一步研究这两种模式。

用 Composite 指定递归数据类型

很容易就可以看出为什么 Composite 模式是有用的。Composite 模式只是指定递归定义的数据类型的面向对象方法；这些机会始终出现在软件开发中。

研究递归定义的对象类型的能力是软件工程的最显著的特征之一（与数字设计成对比，系统是从有限状态的机器构建的）。

回页首

用 Visitor 扩展类层次结构

至于 Visitor 模式，它受到如此广泛应用的许多原因是它补充了 Composite 模式。

Visitor 常常被吹捧为无需实际修改现有复合类层次结构中的类就可扩展其功能的一种方法。但是，它们的能力远远不仅于此。

因为访问器允许您将一个类层次结构的某些功能与类本身分开，所以可以在各式各样的设置中使用它们， 在这些设置中，从概念上很难将功能看作是那些类的固有部分。

这种现象常常出现在复合数据结构上的向下递归中。 例如，考虑二叉树的类层次结构和确定树中的任何节点是否包含一个零的访问器：

abstract class Tree {
  public abstract Boolean accept(TreeVisitor that);
}
class Leaf extends Tree {
  public static final Leaf ONLY = new Leaf();
  public Boolean accept(TreeVisitor that) {
    return that.forLeaf(this);
  }
}
class Branch extends Tree {
  public int value;
  public Tree left;
  public Tree right;
  public Branch(int _value, Tree _left, Tree _right) {
    this.value = _value;
    this.left = _left;
    this.right = _right;
  }
  public Boolean accept(TreeVisitor that) {
    return that.forBranch(this);
  }
}
interface TreeVisitor {
  public Boolean forLeaf(Leaf that);
  public Boolean forBranch(Branch that);
}
class ZeroFinder implements TreeVisitor {
  public Boolean forLeaf(Leaf that) {
    return new Boolean(false);
  }
  public Boolean forBranch(Branch that) {
    if (that.value == 0) { return new Boolean(true); }
    boolean foundInLeft = that.left.accept(this).booleanValue();
    boolean foundInRight = that.right.accept(this).booleanValue();
    return new Boolean(foundInLeft || foundInRight);
  }
}

通过在 for*() 方法（“*”表示通配符，如“Leaf”或“Branch”）中保留这个零查找功能，把 Tree 类本身分开，我们获得这些优势：

• 我们防止了这些类的代码膨胀。如果每次需要一个新功能时我们就将新的方法添加到类中，那么它们将很快变得很大。
• 我们将所有零查找功能放在一个地方，使之便于维护。

回页首

访问器的缺点

现在，如“四人组”所提到的那样，使用访问器的主要缺点是将新类添加到复合层次结构中变得有点困难。 也就是说，当不期望更改复合层次结构时，使用访问器是最佳的选择（虽然对于它还有一些方法可用，如“Extensible Visitor 模式”）。

然而，还有另一个大的缺点。当以同一种方法处理复合层次结构中的许多类时， 访问器中的代码将比放置在类本身中的代码大许多（因为我们可能只将一个缺省实现放入父类）。

幸好，普通访问器有一个变体，它不仅解决了这个问题， 而且在许多情况下可以让我们使代码比它在放入个别类时更加简单。我们将这个变体称为 Depth-First Visitor 模式。

回页首

Depth-first visitor 模式

Depth-First Visitor 模式的基本思想如下：大多数访问器都以深度优先的方式向下递归一个数据结构。 这意味着它们在访问给定的（非叶）节点本身之前，先访问它的子节点。

因此，我们可以在抽象 visitor 类的 for* 方法中实现深度优先遍历， 然后让具体实现简单地描述每种数据类型如何组合访问子节点的结果。这些描述放置在特殊的 for*Only() 方法中，这些方法将访问其子节点的结果作为方法的参数。

例如，清单 2 演示了如何重写二叉树上的深度优先访问器：

abstract class DepthFirstTreeVisitor implements TreeVisitor {
  public abstract Boolean forLeafOnly(Leaf that);
  public abstract Boolean forBranchOnly(Branch that,
                                        Boolean left_result,
                                        Boolean right_result);
  public Boolean forLeaf(Leaf that) {
    return forLeafOnly(that);
  }
  public Boolean forBranch(Branch that) {
    Boolean left_result = that.left.accept(this);
    Boolean right_result = that.right.accept(this);
    return forBranchOnly(that, left_result, right_result);
  }
}

现在，我们可以如清单 3 中所示的那样重写 ZeroFinder 访问器。

abstract class DepthFirstTreeVisitor implements TreeVisitor {
class DepthFirstZeroFinder extends DepthFirstTreeVisitor {
  public Boolean forLeafOnly(Leaf that) {
    return new Boolean(false);
  }
  public Boolean forBranchOnly(Branch that, 
                       Boolean left_result, 
                               Boolean right_result) 
  {
    if (that.value == 0) { return new Boolean(true); }
    return new Boolean(left_result.booleanValue() || 
                       right_result.booleanValue());
  }
}

这样，我们已经使许多深度优先遍历的复杂技术与具体的访问器分离， 并将这些复杂的技术放入（共享的）抽象父类。另外，对于每种类型，深度优先访问器的实现将有一个容易获得（在 for*Only() 方法的签名中）的包含了所有组件的列表。

回页首

复杂的层次结构如何？

这实际上相当于我们可以为这个简单的复合层次结构做些什么。 但是，对于更复杂的类层次结构，我们可以做更多的事情。

通常，对于许多类的复合层次结构，一个给定的访问器能以一个公共（或通用）方法来处理许多情况。 当访问器代替一对 instanceof 检查时，这尤为适用。对于这些情况， 我们可以提供 for*Only() 方法的缺省实现，这些方法只是调用一个抽象的 defaultCase() 方法：

abstract class DepthFirstTreeVisitor implements TreeVisitor {
  public abstract Boolean defaultCase(Tree that);
  public Boolean forLeafOnly(Leaf that) {
    return defaultCase(that);
  }
  public Boolean forBranchOnly(Branch that,
                               Boolean left_result,
                               Boolean right_result)
  {
    return defaultCase(that);
  }
  ...
}

现在，当在这样一个复合上实现深度优先访问器时，我们只需要为那些缺省情况下不处理的情况指定代码。

当复合层次结构的深度大于一层时，我们还可能需要为该层次结构的每个子树提供单独的缺省方法。 可以将这些缺省方法定义成简单地调用父类的缺省方法。但在必要时，可以覆盖它们。

一旦完成了这些操作，我们就获得了使功能包括在复合类中的简洁性，同时保留了普通访问器的所有优点。

回页首

当然，也有警告

对于大多数向下深度优先的访问器，我们仍可以使用深度优先访问器。只要覆盖那些我们不想遍历深度优先的 for*() 方法（与 for*Only() 方法相对）。

然而，这种方法也有一个警告：很容易遇到 中断的分派。还记得它们吗？当我们意外重载一个方法而不是覆盖父类中的它的实现时，会发生 Broken Dispatch 错误模式。 通过深度优先访问器，特别容易发生这种情况。

假设我们想要覆盖父类的一个 for*() （而不是 for*Only() ）方法之一。 这个 for*() 方法说明将采用它所操作的节点，但和 for*Only() 方法不同，它不接受访问子节点的结果。现在， 因为我们正在编写 for*() 和 for*Only() 方法， 所以不难想象我们会遗漏且意外地将 for*Only() 写成一个 for*() 方法的名称。

如果我们这样做了，代码将正常编译，但我们将无法覆盖 for*() 方法。 相反，我们可用不同说明的新方法使 for*Only() 方法重载。

另外，永远不要调用这个新的 for*Only() 方法。类似这样的中断分派可能是隐藏特别深的错误， 需要深入跟踪 — 类型检查器捕捉不到它们并且您决不知道它们何时或者是否真正发出了一个错误信号。 在最坏的情况下，中断的分派将只以这样一种方式（其结果看似十分合理，但实际上是绝对错误的）修改程序的行为。

关于防止这些问题，我只能说它们是最好的示例，说明了为什么在编写代码之前（或同时）编写单元测试会节省时间， 以及为什么应该经常运行那些测试！

因此，您就知道了为什么深度优先访问器很酷以及它们会怎样刺痛您。 我要感谢我们研究实验室的研究生 Brian Stoler，他首先向我介绍了这种模式。深度优先访问器是通过“Java 树构建器（Java Tree Builder）”构造的， 它是一种可以从 参考资料中免费获得的工具，用于根据 JavaCC 语法自动生成一个复合的层次结构（加上访问器）。