Keyman算法设计哲学

It has been 1162 days since the last update, the content of the article may be outdated.

前言

whosbug项目中，最重要的无非是两个部分：

对接入项目的AST静态语法解析
责任人归属算法

whosbug初版发布后我们进行了一系列的测试，发现了老算法在一些场景下的局限性（如对没有第三方库调用的处理、多语言下的泛用性不足等问题）

于是在参考了部分论文后，我们结合实际落地场景设计了新的责任人归属算法 —— Keyman，本文我们就详细介绍下算法设计

主要设计思想

函数唯一标识

为了清晰一个函数在语法树中的精确位置，首先我们需要每个函数的唯一标识，这里我们的标识为：

并且包 / 类也视作一个函数，将包/类内的代码非函数内代码归入这个包 / 类的函数

获取可能和这次错误相关的函数

Init: 获取预设的迭代次数NUMBER_OF_ITERATION，新建相关方法集methods，以错误堆栈中涉及的所有方法为初值
不断地从methods内的每个函数/方法找到与其相连且未在methods内的方法，加入methods中，也同时得到该方法与直接错误方法的距离。如此全面进行NUMBER_OF_ITERATION次

python

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\ =\ trans\left(\frac{\Delta{logicLineCount/logicLineCount}}{\Delta{functionCallCount}/functionCallCount}+d\right)} \\ \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

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)