关于算法:refdiff插件的计算提交版本差异算法

本文作者：Nddtfjiang
个人主页：https://github.com/mappjzc

什么是 计算提交版本差别（CalculateCommitsDiff）？

咱们经常须要计算两个 提交版本 之间的差别。具体的说，就是须要晓得两个不同的 分支 / 标签 之间相差了哪些 提交版本。

对于个别用户来说，通过 计算提交版本差别 ，用户能迅速的判断两个不同的 分支 / 标签 之间在性能、BUG 修复等等方面的区别。以帮忙用户抉择不同的 分支 / 标签 来应用。

而如果只是应用 diff 命令来查看这两个不同的 分支 / 标签 的话，大量庞杂冗余的代码批改信息就会毫无组织的混淆在其中，要从中提取出具体的性能变更之类的信息，等同于海底捞针。

对于一款致力于晋升研发效力的产品来说，通过 计算提交版本差别 ，就能查看一组组不同的 分支 / 标签 的变迁情况，这一数据的获取，有助于咱们做进一步的效力剖析。

例如，当一个我的项目的管理者，想要看看为什么最近的几个版本发版越来越慢了的时候。就能够对最近的几组 分支 / 标签 来计算 计算提交版本差别 。此时有些 分支 / 标签 组之间有着大量的 提交版本 ，而有些 分支 / 标签 组之间有着较少的提交版本。我的项目管理者能够更进一步的计算这些提交版本各自的代码当量，把这些数据以图表的模式展现进去，最终失去一组很直观的 分支 / 标签 的图像。此时他或者就能发现，原来是因为最近的几次发版波及到的变更越来越简单了。通过这样的直观的信息，开发者和管理者们都能做出相应的调整，以便晋升研发效力。

已有的解决方案

当咱们在 GitLab 上关上一个代码仓库的时候，咱们能够通过在 url 开端追加 compare 的形式来进入到仓库的比对页面。

在该页面，咱们能够通过设置 源分支 / 标签 和 指标分支 / 标签 让 GitLab 向咱们展现 指标分支落后于源分支哪些版本，以及落后了多少个版本。

设置结束后，GitLab 会展现如下：

在这里，咱们能看到咱们抉择的 指标分支 / 标签 比源分支 / 标签 少了如图所示的 提交版本（Commits）

然而遗憾的是，像 GitLab 这类解决方案，都没有做批量化，自动化的解决。也更没有对后续的计算出来的后果进行相应的数据汇总解决。用户面对海量的分支提交的时候，既不可能手动的一个一个去比拟，也不可能手动的去把数据后果本人复制粘贴后再剖析。

因而 DevLake 就必须要解决这个问题。

所谓的 计算提交版本差别 具体是在计算什么？

以 GitLab 的计算过程为例来说的话，所谓的 计算提交版本差别 也就是当一个 提交版本 在源分支 / 标签 中存在 ，然而在 指标分支 / 标签 中不存在 的时候，这个提交版本就会被 GitLab 给逮进去。

那么，或者有人会问，如果一个 提交版本 在源分支 / 标签 中不存在 ，相同的，在 指标分支 / 标签 中存在，那是不是也会被抓起来呢？

答案是，不会。

也就是说，当咱们计算 提交版本 的差别的时候，咱们只关怀 指标分支 / 标签 短少了什么，而并不关怀 指标分支 / 标签 多进去了什么货色。

这就如同以前有一位算法比赛的学生，在 NOI 较量完结后被相干学校面试的时候，一个劲的自我介绍本人负责过什么广播站青协学生会，什么会长副会长之类的经验。后果很快就惹得面试官老师们忍气吞声的告诫道：

咱们只想晓得你信息学方面的自我介绍，其余的我都不感兴趣！！！

在计算 提交版本 差别时，GitLab 是这样。GitHub 也是这样。事实上，在应用 git 命令 git log branch1...branch2 的时候，git 也是这样的。

