git - 差异/补丁如何工作以及它们的安全性如何？

Question

关于它们是如何工作的，我想知道低级工作的东西:

1. 什么会触发 merge 冲突？
2. 上下文是否也被工具使用以应用补丁？
3. 他们如何处理实际上并未修改源代码行为的更改？例如，交换函数定义位置。

关于安全性，说实话，巨大的 Linux 内核存储库是其安全性的证明。但我想知道以下几点:

1. 对于用户应了解的工具，是否有任何注意事项/限制？
2. 算法是否已被证明不会产生错误的结果？
3. 如果没有，是否有建议集成测试的实现/论文至少证明它们在经验上没有错误？类似这些论文的内容BrianKorver和 JamesCoplien .
4. 同样，对于前一点，Linux 存储库应该足够了，但我想知道更通用的东西。源代码即使更改也不会发生太大变化(特别是因为实现的算法和语法限制)，但是安全性可以推广到通用文本文件吗？

编辑

好的，我正在编辑，因为问题含糊不清，答案没有解决细节问题。

Git/差异/补丁详情

Git 似乎默认使用的统一差异格式基本上输出三样东西:更改、更改周围的上下文以及与上下文相关的行号。这些事情中的每一个可能会或可能不会同时发生变化，因此 Git 基本上必须处理 8 种可能的情况。

例如，如果在上下文之前添加或删除了行，行号将不同；但是如果上下文和更改仍然相同，那么 diff 可以使用上下文本身来对齐文本并应用补丁(我不知道这是否确实发生了)。现在，其他情况会发生什么？我想知道 Git 如何决定自动应用更改以及何时决定发出错误并让用户解决冲突的详细信息。

可靠性

我非常确定 Git 是完全可靠的，因为它确实拥有完整的提交历史记录并且可以遍历历史记录。我想要的是一些关于学术研究和引用的指示，如果它们存在的话。

仍然与这个主题有点相关，我们知道 Git/diff 将文件视为通用文本文件并在行上工作。此外，diff 采用的 LCS 算法将生成一个补丁，尽量减少更改的数量。

所以这里有一些我也想知道的事情:

1. 为什么使用 LCS 而不是其他字符串度量算法？
2. 如果使用 LCS，为什么不使用考虑了底层语言语法方面的修改后的度量标准版本？
3. 如果使用这种考虑了语法方面的指标，它们能带来好处吗？在这种情况下，好处可以是任何东西，例如，更清晰的“blame 日志”。

同样，这些话题可能很大，欢迎发表学术文章。

Answer 1

What will trigger a merge conflict?

我们来看最简单的git的merge strategies ，递归，首先:当 merge 两个分支时，比如说a和b，它们有一个共同的祖先c， git 创建一个补丁，从提交 c 到 a 头部的提交广告，并尝试将该补丁应用于 b.如果补丁失败，那就是 merge 冲突。

git 默认使用递归 策略，3-way merge .总体思路是相同的:如果链接中描述的 3 向 merge 算法失败，因为来自不同分支的两个提交更改了相同的行，那就是 merge 冲突。

Is the context also used by the tools in order to apply the patch?

是的。如果补丁没有应用到 diff 文件中存储的确切行号，补丁会根据上下文尝试找到与原始行相邻几行的正确行。

How do they deal with changes that do not actually modify source code behavior? For example, swapping function definition places.

补丁不是智能的，它不能区分这样的变化。它将移动的函数视为几行添加和几行删除。如果一个分支上的提交改变了一个函数，而另一个分支上的提交移动了未改变的部分，那么 merge 的尝试总是会给你带来 merge 冲突。

Are there any caveats/limitations regarding the tools that the user should be aware of?

至于 patch 和 diff:否。两者都使用自 1970 年代初就存在的算法，并且非常稳健。只要他们不提示，您就可以相当确定他们按照您的意愿行事。

也就是说:git merge 尝试自行解决 merge 冲突。在极少数情况下，这里的事情可能会出错 - this page有一个接近尾声的例子。

Have the algorithms been proven to not generate wrong results? If not, are there implementations/papers proposing integration testing that at least prove them to be error-free empirically?

“错误的结果”在这种情况下是一个相当不明确的术语；我会声称它无法被证明。经验证明，将 diff a b 生成的补丁应用于文件 a 无论如何都会生成文件 b。

Source code, even when changed, will not change much (specially because of the algorithm implemented and syntax restrictions), but can the safety be generalized to generic text files?

同样，diff/patch/git 不区分源代码和其他文本文件。 git 在通用文本文件上的表现与在源代码上的表现一样好。

I'm pretty much sure the Git is fully reliable since it do have the full history of commits and can traverse history. What I would like is some pointers to academic research and references regarding this, if they exist.

git 中的提交是带有元数据的树的快照，而不是与相邻版本的差异。 patch 和 diff 根本不参与修订遍历。 (但是在表面之下一层，git 然后在 pack files that do use a delta compression algorithm 中组织 blob。这里的错误很容易发现，因为 git 在内部使用 sha1 总和来识别文件，如果发生错误，总和会改变。)

Why is LCS used instead of other string metric algorithms?

git 默认使用 Myers 算法。 The original paper解释了为什么它以这种方式工作。 (它不是纯粹的濒海战斗舰。)