diff/patch是如何工作的？它们安全吗？

Question

关于它们的工作原理，我想了解底层工作细节：

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

关于安全性，说实话，巨大的Linux内核库证明了它们的安全性。但是我想了解以下几点：

1. 用户需要注意哪些与工具有关的提示/限制？
2. 算法已经被证明不会产生错误结果吗？
3. 如果没有，是否有提出集成测试的实现/论文，至少从经验上证明它们是无误的？类似这些论文的内容：BrianKorver和JamesCoplien。
4. 同样，Linux存储库应该足以满足前面提到的问题，但我想了解一些更通用的东西。即使更改了源代码，它也不会改变很多（特别是因为实现的算法和语法限制），但是安全性能够推广到通用文本文件吗？

编辑

好的人们，我在编辑问题，因为问题含糊不清，答案没有涉及细节。

Git/diff/patch细节

统一的差异格式，Git似乎默认使用它，基本上输出三个东西：更改、周围的上下文和与上下文相关的行号。每个这些东西可能会同时更改，也可能不会，所以Git基本上必须处理8种可能情况。

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

可靠性 我非常确定Git是完全可靠的，因为它具有完整的提交历史记录并可以遍历历史记录。如果有的话，我想了解关于此方面的学术研究和参考资料的一些指针。

仍然与此主题相关的是，我们知道Git / diff将文件视为通用文本文件并按行处理。此外，diff使用的LCS算法将生成一个试图最小化更改数量的补丁。

因此，我还想知道以下一些事情： 1. 为什么要使用LCS而不是其他字符串度量算法？ 2. 如果使用LCS，为什么不使用修改后的度量标准版本，该版本考虑底层语言的语法方面？ 3. 如果使用了考虑语法方面的度量标准，它们是否能够提供好处？ 在这种情况下，好处可以是任何东西，例如更干净的“责备日志”。

同样，这些可能是巨大的话题，学术文章也受欢迎。

- cenouro

---

关于第3点，Git是纯文本的。它对代码没有任何了解（除非是为了一些显示目的）。 - MicroVirus

@MicroVirus 我相信你指的是第4点而不是第3点。无论如何，是的，Git是纯文本的，但源代码遵循词法和语法结构。它有结构。例如，在随机生成的大型文本文件上仍然可以使用差异吗？ - cenouro

不，我指的是你第一个枚举中的第三点。关于你评论中的问题，是的，你可以使用Git来跟踪论文写作。只要源代码是基于文本的，Git就可以（相对）良好地工作。但是，Git最适合用于代码。 - MicroVirus

您当前提出的问题不适合在Stack Overflow上发布。 - Andrew C

我没有回答第三组问题的最后两个问题，因为答案显然是基于个人观点的。我的猜测是，由于当前算法已经运行得相当不错，而且一个语言感知的变体需要很多工作（从“我该如何识别一种语言”开始 - 可以查看github的linguist问题来了解即使是正确地完成这一步骤也有多么复杂），因此没有人觉得值得这样做。 - Phillip

Answer 1

什么会触发合并冲突？

首先让我们看一下最简单的git 合并策略，即递归合并：当合并两个分支，比如a和b，它们有一个共同的祖先c时，git会创建一个补丁从提交c到a的头部，并尝试将该补丁应用于b的头部树。如果补丁失败，则会出现合并冲突。

git默认使用递归策略，一种三路合并。总体思路相同：如果链接中描述的三路合并算法失败，因为来自不同分支的两个提交更改了相同的行，那么就会出现合并冲突。

工具是否也使用上下文来应用补丁？

是的。如果补丁文件中存储的行号与实际不符，patch会根据上下文在原始行的几行相邻位置尝试找到正确的行号。

他们如何处理实际上不修改源代码行为的更改？例如，交换函数定义位置。 patch并不智能，无法区分这种更改。它将移动的函数视为添加和删除了几行。如果一个分支上的提交更改了一个函数，而另一个提交移动了未更改的函数，则尝试合并将始终导致合并冲突。