它们都只关怀 指标分支 / 标签 绝对于 源分支 / 标签 短少的局部。

计算 提交版本 差别实际上就是：

• 计算待计算的 指标分支 / 标签 绝对于 源分支 / 标签 短少了哪些 提交版本。

对 提交版本 进行数学建模

想要做计算，那么首先，咱们须要把一个形象的事实问题，转换成一个数学问题。

这里咱们就须要进行数学建模了。

咱们须要把像 指标分支 / 标签 、 源分支 / 标签 、 提交版本 这样一系列的概念变成数学模型中的对象。

如此咱们能力为其设计算法。

想当然的，咱们就想到了应用图的形式来进行数学建模。

咱们将每一个 提交版本 都看作是图上的一个节点，把 提交版本 合并之前的一组 提交版本 与以后 提交版本 之间的父子关系，看作成是一条 有向边。

因为 指标分支 和源分支 事实上也各自与一个特定的 提交版本 相绑定，因而也能将它们看作是图上的特地节点。

• 将 指标分支 / 标签 所对应的节点，命名为 旧节点
• 将 源分支 / 标签 所对应的节点，命名为 新节点

当然，这里咱们还有一个须要特地关注的节点，就是初始的 提交版本 所代表的节点

• 将初始 提交版本 所对应的节点，命名为 根节点

上述的形容或者显得有点儿形象。

咱们当初来理论举一个例子。来看看如何对一个仓库进行上述数学建模。

假如当初有基于如下形容而产生的一个仓库：

1. 创立空仓库
2. 在 main 分支上创立 提交版本 1 作为初始提交
3. 在 main 分支上创立 提交版本 2
4. 在 main 分支上创立新分支 nd
5. 在 nd 分支上创立 提交版本 3
6. 在 main 分支上创立 提交版本 4
7. 在 main 分支上创立新分支 dtf
8. 在 main 分支上创立 提交版本 5
9. 在 dtf 分支上创立 提交版本 6
10. 在 main 分支上创立新分支 nddtf
11. 在 nddtf 分支上创立 提交版本 7
12. 把 nd 分支合并到 nddtf分支
13. 把 dtf 分支合并到 nddtf分支
14. 在 main 分支上创立 提交版本 8
15. 在 nddtf 分支上创立 提交版本 9

咱们对上述的仓库进行构图之后，最终会失去如下图所示的一个有向图：

• 此时黑白节点 1 为 根节点
• main 分支为 1 2 4 5 8
• nd 分支为 1 2 3 随后合并入 nddtf 分支
• dtf 分支为 1 2 4 6 随后合并入 nddtf 分支
• nddtf 分支为 1 2 3 4 5 6 7 9

能够看到，每一个 提交版本 在图中都绝对应的有一个节点

此时咱们把 提交版本 1 所代表的节点，作为 根节点

当然这里可能会有同学发问了：

• 如果我这个仓库有 一万个 根节点 怎么破？

置信一些常常做图的建模的同学应该都晓得破法。

• 创立一个名叫为 一万个根节点 的虚构节点，把它设为这些个虚伪的 根节点 的父节点，来当作真正的 根节点 即可。

在这个有向图中，咱们并没有理论的去指定具体的 指标分支 / 标签 或者 源分支 / 标签

在理论应用中，咱们能够把任意的两个 提交版本 作为一对 指标分支 / 标签 和源分支 / 标签
当然，有的同学在这里可能又会产生一个问题：

• 指标分支 / 标签 和源分支 / 标签 尽管都能映射到其最初的 提交版本 上，然而实际上来说 提交版本 与分支 / 标签 实质上就是两种不同的概念。

分支 / 标签 的本质，是蕴含一系列的 提交版本 的汇合。而特定的 提交版本 仅仅是这个汇合中的最初一个元素罢了。

当咱们把一个仓库通过上述数学建模形象成一个有向图之后，这个汇合的信息，会因而而失落掉吗？

对于一个非法的仓库来说，答案显然是，不会

