做某个项目，会将开发提供的一堆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