关于工具方面，用户应该注意哪些注意事项/限制？

至于patch和diff：没有。两者使用的算法自上世纪70年代以来就存在，并且非常稳健。只要它们没有抱怨，您可以相当肯定地认为它们已经完成了您的意图。

话虽如此：git merge 试图自行解决合并冲突。在极少数情况下，事情可能会出错 - this page 在其末尾附有示例。

这些算法已经被证明不会生成错误的结果吗？ 如果没有，是否有实现/论文提出了至少在经验上证明它们是无误的集成测试？

在这个背景下，“错误结果”是一个相当不具体的术语；我认为它无法被证明。经验证明，由 diff a b 生成的补丁应用于文件 a 将在任何情况下产生文件 b。

源代码即使被更改，也不会改变太多（特别是因为所实现的算法和语法限制），但安全性能否推广到通用文本文件？

同样，diff/patch/git 不区分源代码和其他文本文件。git 对通用文本文件的处理与对源代码的处理一样。

我很确定Git是完全可靠的，因为它具有完整的提交历史记录并且可以遍历历史记录。如果存在相关的学术研究和参考资料，我希望能得到一些指引。

在git中，提交是树的快照，带有元数据，而不是与相邻版本的差异。补丁和差异根本没有涉及修订遍历。(但在表面以下的一个级别，git会将blob组织成使用增量压缩算法的pack文件。如果出现错误，这里的错误将很容易被发现，因为git在内部使用sha1摘要来标识文件，如果出现错误，摘要将发生变化。)

为什么要使用LCS而不是其他字符串度量算法？

git默认使用Myers算法。原始论文解释了它的工作原理。(它不纯粹是LCS。)

- Phillip

---

你的回答含糊不清。如果可以的话，请改进一下。我也会进一步编辑我的问题，使其更易理解。 - cenouro

确实，就像你的问题一样;-) 但是关于你的每个问题确实还有更多要说的。我会把这个回答变成社区回答，这样其他人也可以改进它。 - Phillip

Answer 2

diff/patch格式不安全。=）因为它们根本不了解您的源代码。

这是我在2008年绘制的格式描述。

1. 合并冲突会在源代码块中的行与实际源文件中的行不同或已修改时触发。源代码块由不以“+”开头的黄色行组成。红色轮廓线标出修补程序在修补之前期望找到此源代码块的行号。如果这些行已在历史记录的某个地方进行了修改，则会产生合并冲突。

2. 是的，上下文行用于检查是否可以正确应用修补程序，还用于在插入到这些行之前的某个位置时查找正确的位置，当行号信息（红色）不再正确时。

3. 修补程序工具不知道您的代码行为-它只插入和删除行，并在未找到预期行（也可以失败或尝试查找偏移量）或它们已经被修改时（合并冲突）给出警告。

希望这个解释对您的第二个问题块有所帮助。

关于可以做些什么，我曾经提出了可扩展变更集格式（Extensible Changeset Format），以便差异格式可以携带附加数据以供更智能的修补工具使用。2011年，我将这个想法发送到Subversion邮件列表，但当时并没有引起太多热情。

我在Google Code上记录了这个想法，但该网站已关闭，所以现在它被埋藏在GitHub上（没有任何历史记录），链接如下： https://github.com/techtonik/rainforce/blob/wiki/ExtensibleChangesetFormat.md 由于缺乏真正受益的项目，它没有得到任何进展。实际上，我创建了一个扩展版本（或者更好地说是替代版本）的补丁格式，它知道文件和目录。它被用于构建Wesnoth的增量更新，http://forums.wesnoth.org/viewtopic.php?f=5&t=20132但我太贪心了，不想将其发布为开源（或者担心无法适当支持该工具，会被某些商业公司分叉并赚大钱）。这是扩展/替代版本的路径格式的样子：

