批量同步Gerrit Change的先后逻辑算法-阿里云开发者社区

开发者社区> 开发与运维> 正文

批量同步Gerrit Change的先后逻辑算法

简介:

做某个项目,会将开发提供的一堆gerrit change同步下来后,自动编译。
但一组gerrit change可能由于dependOn的问题,合理同步顺序不一定是开发的提交顺序。比如,存在提交 1 和提交 2,提交1依赖于提交2,那么,合理的下载顺序是,先下载提交2,再下载提交1。

那如果开发需要编译的提交有十几个,怎么计算?
一开始的想法,这就是一个有向图,每个提交就是一个节点,而提交之前的依赖关系就是连接。当然,有可能这几个提交互相都没有关系,那就可以虚拟一个root。然后通过深度优先遍历得到正确的顺序。

感觉以上想法,代码量有点多,同时,需求上其实并不在意同级的提交谁先谁后,只在意dependOn的提交先被同步,于是,通过类似动态规划的想法,设计出如下算法:
思路:对于一组开发的提交,可以分成两组,一组A是可以认为是不安全的,另一组B认为是安全的,即同步的顺序是确定。只要不断地确定B的集合,就能得出相应的队列。

举例:开发有提交1,2, 3, 4
其中,1依赖于2和3,2依赖于4, 3依赖于4, 4不依赖任何提交

1. 初始集合 setA = {1,2,3,4}
2. 得出初始数组的依赖集合 setB = {2,3,4}
3. setA – setB,得出 {1},入列表[1]
4. setA & setB = {2,3,4},将其设为新的setA
5. 得到新的setB = {4}
6. setA – setB,得出 {2,3},入列表得到[2,3,1] (注,新的需要放在头上,当然,放成[3,2,1]也可以,因为认为2与3是等价的)
7. setA & setB = {4},将其设为新的setA
8. setB为空
9. setA – setB,得出 {4},入列表得到[4,2,3,1]

  1. 由于setB为空,跳出循环

实际使用中,这个算法能处理循环依赖问题,也就是如果存在setA为空的时候,就说明出现了循环依赖。同时,也能处理依赖的提交并不在用户提交的提交列表的情况,如,提交4依赖于提交5。由于采用了集合的运算,能很快将这些噪音过滤掉。

附上Python代码,其中self.getDependsOnArray(list(setGerrit))是获取提交的依赖提交集合,另,一开始设计的时候,想用stack来处理得到的safe提交,实现的时候,觉得用list比较方便,就用list来处理了。

代码是以前写的,存在大量对pep8规范的违反,请主动忽略

    def resortGerritNumberForDependency(self, gerritInfo_arr):
        #Sort the gerrit changes here to make sure the depeneded gerritchange is got at first. 
        #  Algorithm is as following:
        #    1. Initial set of gerrit changes topSet, as setGerrit
        #    2. Get its depends on gerrit changes, as setDependsGerrit, set(gerritB) = set(gerritB) and set(gerritA)
        #    3. DiffGerrit = setGerrit - setDependsGerrits. 
        #    4. push DiffGerrit into stack
        #    5. if setDependsGerrit & setGerrit is not empty, set it as topSet and go to step 1, else break
        #    6. Pop gerrit stack. The sequence will be the one to get gerrit changes without dependency conflicts
        newOrderGerrit = []
        topSet = gerritInfo_arr
        while True:
            setGerrit = set(topSet)
            setDependsGerrits = self.getDependsOnArray(list(setGerrit))
            diffSet = setGerrit - setDependsGerrits
            if not len(diffSet):
                logging.error("There is recursive dependency!")
                newOrderGerrit = []
                break
            else:
                #the new found one will be at the head of list which iterated at first
                newOrderGerrit = list(diffSet)+(newOrderGerrit)
            
            topSet = setDependsGerrits & setGerrit
            if not len(topSet):
                #break only this is empty. Because diffSet make sure in each loop, the number will be decreased,
                # there will not be any endless loop under this logic. 
                break
            
        return newOrderGerrit

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章