实际上，这也就是为什么咱们肯定要在该有向图中强调 根节点 的起因。

咱们这里这里，先给出论断：

分支 / 标签 所对应的节点，到 根节点 的全副门路中路径的 所有节点 的汇合，即为该 分支 / 标签 所蕴含的 提交版本 汇合。

简略证实 上述论断

• 设 根节点 为节点 A
• 设要求的 分支 / 标签 所代表的节点为节点 B

• 当 节点 C 是属于要求的 分支 / 标签
• 因为 节点 C 是属于要求的 分支 / 标签
• 所以 必然存在一组提交或者合并 使得 节点 C 能够始终提交到节点 B
• 又因为 每一个新增的提交 或者 合并操作，均会切实的建设一条从新增的提交 / 合并到以后提交的边
• 所以，反过来说，每一个提交或者合并后的节点，均能够到达节点 C
• 所以 节点 B 存在至多一条门路 能够 到达节点 C
• 同理可证，节点 C 存在至多一条门路到达 根节点 也就是节点 A
• 综上，存在一条从节点 B 到节点 A 的门路，通过节点 C

• 当 节点 C 不属于要求的 分支 / 标签
• 假如 存在一条从节点 B 到节点 A 的门路，通过节点 C
• 因为 每一条边都是由新增的提交或者合并操作建设的
• 所以 必然存在一系列的新增提交或者合并操作，使得节点 C 成为节点 B
• 又因为 每一个提交在形象逻辑上都是举世无双的
• 因而，如果缺失了节点 C 则必然导致在构建节点 B 所代表的 分支 / 标签 的过程中，至多存在一个提交或者合并操作无奈执行。
• 这将导致分支非法
• 因而 假如不成立
• 因而 其逆否命题 对任意一条从节点 B 到节点 A 的门路，都不会通过节点 C 成立

• 依据
• 当 节点 C 是属于要求的 分支 / 标签，存在一条从节点 B 到节点 A 的门路，通过节点 C（必要性）
• 当 节点 C 不属于要求的 分支 / 标签，对任意一条从节点 B 到节点 A 的门路，都不会通过节点 C（充分性）
• 可得 分支 / 标签 所对应的节点，到 根节点 的全副门路中路径的 所有节点 的汇合，即为该 分支 / 标签 所蕴含的 提交版本 汇合。

算法抉择

咱们当初曾经实现了数学建模，并且曾经为数学建模做了根本的证实。当初，咱们终于能够开始在这个数学模型的根底上来设计并实现咱们的算法了。

如果没有做上述根本论证的同学，这里可能会犯一个小谬误：那就是它们会误以为，只有计算两个节点之间的最短门路即可。若真是如此的话，SPFA，迪杰斯特拉 （Dijkstra），甚至头铁一点儿，来个 弗洛伊德 （Floyd）都是很容易想到的。当然因为该有向图的所有边长都是 1，所以更简略的办法是间接应用 广 / 宽度优先搜索算法（BFS）来计算最短路。

上述的一系列耳熟能详的算法，或多或少都有成熟的库能够间接应用。然而遗憾的是，如果真的是去算最短路的话，那最终后果恐怕会不尽如人意。

在 DevLake 的晚期不成熟的版本中，已经应用过最短路的算法来计算。只管对于比较简单线性的仓库来说，能够歪打正着的算出后果。然而当仓库的分支和合并变得复杂的时候，最短路所计算的后果往往都会脱漏大量的 提交版本。

因为在方才咱们曾经论证过了，这个 分支 / 标签 所蕴含的 提交版本 汇合，是必须要全副门路才行的。只有全副门路，能力满足充沛且必要条件。

也就是说，两头只有漏了一条门路，那就会漏掉一系列的 提交版本。

要计算这个有向图上的 旧节点 所代表的 分支 / 标签 比新节点 所代表的 分支 / 标签 短少了哪些 提交版本。

