从 Git 原理上解析， Git 是如何在代码合并时发现冲突的。
引言
写这篇文章的起因源于今年初去年初的一次面试，当时正在「印象笔试」面试 macOS 工程师，面试官是他们 macOS & iOS 端的负责人，在考察 Git 的时候突然问了这么一个问题：
Git 是如何发现冲突的，能从原理上进行说明吗？它在进行检测的时候，是对本地和远程全部进行匹配吗，如果不是怎么做的？
非常有意思的问题，所以写这篇文章来从 Git 的原理上分析，它究竟是如何发现并定位冲突的，从而反向推出面试官想要考察的知识点。
Git 如何存储数据？
首先说一下 Git 是如何储存数据的，Git 作为一个内容寻址文件系统，本质上是一个键值对数据库（key-value data store）。每存储一份数据，都会返回一个 40 位的 Hash 值作为键，通过这个键，我们就能找到所存储的数据。其中 Hash 值的前 2 位作为目录，后 38 位为文件名。文件的内容就是键值对的值 ，也就是 Git 存储的一系列数据。
Git 中的文件有三种状态：
- 未暂存
- 已暂存
- 已提交
Git 会存储 已暂存 和 已提交 的文件。同时，当我们提交数据时，当前的commit的注释、作者信息等也会被一并保存下来。
Git 通过键值对的方式存储数据，Git 存储的对象有四种:
- 提交对象
- 标签对象
- 树对象
- 数据对象
提交对象
每次向 Git 仓库中提交文件时，Git 会生成一个提交对象，用以保存当前提交的信息（包括 commit、author、committer等）和指向树对象的索引。这个提交对象的保存方式也是以 Hash 值为文件名的文件。
标签对象
Git 中的标签主要分为两种，轻量标签（lightweight）与附注标签（annotated）。这里的标签对象主要指附注标签，因为轻量标签只是一个特定提交的引用，而附注标签却是存储在 Git 数据库中的一个完整对象。附注标签中包含打标签者的名字、电子邮件地址、日期时间以及标签信息，是可以被校验（如果你对这个感兴趣，可以去了解使用 GNU Privacy Guard （GPG）对附注标签进行签名与验证 ）。其保存形式与提交对象相同。
树对象
Git 在每次提交时，会将暂存区的所有数据保存起来，这时会产生一个 树对象 ，记录了在提交前，处于暂存区中的每个文件的状态（这个记录并非将数据都拷贝到当前树对象的文件中，而是记录了暂存区中每个文件的数据对象的 键 ）。在不包含附注标签的情况下，每个 Git 仓库中包含 n + 2 个对象，分别是 1 个提交对象、1 个 树对象和 n 个数据对象。而树对象主要就是记录这三个数据对象的索引值和目录结构。
数据对象
Git 使用数据对象来记录每一个文件的数据。比如将一个文件添加到暂存区（index）中，这时，在 objects 目录下就会产生一个数据对象。
Git 就是将所需要用到的数据转为这四种对象，并且以 Hash 值为文件名的文件的形式，保存在 .git/objects 中。
Git 如何检测文件改动并定位？
检测改动
每当所储存的文件发生改动，其对应的 Hash 值就会产生变化，这个 Hash 值可以理解为一个文件对象的特定版本，对比远程仓库与本地仓库同一文件的 Hash 值，即可知道该文件是否发生曾过改动。
进行定位
我们可以通过对比 Hash 值的方式，很轻松的知道文件是否有过改动，但如何定位到改动具体发生的位置呢？
通常你可以使用 git diff 命令来对比文件的不同，diff 操作并不会显示完整的文件内容，只会标记出那些实际上修改的部分。这些部分除了实际更改的代码行，还有一个特定的 “上下文环境”，例如那些改变之前和之后的差别，能让你更容易理解在特定的上下文环境中这个改变的具体含义。那么 diff 操作是如何找到并标记出实际的修改呢？
diff 就是目标文本和源文本之间的区别，也就是将源文本变成目标文本所需要的操作。先来看下 diff 做了哪些事情，在测试工程中使用 git diff 命令
文件元数据
图中的 index 表示文件的元数据（Metadata），7defa7d和161da96表示两个文件的 hashes，相当于它们的 HashID，这个 HashID 就代表了一个文件对象的特定版本，最后的一串数字代表了一个文件的模式（100644 代表它是一个普通的文件，100755 表示一个可执行文件，120000 仅仅是一符号链接）。
标记 a/b
我们可以看到在元数据的下面两行，分别出现了 a 和 b 两个标识，它标识文件的两个不同版本。为了区分它们，a和 b 都被赋予了它们特有的符号：对于版本 a，它的符号是一个减号（“-”）；而对于版本 b ，它会使用一个加号（“+”）。
区块标头
Git 会告诉你哪些行存在差异，它们被显示在两个 “@@” 符号之前，以上图示例中所表示的含义为：
- 来自文件 a （标记为 “-”），从第 73 行开始之后的 7 行代码。
- 来自文件 b （标记为 “+”），从第 73 行开始之后的 10 行代码。
而”@@”后面的紧跟着的部分就是其上下文信息。
具体改动
在每一个被改动过的代码行之前都会前置一个 “+” 或是 “-” 符号。这些符号可以帮助你准确了解版本 a 和 版本 b ，例如前置了 “-” 符号的行就代表来自版本 a，反之带有符号 “+” 的行就代表来自于版本 b。
1 | - (void)tableView:(UITableView *)tableView didSelectRowAtIndexPath:(NSIndexPath *)indexPath { |
Myers 算法
Git 为我们生成的 diff 是很直观易懂的，”+”和”-“的区域划分非常明显，一看就知道我们对文件进行了哪些改动，但这实际上涉及到一个复杂的算法问题。即使是很小的改动，a-b之间所产生的 diff 都可能有无穷多种。所以，我们需要一个算法，生成直观的 diff，除此之外，diff 还需要尽可能的简短，只显示实际的改动。那么，如何找到最直观最简短的 diff ，就是我们的问题。
Myers 算法 是一个差异算法，出自尤金·迈尔斯（Eugene W. Myers）之手，是一个能在大部分情况产生最直观最简短 diff 的一个算法，也是一个典型的「动态规划」算法，父问题的最优解归结为子问题的最优解，也就是「最优子结构」。要知道 A1 的最优坐标，必须先要知道 A2 的最优坐标，要知道 A2 的最优坐标，必须知道 A3 的结果，以此类推。
寻找 diff 的过程可以被表示为图搜索，寻找 diff 实际上就是个图搜索的问题，至于为什么，我猜你肯定不想看数学证明。所以这里直接给出结论：最直观最简短的 diff = 寻找图的最短路径，这也是Myers 算法的基本思想。
Myers算法背后的想法非常简单：如图对比两个字符串ABCABBA 和 CBABAC之间的差异。我们希望以尽可能少的步骤从（0,0）移动到（7,6）（右下）。「移动」是向右（从a删除）或向下（从b 插入）的单个步骤。图中我们从a移动到b进行的最多移动数是13：两个字符串的总长度 7 + 6。
Myers算法就是提供了找到最短路径的一种策略，其会通过广度优先搜索（BFS）来探索图表中每条可能的路线，并在到达最终位置时立即停止。在这个过程中，Myers算法做了三件事：
- 找到最短路径，以将
a转换为b，源文本变成目标文本 - 找到源文本变成目标文本所需的最少编辑量
- 通过回溯，来反向查看记录的数据，找出导致结果的单个路径，也就是具体改动内容
然而标准的 Myers 算法有一个很大的缺点，虽然其速度很快，但是空间消耗很大，如果输入文件比较大，其空间开销是不能接受的。所以，Git 真正用的是标准 Myers 算法 的一个变体，这个变体需要的空间开销要小得多。
想要了解具体的 Myers 算法的实现，可以参考他的论文。
得出结论
现在我们可以得出结论，Git 是如何发现代码冲突并进行定位的了。
1.首先，比对本次提交与远程仓库文件的 Hash 值，找到发生改动的对象。
2.检查改动文件的前后版本，利用 Myers 的变种算法找到改动的增减位置，输出具体的改动信息。
3.定位冲突点，找出在相同元数据 hashes 的基础上进行的同位置改动。换句话说，就是在同一特定版本的基础上，进行的相同位置的改动。
面试官的考察点
由此我们不难反推出面试官的这个问题究竟想要考察我们那些知识点，或者说可能会考察哪些知识点
- Git 储存原理
- Git 对象结构
- Git 合并的工作流
- git diff 执行原理
- 动态规划
- 广度优先搜索
我想最终面试官是希望从 Git 原理考察引出对算法，尤其是「动态规划」算法的考察，一步一步深入，最后诱导面试者回答出自己想要的答案。
参考
Git从原理到解决冲突
Git存储数据的原理
Git 基础 - 打标签
用 diff 来检查改动
Git 是怎样生成 diff 的：Myers 算法
The Myers diff algorithm: part 1
The Myers diff algorithm: part 2
The Myers diff algorithm: part 3