14.1. 观察效果：二叉搜索树范围查询¶

学生常见的一个误解是，可以通过构造一个执行该分支的测试用例来获得分支的变异覆盖率。事实上，要获得分支的变异测试覆盖率，需要满足两个要求。

1. 执行分支。

2. 该分支的执行是否影响某些测试的结果。

也就是说，为了获得覆盖率积分，该分支必须通过测试用例影响某个断言——通常是通过改变某个方法的返回值（该值正被断言），或者通过打印正在被检查的输出。

示例：考虑在二叉搜索树（BST）上执行范围查询，目标是访问最少数量的节点。这意味着添加两个检查来限制哪些子节点将被访问：

1. 仅当当前节点的值小于范围最大值时，才访问右子树。

2. 仅当当前节点的值大于或等于范围最小值时，才访问左子树。

学生可能会仔细构造测试用例，使其在所有这些情况下都能正确避免访问子节点——也就是说，这些测试用例共同执行了所有分支。如果要求是在范围内打印节点值，那么该输出可能是完全正确的。然而，这些内容都不会为这些分支的变异覆盖率加分。原因是，不必要地访问子节点本身通常不会改变搜索过程中是否能找到正确值。结果（找到并返回的内容）无论代码是否正确最小化了访问的节点数量都是一样的。因此，任何决定限制访问节点数量的操作都不会影响结果。因此，其行为变异不会影响测试结果，所以该变异未被覆盖。

从限制不必要的访问的代码中得出的唯一可能差异将以某种形式的节点访问数量统计出现。因此，为了获得覆盖这些分支的分数，测试必须实际检查优化的结果，而不是搜索的结果。这意味着要检查类似节点访问数量这样的内容，要么让搜索过程返回该计数（并通过断言验证正确的值），要么检查打印出的正确节点计数。但这通常需要在代码中构建一个用于收集该节点计数的收集器，并报告其值。

注意，这是一个尝试优化性能的示例，其中实际计算的结果并未因优化而改变。这是一种常见情况。

14.2. 约束过度的代码：访问象限¶

您可能遇到一种情况，无论您如何努力，您的单元测试都无法覆盖代码的所有分支，但这并不是上述所描述的优化示例。在这种情况下，您应该检查是否编写了过度约束的代码，即一个分支的执行会“隐藏”或使得另一个分支的执行成为不可能。

考虑两个点的比较示例。这里，较小的 Y 值在较大的 Y 值的北方，较小的 X 值在较大的 X 值的西方。您想知道第二个点 (x2, y2) 相对于第一个点 (x1, y1) 位于哪个象限：西北、东北、西南还是东南。

public static String getQuadrant(int x1, int y1, int x2, int y2) {
    if ((x2 < x1) && (y2 < y1))
        return "North-West";
    else if ((x2 < x1) && (y2 >= y1))
        return "South-West";
    else if ((x2 >= x1) && (y2 < y1))
        return "North-East";
    else if ((x2 >= x1) && (y2 >= y1))
        return "South-East";
    return null; // This should never happen
}

这具有逻辑清晰这一优点。然而，它也存在一些问题。一方面，与替代方案相比，它的效率相对较低，需要更多的算术比较测试。但我们要关注的主要问题是测试覆盖率和变异覆盖。

事实： 没有任何测试序列能够覆盖此代码中的所有分支。

你可以尝试自己验证这一点，只需仔细考虑代码的逻辑。注意，共有 4 种可能的结果（每个测试点必须位于四个象限之一），但至少有 8 个分支需要测试（因为有 8 个比较操作）。你能想到触发这八个分支的测试用例吗？由于只有四种可能的输入，这是不可能的。

仔细查看这一点，我们可以编写测试用例来正确检查第一个 if 语句的所有分支。例如，如果测试针对位于西北方向的点，则将任一测试设置为 false 将（正确）导致测试失败。

但考虑一下当我们到达第二个 if 语句时会发生什么。问自己这个问题：我们为什么在这里？原因是我们已经（已经！）失败了第一个 if 测试。这意味着我们位于第二个 if 语句这一事实存在先决条件。具体而言，我们知道我们不能有一个点同时具有小 x2 和小 y2 ，否则我们就不会在这里。所以，考虑一下当我们修改第二个 if 语句中的比较时会发生什么。特别是，当 y 值的比较被修改为 true 时会发生什么？那么，一个位于西北的点会错误地被返回为西南，并且测试会（正确地）失败。但是不幸的是，这种情况已经被第一个 if 语句捕获，并且所有其他点位置的行为都符合预期。因此，没有任何输入实际上能触发错误并导致测试失败。

注意，这不是变异测试与代码覆盖率之间的问题。问题不仅在于分支无法检查出正确答案，甚至无法执行。因此，代码覆盖率也不会计算该分支。

由于我们需要针对四种可能的输入实现完全的变异覆盖率，因此我们必须编写出仅包含四个分支的代码。例如，重构后的代码可能看起来像这样：