[PatchPlan version 0.1]------------------------------------
* Description   : 
* Old Version   :
* New Version   :
* URL       :
* Patch made by : 
* Comments  :
* Used tools    :
-----------------------------------------------------------
[C ] ... "dir1/dir2/filename.ext" MD5
         N:"dir3/dir4/newfile.ext" MD5
[C ] ... "dir1/dir3/filename.ext" MD5
         P:"dir1/dir3/patchfile.ext.patch" TYPE MD5
[D ] ... "dir1/dir2/filename.ext" MD5
[A ] ... "dir1/dir2/filename.ext"
         N:"dir3/dir4/newfile.ext" MD5
[AD] ... "dir1/dir2/newdirname"
-----------------------------------------------------------

[C ] ... - Status field

         C  - Changed
         D  - Deleted
         A  - Added
         DE - Deleted empty directory
         DD - Deleted directory
         AD - Added directory
         ... - place reserved for flags like overwrite,
               force deletion etc. flags are separated by
               spaces from other fields




"dir1/dir2/filename.ext" - relative path of patched file


MD5    - 32 letters, i.e. cb5bc9f48388568178f24e6294ea782b


N:"dir3/dir4/newfile.ext" MD5
       - path for replacement file relative to directory
         with new files, i.e. temp directory where they
         were extracted, for example

P:"dir3/dir4/patchfile.ext.patch" TYPE MD5
       - path for patch file that should be applied
         TYPE is one of the supported 
         - VPATCH (DIFF, BSDIFF are planned)
       - .patch extensions is not a requirement, but
         merely a convention
       - MD5 in this case is MD5 of the new patched file
         and not of the patch itself


[D ] ... - MD5 of the file to be deleted

鉴于这一点，任何人都可以自己推导出用于比较目录和修补它们、构建二进制补丁、文本补丁等的工具。仍然没有扩展信息的地方，但随着更多的故事出现，可以添加这些信息。当然，我有兴趣参与这种工具的全职开发（或者更确切地说，开源我的自己的工具）。

今天，我会添加关于存储库的知识，应在应用补丁之前失败的测试，对审阅者有用的其他信息（例如检测审查所需的资格和代码水平），以及许多其他想法……使用哈希格式使补丁系列形成连续的块链，多级工具来检测补丁是否正交于整个源代码树中的其他更改。但这需要资金支持和不止一个人的力量。

- anatoly techtonik

Answer 3

1. 什么会触发合并冲突？

找到原始版本，也就是两个分支都开始的那个版本。对比原始版本和左侧分支最新版本以及右侧分支最新版本之间的差异。如果在重叠的变更块中，两个版本显示出不同的变更，则 Git 将拒绝自动解决这些冲突。就是这样。

2. 工具是否还使用上下文来应用补丁？

合并不需要它，它已经有了两个差异，显示每个原始行在每个最新版本中的位置。它知道在哪里获取和放置更改的行。

3. 他们如何处理实际上不修改源代码行为的更改？例如，交换函数定义的位置。

他们不会处理。想想看如何教 git 在哪里适用语义。如果你没有精神上的恐慌，那么你就做错了 :-)

您可以提供自己的合并驱动程序。这很容易。如果您有一些常见的特殊情况要自动处理，请开始编写一个简单的 shell 脚本，调用内置驱动程序，然后使用 sed 或 awk 等自动处理您可以正确处理的冲突。

---

我非常确定 Git 是完全可靠的，因为它拥有完整的提交历史记录并可以遍历历史记录。如果存在相关的学术研究和参考资料，我想了解一下。

Git 的内部结构非常简单。我不是开玩笑。您可以通过检查模型的可靠性来验证它。记住 DAG-of-trees 结构以及合并操作，尝试找到关于其可靠性的具体问题或问题，我认为您将像他们形成一样快速解决任何问题。

如果您的问题是关于其实现操作的可靠性，例如它是否正确压缩或传输正确的对象以满足推送或获取等操作，那么这被称为“Git 是否有 bug？”。

- jthill