Double Descent 错误模式
内容:
不要强制转换这个类!
Double Descent 错误模式
症状
起因
治疗和预防措施
总结
参考资料
关于作者
对本文的评价
在开始时击败递归类强制转换概念性错误 Eric E. Allen (eallen@cyc.com)
软件工程师,Cycorp, Inc.
2001 年 4 月
类型转换错误信息通常表明在递归下行一个复合数据结构时出现概念性错误,虽然它通常比其它错误更易调试,但也具有更多隐蔽的错误行为。在诊断 Java 代码的这一部分,Eric Allen 讨论了程序员应该到哪里去查找这种错误模式、如何识别该模式以及应该做什么工作来使这种错误的发生次数降到最少。
不要强制转换这个类!
与可怕的空指针异常(该异常除了报告空指针之外,对于将要发生的事情什么也不说)不同,类强制转换异常相对来说轻易调试。
类强制转换经常发生在递归下行数据结构的程序中,通常是当代码的某些部分在每次方法调用中下行了两级且在第二次下行时调度不当时发生的。程序员可通过学习 Double Descent 错误模式来识别这种问题。
快速跟踪代码
清单 1. int 二元树的类层次结构
我们讨论的起点。
清单 2. 确定两个连贯的节点是否都包含 0 的方法
我已经添加了一些方法来确定两个连贯的节点是否都包含 0,但类 Branch 方法将不编译。
清单 3. 在适当的 if 语句中将 this.left 和 this.right 强制转换为 Branch
看看在强制转换为 Branch 时会发生什么情况。
清单 4. 一种修正方法:将每个类型强制转换都包在 instanceof 检查语句中
修正这个问题的一种方法。
清单 5. 使用 valueIs 来代替 instanceof
修正这个问题的一种更好的方法。
Double Descent 错误模式
本周的专题是 Double Descent 错误模式。它通过类强制转换异常来表明。它是由递归下行复合数据结构引起的,这种下行方式有时在一次递归调用中要下行多级。这样做经常需要添加类型强制转换来编译代码。但是,在这种下行中,很轻易忘记检查是否满足了适当的不变量来保证这些类型强制转换成功。
考虑以下的 int 二元树的类层次结构。因为我们希望考虑到空树的情况,所以将不把 value 字段放入 Leaf 类中。由于这一决定使所有的 Leaf 相同,我们将用一个静态字段为 Leaf 保留一个单元素。
清单 1. int 二元树的类层次结构
abstract class Tree {
}
class Leaf extends Tree {
public static final Leaf ONLY = new Leaf();
}
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;
}
}
现在,假定我们希望在 Tree 上添加一个方法,该方法确定任意两个连贯的节点(比如一个分支和它的其中一个子分支)是否都包含一个 0 作为它们的值。我们可能添加以下方法(注重:最后一个方法将不以它的当前形式编译):
清单 2. 确定两个连贯的节点是否都包含值 0 的方法 // in class Tree:
public abstract boolean hasConsecutiveZeros();
// in class Leaf:
public boolean hasConsecutiveZeros() {
return false;
}
// in class Branch:
public boolean hasConsecutiveZeros() {
boolean foundOnLeft = false;
boolean foundOnRight = false;
if (this.value == 0) {
foundOnLeft = this.left.value == 0;
foundOnRight = this.right.value == 0;
}
if (foundOnLeft foundOnRight) {
return true;
}
else {
foundOnLeft = this.left.hasConsecutiveZeros();
foundOnRight = this.right.hasConsecutiveZeros();
return foundOnLeft foundOnRight;
}
}
类 Branch 中的方法将不编译,因为 this.left 和 this.right 不保证具有 value 字段。
我们无法编译强烈地表明我们对这些数据结构所进行的操作中有逻辑错误。但是假设我们忽略此警告,只是仅仅在适当的 if 语句中将 this.left 和 this.right 强制转换为 Branch,如下所示:
清单 3. 在适当的 if 语句中将 this.left 和 this.right 强制转换为 Branch
public boolean hasConsecutiveZeros() {
boolean foundOnLeft = false;
boolean foundOnRight = false;
if (this.value == 0) {
foundOnLeft = ((Branch)this.left).value == 0;
foundOnRight = ((Branch)this.right).value == 0;
}
if (foundOnLeft foundOnRight) {
return true;
}
else {
foundOnLeft = this.left.hasConsecutiveZeros();
foundOnRight = this.right.hasConsecutiveZeros();
return foundOnLeft foundOnRight;
}
}
症状
现在代码将会编译。实际上,在许多测试事例中它都会成功。但是假设我们要在图 1 所示的树上运行这段代码,其中树的分支都用圆形表示,值在中心,叶子用正方形表示。调用这棵树上的 hasConsecutiveZeros 将导致类强制转换异常。
图 1. 在这棵树上,调用 hasConsecutiveZeros 导致类强制转换异常
起因
问题发生在左分支上。因为该分支的值为 0,hasConsecutiveZeros 将其子分支强制转换为 Branch 类型,当然,转换失败。
治疗和预防措施
修正上述问题的方法与预防这种问题的方法相同。但是,在讨论这个修正方法之前,我先讨论一种 不修正的方法。
一种快速但不正确的解决这个问题的方法是除去 Leaf 类并通过简单地将空指针放在 Branch 的 left 和 right 字段中来表示 Leaf 节点。这种方法可除去上面代码中类型强制转换的需要,但不修正错误。
相反,在运行时发出的错误将会是一个空指针异常而不是类强制转换异常。因为空指针异常更难诊断,这种“修正”实际上会降低代码的质量。关于这个问题的更多讨论,请参阅我的文章空标志错误模式。
那么,我们如何修正这个错误呢?一种方法是将每个类型强制转换都包在 instanceof 检查语句中。
清单 4. 一种修正方法:将每个类型强制转换都包在 instanceof 检查语句中
if (! (this.left instanceof Leaf)) {
// this.left instanceof Branch
foundOnLeft = ((Branch)this.left).value == 0;
}
if (! (this.right instanceof Leaf)) {
// this.right instanceof Branch
foundOnRight = ((Branch)this.right).value == 0;
}
顺便注重一下断定每个 if 语句正文中希望保留的不变量的注释。在代码中添加类似的注释是个好习惯。这种习惯对于 else 子句尤其有用。因为我们很少对 else 子句中希望保留的不变量进行显式检查,所以在代码中清楚说明该不变量是一个不错的主意。
把类型强制转换当作一种断言,把不变量当做说明该断言为 true 的原因的参数。
以这种方式使用 instanceof 检查语句的一个缺点是,假如我们要添加 Tree 的另一个子类(比如一个 LeafWithValue 类),我们将不得不修改这些 instanceof 检查语句。由于这个原因,只要可能我都会设法避开 instanceof 检查语句。
相反,我向为每个子类执行适当的操作的子类添加额外的方法。究竟,添加这种多态方法的能力是面向对象语言的要害优势之一。
在目前的示例中,我们可以通过向 Tree 类中添加 valueIs 方法来完成这个操作,如下所示:
清单 5. 使用 valueIs 代替 instanceof
// in class Tree:
public abstract boolean valueIs(int n);
// in class Leaf:
public boolean valueIs(int n) { return false; }
// in class Branch:
public boolean valueIs(int n) {
return value == n;
}
// in class Branch, method hasConsecutiveZeros
if (this.valueIs(0)) {
foundOnLeft = this.left.valueIs(0);
foundOnRight = this.right.valueIs(0);
}
注重:我已经添加了 valueIs 方法来代替 getValue 方法。假如我们已经向 Leaf 类添加了 getValue 方法,我们要么是不得不返回一些类型的标志值表明此方法应用是无意义的,要么是实际抛出一个异常。
返回一个标志值将引起许多与我们上次讨论的空标志错误模式一样的错误。抛出一个异常在本例中帮不了什么忙,因为我们将不得不在 hasConsecutiveZeros 中添加 instanceof 检查语句以确保我们没有触发异常。而这正是在新方法中我们要设法避免的。
valueIs 通过封装我们真正希望每个类单独处理的内容:检查类的一个实例是否包含给定的值,以避开所有这些问题。
总结
下面是本周的错误模式的小结:
模式:Double Descent
症状:在数据结构上执行递归下行时抛出类强制转换异常。
起因:代码的某些部分在每次方法调用中下行了两级且第二次下行时调度不当。
治疗和预防措施:把类型强制转换代码分解到每个类的单独方法中去。还有一种选择是,检查不变量以确保类型强制转换将会成功。
简言之,这些方法的本质总是使您确信代码块内部的不变量会确保代码块中的任何类型强制转换都将成功。当对每个类型强制转换进行这种级别的具体审查时,您可能会发现通过向相关的子类添加方法,您将许多这些类型强制转换分解了。
在下一篇文章中,我将讨论与错误处理复杂的输入数据相关的错误模式。
参考资料
Set-based 分析是一个方法,它可在程序运行之前自动确定许多类强制转换异常发生的可能性。The Carnegie Mellon School of Computer Science 的 Web 站点提供了这种方法的简短介绍以及关于这个主题的几本技术出版物的链接。
请访问模式主页,它提供关于设计模式以及如何使用这些模式的很好的介绍。
请查阅 JUnit,并通过编写“布满测试”的代码来捕捉更多的错误。
请阅读 Eric 的关于错误模式的完整系列:
“错误模式:介绍”
“Dangling Composite 错误模式”
“空标志错误模式”
Neel V. Kumar 在文章“Multi-threading in Java programs”中提供了调试多 Java 线程的方法。
关于在开发过程中向 Java 程序添加跟踪方法的循序渐进的介绍,请参阅 Andrei Malacinski 的“Techniques for adding trace statements to your Java application”。
关于调试 AIX C 或 C++ 代码(供 Java 程序调用)的论文,请查阅“Debugging Java Native Interface (JNI) code with DBX on AIX”。
David Wendt 在他的文章“Implementing Java native methods in Windows”中说明了如何调试在 Windows 环境下实现的 Java 语言本机方法。
关于作者
Eric Allen 在 Cornell 大学获得计算机科学和数学的学士学位。他目前是 Cycorp 公司的 Java 软件开发人员带头人,还是 Rice 大学的编程语言小组的兼职硕士生。他的研究涉及正规语义模型和 Java 语言的扩展,都是在源代码和字节代码的级别上的。目前,他正在为 NextGen 编程语言实现一种从源代码到字节代码的编译器,这也是 Java 语言的泛型运行时类型的一种扩展。可通过 eallen@cyc.com 与 Eric 联系。