public static String getQuadrant2(int x1, int y1, int x2, int y2) {
    if (x2 < x1) {
        if (y2 < y1)
            return "North-West";
        return "South-West";
    }
    if (y2 < y1)
        return "North-East";
    return "South-East";
}

经过重构的代码，不仅可以测试每个分支，而且效率更高。此处，每个分支需要两次布尔比较。（相比之下，如果原始代码需要遍历所有 if 语句，则需要进行八次布尔比较。）

编写过于复杂的代码是许多程序员常见的问题。这是突变测试如何帮助您提高代码质量和效率的一个例子，通过提醒您注意过度受限的代码块。

14.3. 约束过度的代码：从二叉搜索树中删除¶

考虑一种允许重复键值（但记录本身不同）的 BST 实现。例如，BST 可能存储关于某个城市的记录，该记录包含城市名称（BST 键值）和位置（对 BST 而言只是随记录携带的信息）。这为删除操作创造了一个重要的区别：如果要删除一条记录，必须删除正确的记录，而不仅仅是任何恰好匹配该城市名称的记录。

这里是一个相当典型的实现删除操作的方法。注意，在此上下文中，可以保证该方法只有在确认该记录已在树中时才被调用。（也许调用方会在实际调用删除操作之前先测试该记录是否存在。）因此，子树为空的常见“安全检查”（这仅发生在记录不在树中时）实际上无法在系统级别进行测试。（它可能可以通过特定类的单元测试来测试。）