本质上就是在计算 旧节点 到根节点 的全副门路所经节点，比照 新节点 到根节点 的全副门路所经节点，短少了哪些节点。

如果咱们数学建模的时候，把这个有向图建设成一棵树的话。

那么相熟算法的同学，就能够很天然的应用最近公共先人（LCA）算法，求出其并集，而后再来计算其对应的缺失的局部。

然而作为一个有向图来说，树结构的算法是没法间接应用的。所幸的是，咱们的这个图，在由非法仓库生成的状况下，必然是一个有向无环图。

一个有向无环图，也是有本人的最近公共先人（LCA）算法的。

只是，这里有两个问题：

• 咱们真的对 最近公共先人 这个特定的节点感兴趣吗？
• 在有多个不同门路的公共先人的状况下，只求一个最近公共先人有什么意义呢？

首先，咱们须要明确咱们的需要。

咱们只是为了计算。

• 旧节点 到根节点 的全副门路所经节点，比照 新节点 到根节点 的全副门路所经节点，短少了哪些节点。

除此之外的，咱们不感兴趣。

换句话说，咱们想晓得其公共先人，然而，不关怀它是不是最近的。

它是近的也好，它是远的也罢，只有是公共先人，都得抓起来。去求最近公共先人，在树结构下，能够近似等价于求其全副先人。因而能够应用该算法。

然而在有向无环图下，最近公共先人就是个废物。求进去了又能如何？

基本上，还是应该去求全副的公共先人。

所以咱们别无选择，只能用最间接的算法。

• 计算出 旧节点 到根节点 的全副门路所经节点
• 计算出 新节点 到根节点 的全副门路所经节点
• 查看 新节点 的全副门路所经节点短少了哪些节点

如何计算任意节点到 根节点 的全副门路所经节点？

在 OI 上纯熟于骗分导论的同学们，应该很天然的就意识到了

深度优先搜寻（DFS）

当然，这里补充一下，因为 根节点 的性质，事实上，无论是从哪个方向登程，无论走那条边，只有是能走的边，最终都会到达 根节点

因而，在上述条件成立的根底上，没有记录门路状态的 广 / 宽度优先搜寻（BFS）也是能够应用的。因为在必然能到达 根节点 的前提下，能够疏忽门路状态，不做门路的可行性判断。

当然，这一前提，也有利于咱们 深度优先搜寻（DFS）进行优化。

在咱们执行 深度优先搜寻（DFS）的时候，咱们能够将所有拜访到的节点，均增加到汇合中，而无需期待确认该节点能的确到达 根节点 后再进行增加。

实际上这里在一个问题上咱们又会呈现了两种一致。
问题是，如何将一个节点增加到汇合中。计划有如下两种。

染色法：增加到汇合中的节点进行染色，未增加到汇合中的节点不进行染色。
汇合法：应用均衡树算法建设一个汇合，将节点增加到该汇合中。

这两种算法各有优劣。

• 染色法的劣势在于，染色法增加一个元素的工夫复杂度是 O(1) 的，快准狠。相比较而言，汇合法增加一个元素的工夫复杂度是 O(log(n))。
• 汇合法的劣势在于，汇合法遍历所有元素的工夫复杂度是 O(n) 的，而染色法下，要遍历所有元素工夫复杂度会是 O(m)，同时汇合法能够通过设计一个优良的 hash 算法代替均衡树，来将工夫复杂度优化到靠近 O(1).（这里 n 示意汇合大小，m 示意整个图的大小）

咱们这里抉择应用汇合法。实际上这两种算法都差不多。

算法实现

