4.1.4　算法介绍

因为我们把FC和CBJ(同时结合变量的闭包)整合成一个混合回溯算法,在本节中将这个基于混合回溯方法的测试用例生成方法称为BFS-BB-Hybrid Backtracking(BFSBB-HB)。表4-2解释了BFS-BB-HB中用到的一些概念。

表4-2　BFS-BB-HB中用到的变量及其含义

(https://www.daowen.com)

待覆盖路径是BFS-BB-HB的输入,其中包括需要满足的约束(R)、输入变量的集合(X)和对应于每个变量的取值区间(D)。测试用例(result)是空的。如第2~10行所示,为每个变量计算其相关变量和闭包。当FV非空时,也就是说仍有变量未被赋值时,执行以下操作。对FV中的变量进行排序确定当前变量x*,从x*的区间D*中为其选择一个值V*,如第12和13行所示,其具体方法在第3章已经介绍过。第14行初始化S conflict(x*)。第15行执行前向检查来判断x*的赋值V*是否会导致不一致,同时对未来变量的区间进行削减。如果前向检查成功了,那么就将＜x*,V*＞加入result,将x*从FV移到PV,如第27~29行所示。接下来继续FV的排序。如果前向检查失败了,也就是说检测出了不一致,那么就需要确定矛盾变量。区间被消除的已赋值变量被放入x*的矛盾变量集,并使用快速排序确定其中层次最浅的变量(如x f),它就是矛盾变量。在这种情况下,CBJ将直接跳到x f所在的层次,如第17~21行所示。在有些情况下,x*的矛盾变量集是空的,那么就不可避免地只能执行BT,在x*上一层的变量变成了当前变量(第22行)。如第23~25行所示,使用矛盾信息来为当前变量选择一个赋值。接下来就开始新一次的前向检查(第26行),直到FV变成空集。最后,如第30行所示,返回result作为能够覆盖路径的测试用例。