duanboshe0001 2017-12-18 05:57
浏览 66
已采纳

如何以编程方式找到两个分支的共同祖先

I am working on a project where I integrated my project with git. For integration purpose, I am using go-git library. My question is how can I find a common ancestor for two branches programmatically? I want to implement this function. Looks like go-gitand other go library do not provide such functionality.

  • 写回答

2条回答 默认 最新

  • dsc56927 2017-12-19 16:14
    关注

    Here is small program using go-git that mimics the behavior of git merge-base --all

    package main
    
    import (
        "fmt"
        "os"
    
        "gopkg.in/src-d/go-git.v4"
        . "gopkg.in/src-d/go-git.v4/_examples"
        "gopkg.in/src-d/go-git.v4/plumbing"
        "gopkg.in/src-d/go-git.v4/plumbing/object"
        "gopkg.in/src-d/go-git.v4/plumbing/storer"
    )
    
    // store h in set, s, handling nil s if necessary. Return new set.
    func store(s map[plumbing.Hash]bool, h plumbing.Hash) map[plumbing.Hash]bool {
        if s == nil {
            s = make(map[plumbing.Hash]bool)
        }
        s[h] = true
        return s
    }
    
    // mergeBase finds best common ancestors between two commits to use in a
    // three-way merge. One common ancestor is better than another common ancestor
    // if the latter is an ancestor of the former. A common ancestor that does not
    // have any better common ancestor is a best common ancestor, i.e. a merge base.
    // Note that there can be more than one merge base for a pair of commits.
    func mergeBase(s storer.EncodedObjectStorer, a, b plumbing.Hash) ([]plumbing.Hash, error) {
        commitA, err := object.GetCommit(s, a)
        if err != nil {
            return nil, err
        }
    
        commitB, err := object.GetCommit(s, b)
        if err != nil {
            return nil, err
        }
    
        // Mapping of direct descendants of each commit we visit
        desc := make(map[plumbing.Hash]map[plumbing.Hash]bool)
    
        // Set of commits reachable from a
        reachableFromA := make(map[plumbing.Hash]bool)
    
        // Walk commits reachable from A
        err = object.NewCommitPreorderIter(commitA, nil, nil).ForEach(func(c *object.Commit) error {
            reachableFromA[c.Hash] = true
            for _, h := range c.ParentHashes {
                desc[h] = store(desc[h], c.Hash)
            }
            return nil
        })
        if err != nil {
            return nil, err
        }
    
        // Set of common commits between a and b
        common := make(map[plumbing.Hash]bool)
    
        // Walk commits reachable from B
        err = object.NewCommitPreorderIter(commitB, nil, nil).ForEach(func(c *object.Commit) error {
            if reachableFromA[c.Hash] {
                common[c.Hash] = true
            }
            for _, h := range c.ParentHashes {
                desc[h] = store(desc[h], c.Hash)
            }
            return nil
        })
        if err != nil {
            return nil, err
        }
    
        best := make(map[plumbing.Hash]bool)
    
        // Trim down the set of common commits to only those that are best
        for h := range common {
            best[h] = true
            for child := range desc[h] {
                if common[child] {
                    // there is a descendant to h that is common to both a and b. h is not in best.
                    delete(best, h)
                    break
                }
            }
        }
    
        var result []plumbing.Hash
        for h := range best {
            result = append(result, h)
        }
        return result, nil
    }
    
    // Open an existing repository in a specific folder.
    func main() {
        CheckArgs("<path> <commitA> <commitB>")
        path := os.Args[1]
        a := plumbing.NewHash(os.Args[2])
        b := plumbing.NewHash(os.Args[3])
    
        r, err := git.PlainOpen(path)
        CheckIfError(err)
    
        bases, err := mergeBase(r.Storer, a, b)
        CheckIfError(err)
    
        for _, b := range bases {
            fmt.Println(b)
        }
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题