git merge时三方合并算法源码解读

三方合并算法简介：

Git 的三方合并算法主要由 merge-recursive.c 和 diff.c 中的代码实现，核心部分涉及以下几个步骤：找到共同祖先、生成差异、合并变更。这段代码逻辑较复杂，这里只讲解 Git 代码库中的关键函数和其逻辑。

以下是简化和注释版的三方合并算法实现的核心代码片段：

1. 找到共同祖先 (common ancestor)

共同祖先的查找通过 merge-base 实现，使用 Git 的 DAG 结构查找分支的最低公共祖先。

源码：merge-base.c

 1 struct commit *get_merge_base(struct commit *one, struct commit *two) {
 2     // 找到分支 one 和 two 的最低公共祖先
 3     struct commit_list *list;
 4     struct commit *result;
 5 
 6     // 使用递归方法遍历提交图
 7     list = get_merge_bases(one, two);
 8     result = pop_commit(&list);
 9 
10     // 如果有多个祖先（Octopus），需要进一步处理
11     while (list) {
12         free_commit_list(list);
13         list = get_merge_bases(one, two);
14     }
15     return result;
16 }

2. 生成差异 (diff generation)

在找到共同祖先后，Git 会计算当前分支（HEAD）和目标分支相对于共同祖先的差异。

源码：diff.c

 1 void diff_tree_merge(const struct tree *ancestor, const struct tree *head, const struct tree *merge) {
 2     // 比较 ancestor 与 head 的差异
 3     diff_tree(ancestor, head, &diffopts);
 4 
 5     // 比较 ancestor 与 merge 的差异
 6     diff_tree(ancestor, merge, &diffopts);
 7 
 8     // 处理两组差异结果，供后续合并使用
 9     diffcore_std(&diffopts);
10 }

3. 三方合并逻辑 (Three-way merge)

三方合并的核心逻辑在 merge-recursive.c 中，通过 merge_trees 实现。

源码：merge-recursive.c

 1 int merge_trees(const struct tree *ancestor, const struct tree *head, const struct tree *merge) {
 2     struct traverse_info info;
 3     struct merge_options options;
 4     int merge_status;
 5 
 6     // 初始化合并选项
 7     memset(&options, 0, sizeof(options));
 8     options.head = head;
 9     options.merge = merge;
10 
11     // 递归合并文件和目录
12     merge_status = traverse_trees_recursive(ancestor, head, merge, &info, &options);
13 
14     if (merge_status < 0) {
15         fprintf(stderr, "Merge conflict detected\n");
16         return -1; // 冲突需要用户手动解决
17     }
18 
19     return 0; // 合并成功
20 }

int traverse_trees_recursive(const struct tree *ancestor, const struct tree *head, const struct tree *merge, 
                             struct traverse_info *info, struct merge_options *options) {
    // 遍历树，逐文件比较
    if (is_conflict(head, merge)) {
        // 如果同一文件在两个分支中都有修改，则标记为冲突
        add_conflict_entry(info, head, merge);
        return -1;
    }

    // 合并变更
    merge_file(info, ancestor, head, merge, options);
    return 0;
}

文件级合并（merge_file）

void merge_file(struct traverse_info *info, const struct tree *ancestor,
                const struct tree *head, const struct tree *merge,
                struct merge_options *options) {
    struct file_merge_data data;

    // 从 ancestor、head 和 merge 中获取文件内容
    data.base = get_file_content(ancestor);
    data.local = get_file_content(head);
    data.remote = get_file_content(merge);

    // 执行合并操作
    if (!apply_three_way_merge(&data)) {
        fprintf(stderr, "Conflict: Manual resolution required for %s\n", info->path);
    }
}

4. 冲突处理 (Conflict resolution)

如果三方合并出现冲突，Git 会将冲突区域标记在文件中。例如：

<<<<<<< HEAD
本地修改
=======
远程修改
>>>>>>> branch

源码：merge-recursive.c

 1 int apply_three_way_merge(struct file_merge_data *data) {
 2     // 调用底层差异计算
 3     diff_result = diff_files(data->base, data->local, data->remote);
 4 
 5     if (diff_result.has_conflict) {
 6         // 如果检测到冲突，将冲突标记写入文件
 7         write_conflict_markers(data);
 8         return -1;
 9     }
10 
11     // 合并成功，写入合并结果
12     write_merged_file(data);
13     return 0;
14 }

5. 合并提交

当文件成功合并后，Git 创建一个新的提交，将 HEAD 和目标分支的最新提交作为父提交。

源码：commit.c

int commit_merge(const char *message, struct commit *head, struct commit *merge) {
    struct commit_list parents;

    // 设置父提交（HEAD 和目标分支的最新提交）
    parents.item = head;
    parents.next = merge;

    // 创建合并提交
    create_commit(message, &parents);
    return 0;
}

总结

• 共同祖先查找：merge-base.c
• 差异计算：diff.c
• 三方合并算法：merge-recursive.c
• 冲突标记：在 merge-recursive.c 中完成
• 提交生成：commit.c

源码来源：https://github.com/git/git