• 依据提交建图
• 咱们对 旧节点 应用 深度优先搜寻（DFS）计算出其到 根节点 的全副门路所经节点，增加到 汇合 A 中
• 接着，咱们对 新节点 应用 深度优先搜寻（DFS）计算出其到 根节点 的全副门路所经节点，增加到 汇合 B
• 留神，这里有一个优化，这个优化是建设在咱们的需要上
• 反复一遍咱们的需要
• 咱们只关怀 指标分支 / 标签 短少了什么，而并不关怀 指标分支 / 标签 多进去了什么货色。
• 因而当对 新节点 应用 深度优先搜寻（DFS）搜寻到曾经在 汇合 A 中的节点时，能够认为该节点已搜寻过，无需再次搜寻。
• 此时的 汇合 B，能够恰好的避开 汇合 A 中已有的所有节点，因而，恰好就是咱们所需的后果。

外围的计算代码如下所示：

oldGroup := make(map[string]*CommitNode)
var dfs func(*CommitNode)
// put all commit sha which can be depth-first-searched by old commit
dfs = func(now *CommitNode) {if _, ok = oldGroup[now.Sha]; ok {return}
    oldGroup[now.Sha] = now
    for _, node := range now.Parent {dfs(node)
    }
}
dfs(oldCommitNode)

var newGroup = make(map[string]*CommitNode)
// put all commit sha which can be depth-first-searched by new commit, will stop when find any in either group
dfs = func(now *CommitNode) {if _, ok = oldGroup[now.Sha]; ok {return}
    if _, ok = newGroup[now.Sha]; ok {return}
    newGroup[now.Sha] = now
    lostSha = append(lostSha, now.Sha)
    for _, node := range now.Parent {dfs(node)
    }
}
dfs(newCommitNode)

这里的 lostSha 即为咱们最终求得的缺失的局部

算法执行的演示动画

咱们用一个简陋的动画来简略的演示一下，上述算法在逻辑上执行的状况。

• 旧节点 为节点 8
• 新节点 为节点 9

如上述动画所演示的个别
从节点 8 开始执行 深度优先搜寻（DFS）到 根节点 停止
从节点 9 开始执行 深度优先搜寻（DFS）到曾经在节点 8 的汇合中的节点为止
此时，在节点 9 执行 深度优先搜寻（DFS）过程中被拜访到的所有非节点 8 的节点

• 节点 3
• 节点 6
• 节点 7
• 节点 9

它们所对应的 提交版本 就是咱们要求的差集

此时最短路为 9 -> 7 -> 5 -> 8
此时最近公共父节点为 5，到该节点的门路为 9 -> 7 -> 5
从上图中也能够直观的看到如果应用最短路算法，或者最近公共父节点算法的状况下，咱们是无奈失去正确答案的。

时空复杂度

设 提交版本 的总大小为 m，每一组 源分支 / 标签 和指标分支 / 标签 的均匀大小为 n，一共有 k 组数据

DFS 每拜访一个节点，须要执行一次退出汇合操作。咱们依照咱们理论实现中应用的 均衡树算法来计算 工夫复杂度为 O(log(n))

此时咱们能够计算得出

• 建图的工夫复杂度：O(m)
• 计算一组 源分支 / 标签 和指标分支 / 标签 工夫复杂度：O(n*log(n))
• 计算所有 源分支 / 标签 和指标分支 / 标签 工夫复杂度：O(k*n*log(n))
• 读取、统计后果工夫复杂度：O(k*n)
• 总体工夫复杂度：O(m + k*n*log(n))

• 图的空间复杂度：O(m)
• 每组 源分支 / 标签 和指标分支 / 标签 汇合的空间复杂度：O(n)（非并发状况下，k 组数据可共用）
• 总体空间复杂度：O(m+n)

关键词

• DevLake
• CalculateCommitsDiff
• 算法
• 数学建模
• 证实逻辑
• 充分条件
• 必要条件
• 图论
• 深度优先搜寻（DFS）
• 广 / 宽度优先搜寻（BFS）
• 工夫复杂度
• 空间复杂度
• 时空复杂度

理解更多最新动静

官网：https://devlake.incubator.apache.org/

GitHub：https://github.com/apache/incubator-devlake/

Slack：通过 Slack 分割咱们

原文链接：https://devlake.apache.org/blog/refdiff-calculate-commits-diff