Page 78 - 《软件学报》2021年第6期

1652 Journal of Software 软件学报 Vol.32, No.6, June 2021

27: end for
28: return BranchInfos
分支简化是非常重要的一步,如果没有分支简化操作或者分支简化没有在遍历各个组件的过程中进行,后
面将会面临前面提到的代码生成的“分支爆炸”问题.算法 2 详细描述了对于单个组件的分支简化算法,对应到
算法 1 中第 24 行的 simplifyBranchPath 函数.该算法的整体思路是:遍历当前组件的所有分支路径的组合,找到
可以合并的分支路径,并使用合并后的分支路径将其替换.比如,{0,0B,0F}和{0,0B,1F}这两个分支路径可以合
并为{0,0B}.为了避免无意义的分支路径组合的遍历,首先对所有分支路径按照分支路径的长度从小到大排序,
比如,{0,0B,0F},{0,1B},{0,0B,1F}排序后变为{0,1B},{0,0B,0F},{0,0B,1F},如算法 2 的第 1 行所示.然后,从后向前
进行匹配寻找可能合并的分支路径,这里的匹配条件为:1) 具有相同的分支数量;2) 具有完全相同的数据源;
3) 除分支路径内最后一个分支外,前面的分支完全相同,如{0,0B,0F}和{0,0B,1F};4) 分支路径内最后一个分支
的分支组件相同.分支路径匹配的伪代码见算法 2 的第 2 行~第 23 行,其中,第 9 行、第 10 行和第 20 行用来存
储匹配到的所有分支路径.第 24 行~第 31 行尝试将匹配到的分支路径进行合并,可以合并意味着所有匹配到的
分支路径各自的最后一个分支是互补的,比如,{0,0B,0F}和{0,0B,1F}中的 0F 和 1F 在二分支的情况下就是互补
的,多分支也是同理.如果可以合并,则将合并后的分支路径插入当前分支路径的集合中继续参与匹配,因为有
些情况的分支路径集合可以进行多次合并,比如,{0,1B},{0,0B,0F},{0,0B,1F}最终可以合并为{0}.之后继续尝试
新的匹配,直到遍历完所有分支路径的组合.
算法 2. 对于单个组件的分支信息简化算法.
输入:组件的所有分支信息组 BranchPathsWithDataSrc;
输出:简化的组件所有分支信息组 SimpleBranchPathsWithDataSrc.
1: SimpleBranchPathsWithDataSrc=sortByBranchPathLength(BranchPathsWithDataSrc)
2: curPos=len(SimpleBranchPathsWithDataSrc)−1
3: while curPos>0 do
4: branchPath=SimpleBranchPathsWithDataSrc[curPos].key
5: dataSrcs=SimpleBranchPathsWithDataSrc[curPos].value
6: subBranchPath=branchPath[0:−1]
7: lastBranch=branchPath[−1]
8: findPos=curPos−1
9: branchPathsWithSameDataSrc=∅
10: branchPathsWithSameDataSrc.append(branchPath)
11: while findPos>0 do
12: branchPathFind=SimpleBranchPathsWithDataSrc[findPos].key
13: dataSrcsFind=SimpleBranchPathsWithDataSrc[findPos].value
14: subBranchPathFind=branchPath[0:−1]
15: lastBranchFind=branchPath[−1]
16: if len(branchPath)=len(branchPathFind) and
17: dataSrcsFind==dataSrcs and
18: subBranchPath==subBranchPathFind and
19: getBranchActor(lastBranch)==getBranchActor(lastBranchFind) then
20: branchPathsWithSameDataSrc.append(branchPathFind)
21: end if
22: findPos=findPos−1
23: end while