// Return the subtree rooted by rt that has rec removed from it
Node removehelp(Node rt, Record rec) {
  // if (rt == null) { return null; } NOT TESTABLE IF WE KNOW THE RECORD IS THERE
  if (rt.value() > rec) {
    rt.setleft(removehelp(rt.left(), key));
  }
  else if (rt.value() < rec) {
    rt.setright(removehelp(rt.right(), key));
  }
  else if (!rt.value().equals(rec)) { // The names match, but it might not be the correct record
    rt.setleft(removehelp(rt.left(), key)); // Equal valued keys go left in our implementation
  }
  else {
    // FOUND IT: Replace this node with an appropriate substitute
    ...
  }

这看起来逻辑上已经足够合理。我们处理键值较大的情况、键值较小的情况，并且在名称相等但记录不相等时有一个特殊情况。否则，我们已经找到了记录并对其进行处理。四种情况，四个分支。不幸的是，我们将发现无法测试此代码的所有分支。这类事情会让程序员发疯，因为他们坚信自己的测试“覆盖”了所有情况（因为他们确实执行了所有分支！），但他们所做的任何事都无法获得完整的变异覆盖率。一个预示即将出现问题的红色信号是，我们有四个分支，但实际上只有三种结果（注意，虽然两个条件似乎代表不同的逻辑情况，但事实是代码对这两个条件都向左执行）。

是什么导致了问题？考虑 MT 的工作原理：对于四个比较中的每一个，它首先将表达式替换为 TRUE 并运行所有测试，然后将其替换为 FALSE 并运行所有测试。对于每个变异，必须有一些测试用例失败才能获得覆盖该变异的信用。

考虑第一个测试用例的情况，其中小键值应该向左走。如果 MT 将此测试设置为 TRUE（即方法总是向左走），那么它最终会失败，这正是我们想要的。但是，如果 MT 将此测试始终设置为 FALSE 呢？那么我们将到达第三个测试用例，当然，当键值较小时，这个测试用例确实为 TRUE（因为它不匹配搜索记录）。因此，我们会向左走……这正是我们原本应该做的。因此，没有测试用例失败，所以该变异体从未被覆盖。问题的关键在于第三个测试用例使得第一个测试用例变得多余。

这里是代码的一个轻微修订，使其可被 100% MT 覆盖率测试：

// Return the subtree rooted by rt that has rec removed from it
Node removehelp(Node rt, Record rec) {
  // if (rt == null) { return null; } DO NOT INCLUDE THIS IF WE KNOW THE RECORD IS THERE
  if ((rt.value() >= rec) && (!rt.value().equals(rec))) { // Combine the two cases
    rt.setleft(removehelp(rt.left(), key));
  }
  else if (rt.value() < rec) {
    rt.setright(removehelp(rt.right(), key));
  }
  else {
    // FOUND IT: Replace this node with an appropriate substitute
    ...
  }
}

此处我们合并了向左移动的两个情况，从而完全指定了所需条件。此代码既易于测试，又稍显简单。

值得注意的是，我们本可以简单地移除针对小值向左的情况（第一个测试）。因为第二个测试将大记录发送到右侧，所以第三个（不相等记录）测试实际上也捕获了小键向左的行为。代码的这一改动是可测试的。哪种方法更容易理解，这属于个人偏好。

14.4. 约束过多的代码：大数指数¶

本示例在精神上与上一个类似，但可能更容易理解。考虑编写一个函数，该函数接收一个基数和一个指数，用于计算基数的指数次幂。我们可以编写此函数，其中包含两个基本情况（ exponent == 0 和 exponent == 1 ），以及两个递归调用，分别用于指数为偶数或奇数的情况。

public int exponentiate(int base, int exponent) {
  if (exponent == 0) {
    return 1;
  }
  else if (exponent == 1) {
    return base;
  }
  else if (exponent % 2 == 0) {
    return exponentiate(base * base, exponent / 2);
  }
  else {
    return base * exponentiate(base, exponent - 1);
  }
}

这很有道理，我们处理两个特殊案例，其中指数幂的规则可能有点棘手，然后我们处理两个一般案例，其中如果指数是偶数或奇数，我们计算略微不同的数字。四个情况，四个案例。不幸的是，我们将发现无法测试此代码的所有分支---即使测试“覆盖”了所有案例（因为它们确实执行了所有分支！）。正如最后一个例子一样，我们可能会通过注意到有四个分支，但实际上只有三个结果：基本情况、偶数情况和奇数情况而意识到有一个问题。这是因为虽然 0 是一个真正的基例（它不应该像其他偶数那样对待），但 1 实际上是一个优化，因为奇数情况最终会正确处理它。

考虑 MT 在第二个条件 else if (exponent == 1) 上的表现。如果 MT 将此测试设置为 TRUE，我们总是返回基数而不是计算意图的结果。例如，计算 (8, 2) 应返回 64，但如果突变体使第一个 else if 为 TRUE，代码将返回 8，从而允许该突变体被杀死。但如果 MT 将此条件设置为 FALSE 呢？这意味着我们的代码将跳过该基本情况，这似乎表明输入为 1 会导致失败。但接下来会发生什么。如果我们修改示例，尝试调用 exponentiate(8, 1)，其中 MT 将第一个 else if 设置为 FALSE，我们将进入 else 分支，将 8 * exponentiate(8, 0) 相乘。exponentiate 的结果为 1，因为它触达了基本情况，因此我们得到 8 * 1，即 8，这是正确的。因此，我们并没有检测到该突变体。这里的“问题”在于，检查 1 的测试与（一个特殊实例的）奇偶条件冗余。在某些情况下，像这样的优化测试可能会导致运行时效率的提升。但从突变测试的角度来看，这是不必要的代码复杂性。

这里是代码的轻微修订，允许我们实现 100% 的 MT 覆盖率：

public int exponentiate(int base, int exponent) {
  if (exponent == 0) {
    return 1;
  }
  else if (exponent % 2 == 0) {
    return exponentiate(base * base, exponent / 2);
  }
  else {
    return base * exponentiate(base, exponent - 1);
  }
}

这仅仅是移除了第二个基本情况。这段代码既易于测试，又稍微简单一些。

14.5. 通过变异测试未捕获的 Bug：哈希插入¶

变异测试效果相当不错。它能够捕获大多数错误，并有助于指导你找到测试薄弱的地方（或者你的代码过于复杂）。但它并不完美，有时它会漏掉一些错误。考虑这个例子：在哈希表插入操作中，我们不希望哈希表超过一半满。假设任何会导致哈希表超过一半满的插入操作都会使其自动加倍大小，并重新插入所有现有记录。

处理这种展开的正确方法是先计算是否需要进行展开，如果需要则执行展开，然后计算正确的哈希索引：

private void localInsertCorrect(Record inH) throws IOException {
  if (numElements >= table.length / 2) {
    expand();
  }
  int home = h(inH.key());
  int h2 = h2(inH.key());
  int slot = home;
  while ((table[slot] != null) && !isTombStone(table[slot])) {
    slot = (slot + h2) % table.length;
  }
  table[slot] = inH;
  numElements++;
}

然而，一个简单的错误是在检查扩展条件 之前 计算索引：

 private void localInsertIncorrect(Record inH) throws IOException {
   // these should be after the expansion
   int home = h(inH.key());
   int h2 = h2(inH.key());
   int slot = home;
   if (numElements >= table.length / 2) {
     expand();
   }
   while ((table[slot] != null) && !isTombStone(table[slot])) {
     slot = (slot + h2) % table.length;
   }
   table[slot] = inH;
   numElements++;
}

在第一个示例中，如果您有一个大小为 4 的哈希表并插入第三个对象，那么您就触发了扩展情况。如果该对象应哈希到哈希表新部分中的某个位置（索引 4-7），它将正确处理这种情况。然而，在不正确的代码中，它会将这个新插入发送到前四个位置中的某个位置（索引 0-3）。但是，为了满足变异测试（即覆盖分支），您只需要在扩展情况下插入任何内容即可。因此，一个将某个会正确哈希到现有哈希表一半中的对象（索引 0-3）插入的测试，在两种实现上都会通过。这满足了变异测试，但错过了实际锻炼该错误。这个示例有点牵强，因为它要求测试最小化，仅哈希到表中的小索引。更好的测试会捕获该错误。尽管如此，这是一个变异测试未能警告开发人员其测试不充分的情况。