前言
whosbug
项目中,最重要的无非是两个部分:
- 对接入项目的
AST
静态语法解析 - 责任人归属算法
`whosbug`初版发布后我们进行了一系列的测试,发现了老算法在一些场景下的局限性(如对没有第三方库调用的处理、多语言下的泛用性不足等问题)
代码语言:txt复制于是在参考了部分论文后,我们结合实际落地场景设计了新的责任人归属算法 —— **Keyman**,本文我们就详细介绍下算法设计
主要设计思想
函数唯一标识
为了清晰一个函数在语法树中的精确位置,首先我们需要每个函数的唯一标识,这里我们的标识为:
<img src="https://kevinello-1302687393.cos.ap-hongkong.myzijiebao.com/img/20211011154354.png" style="zoom: 50%;" />
并且包 / 类也视作一个函数,将包/类内的代码非函数内代码归入这个包 / 类的函数
获取可能和这次错误相关的函数
Init
: 获取预设的迭代次数NUMBER_OF_ITERATION
,新建相关方法集methods
,以错误堆栈中涉及的所有方法为初值- 不断地从
methods
内的每个函数/方法找到与其相连且未在methods
内的方法,加入methods
中,也同时得到该方法与直接错误方法的距离。如此全面进行NUMBER_OF_ITERATION
次
NUMBER_OF_ITERATION = 3
methods = stacks.all_methods()
# stacks.all_methods()内的method的relevance_weight都为0
for i in range(NUMBER_OF_ITERATION):
for method in methods:
members = ['father', 'son', 'brother']
for member in members:
method_got = method.__getattribute__(member)
if method_got not in methods:
method_got.relevance_weight = method.relevance_weight 1
methods.append(method_got)
计算每个函数对该次出错的贡献
贡献
考虑一个函数与直接导致错误的函数(输入的堆栈中的原始栈帧)的距离(语法树中的距离)、其原始栈帧到栈顶的距离以及其置信度
$$
mathit{Contribution} = mathit{Confidence frac{1}{frameNumber 1} left( NUMBER_OF_ITERATION - relevanceDist right)}
$$
置信度
置信度的设定能保证:
- 函数保留的越久越可信(时间维度上的考虑,一定程度上也考虑了初版的假设:越近的修改越容易导致
bug
) - 函数大改时会基本回落到初始化的置信度
- 一定程度上区分
bugfix
型的变动和业务变更的变动
初始化
$$
mathit{Confidence = a^{lineCount} * overline{SubMethod.Confidence} quad left(a epsilon (0,1)right)}
$$
以下两种情况下,$SubMethod.Confidence$视为1:
- 一个函数没有调用子函数时,$overline{SubMethod.Confidence}$整项视为1
- 调用的子函数为系统函数 / 第三方库函数时,$SubMethod.Confidence$视为1
更新
$$
mathit{Confidence := left(frac{remainLineCount}{lineCount} oldConfidence frac{newLineCount}{lineCount}a^{newLineCount} *overline{newSubMethod.Confidence}right)^{PropensistyForChange}}
$$
函数大改时,$frac{remainLineCount}{lineCount} *oldConfidence$一项将接近于0,置信度会基本回落到初始化的置信度
变更倾向系数
变更倾向系数基于以下假设,在一个函数的一次变更内:
- 逻辑代码行的修改越多,我们越倾向于认为这是一次
bugfix
- 调用方法行的修改越多,我们越倾向于认为这是一次业务更新
- 代码留存的时间越长,认为其置信度越高
$$
mathit{PropensistyForChange = transleft(frac{Delta{logicLineCount/logicLineCount}}{Delta{functionCallCount}/functionCallCount} dright)}
mathit{trans(x) = b^{cx}}
b epsilon (0 , 1), c epsilon (0 , infty), d epsilon (0 , infty)
mathit{PropensistyForChange} epsilon left(0,b^{cd}right]
$$
trans
函数用于值域变换,使变更倾向归一化到$left(0,b^{cd}right]$,其中超参数b, c
对曲线的走向有一定影响
同时超参数d
使得PropensistyForChange
始终小于1,保证每次置信度更新时都会更趋近于1(代码留存的时间越长,认为其置信度越高)
计算获取一个函数的主要贡献者
代码语言:python代码运行次数:0复制commiters = []
contribution_rate = 1
for commit in related_commits:
weight = commit.commiter.weight
weight = contribution_rate*(changed_line_count/all_line_count)*Confidence
commiters.append(commit.commiter)
unchanged_rate *= 1-(changed_line_count/all_line_count)
commiters.sortByWeight(reverse = True)
假设:有三次不同的commit存在,且三次提交的变动情况如图,
会被处理为
<img src="https://kevinmatt-1303917904.cos.ap-chengdu.myzijiebao.com/截屏2021-10-13 14.31.23.png" alt="image-20211013143009732" style="zoom: 25%;" />