diff/patch 如何工作以及它们的安全性如何？
How do diff/patch work and how safe are they?
关于它们是如何工作的，我想知道低级工作的东西：
- 什么会触发合并冲突？
- 上下文是否也被工具使用以应用补丁？
- 他们如何处理实际上并未修改源代码行为的更改？例如，交换函数定义位置。
关于安全，说实话，巨大的 Linux 内核存储库是他们安全的证明。但我想知道以下几点：
- 是否有任何caveats/limitations用户应该了解的工具？
- 算法是否已被证明不会产生错误的结果？
- 如果没有，是否有 implementations/papers 提议集成测试至少证明它们在经验上没有错误？像这些论文的内容BrianKorver and JamesCoplien.
- 同样，Linux 存储库对于前一点应该足够了，但我想知道更通用的东西。源代码即使更改，也不会发生太大变化（特别是因为实现的算法和语法限制），但是安全性可以推广到通用文本文件吗？
编辑
好的，我正在编辑，因为问题含糊不清，答案没有解决细节问题。
Git/diff/patch 详情
Git 似乎默认使用的统一差异格式基本上输出三样东西：更改、更改周围的上下文以及与上下文相关的行号。这些东西中的每一个都可能会或可能不会同时更改，所以 Git 基本上必须处理 8 种可能的情况。
例如，如果在上下文之前添加或删除了行，行号将不同；但是如果上下文和更改仍然相同，那么 diff 可以使用上下文本身来对齐文本并应用补丁（我不知道这是否确实发生了）。现在，其他情况会发生什么？我想知道 Git 如何决定自动应用更改以及何时决定发出错误并让用户解决冲突的详细信息。
可靠性
我非常确定 Git 是完全可靠的，因为它确实具有完整的提交历史记录并且可以遍历历史记录。我想要的是一些关于学术研究和参考的指针，如果它们存在的话。
仍然与这个主题有点相关，我们知道 Git/diff 将文件视为通用文本文件并在行上工作。此外，diff 使用的 LCS 算法将生成一个补丁，以尽量减少更改次数。
所以这里有一些我也想知道的事情：
- 为什么使用 LCS 而不是其他字符串度量算法？
- 如果使用 LCS，为什么不使用确实考虑了基础语言语法方面的度量的修改版本？
- 如果使用这样一个考虑语法方面的指标，它们能带来好处吗？在这种情况下，好处可以是任何东西，例如，清洁工 "blame log".
同样，这些话题可能很大，欢迎发表学术文章。
What will trigger a merge conflict?
先看最简单的git的merge strategies，recursive，首先：合并两个分支时，说a 和 b，它们有一个共同的祖先 c，git 创建一个补丁以从提交 c 到 a 头部的提交广告，并尝试将该补丁应用于 b 头部的树.如果补丁失败，那就是合并冲突。
git 默认使用 递归 策略，3-way merge。总体思路是相同的：如果 link 中描述的 3 向合并算法失败，因为来自不同分支的两个提交更改了相同的行，那就是合并冲突。
Is the context also used by the tools in order to apply the patch?
是的。如果补丁没有应用到差异文件中存储的确切行号，补丁会根据上下文尝试找到与原始行相邻几行的正确行。
How do they deal with changes that do not actually modify source code behavior? For example, swapping function definition places.
补丁不智能，无法区分此类变化。它将移动的函数视为几行添加和几行删除。如果一个分支上的提交改变了一个函数，而另一个分支上的提交移动了未改变的部分，那么尝试合并总是会给你带来合并冲突。
Are there any caveats/limitations regarding the tools that the user should be aware of?
至于 patch 和 diff：否。两者都使用自 1970 年代初以来就存在的算法，并且非常可靠。只要他们不抱怨，您就可以相当确定他们按照您的意愿行事。
也就是说：git 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?
"wrong results" 在这种情况下是一个相当不明确的术语；我会声称它无法被证明。经验证明，将 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 解释了为什么它会这样工作。 （这不是纯粹的濒海战斗舰。）
diff/patch 格式不安全。 =) 因为他们对您的消息来源一无所知。
这里是我在(OMG)2008画的格式说明。
当源块中的行在实际源文件中不同或被修改时，会触发合并冲突。源块由不以“+”开头的黄线组成。红色勾勒出补丁程序希望在补丁之前找到此源块的行号。如果这些行已经在历史记录中的某处进行了修改，则会出现合并冲突。
是的，上下文行用于检查补丁是否可以正确应用，以及当行号信息（红色）由于之前某处插入的内容而不再正确时找到正确的位置这些行。
patch 实用程序对您的代码行为一无所知 - 它只是插入和删除行，在未找到预期的行（也可能失败或尝试查找偏移量）或当它们已经被修改（合并冲突）
希望这个解释对你的第二个问题有用。
至于可以做些什么，我曾经想出Extensible Changeset Format，让diff格式可以携带额外的数据，用于更智能的补丁工具。我sent idea to subversion mailing list in 2011，但当时那里的热情很高
我在 Google 代码上记录了这个想法，但它被关闭了，所以现在它被埋在了 GitHub 上（没有任何历史记录）：
https://github.com/techtonik/rainforce/blob/wiki/ExtensibleChangesetFormat.md
由于缺乏可以从中受益的实际项目，它没有取得任何进展。实际上，我创建了一个知道文件和目录的补丁格式的扩展版本（或者更好的说法是替代版本）。它曾用于在 2008 年为 Wesnoth http://forums.wesnoth.org/viewtopic.php?f=5&t=20132 构建增量更新，但我太贪心了，没有将它发布到开源（或者担心我无法正确支持该工具，它会被一些商业分叉会赚很多钱的公司）。下面是 extended/alternative 版本的路径格式：
[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
鉴于此，任何人都可以自己派生出用于比较目录和修补它们、构建二进制补丁、文本补丁等的工具。仍然没有扩展信息的位置，但是随着更多故事的出现，可以添加这些信息。我当然有兴趣参与此类工具的全职开发（或者更确切地说，我自己的开源工具）。
今天我将添加有关存储库的知识、在应用补丁之前应该失败的测试、对审阅者有用的其他信息（例如检测审阅所需的资格和代码级别）以及许多其他想法..哈希格式来自补丁系列的连续区块链，用于检测补丁是否与整个源代码树中的其他更改正交的多级工具。但这需要资金和不止一个人的军队。
- What will trigger a merge conflict?
找到原始版本，即两个分支都以其开头的版本。 运行 与原始版本的两个差异，一个在左侧分支提示版本，另一个在右侧。两者在重叠变化块中显示不同变化的任何地方都是冲突 git 拒绝自动解决。就是这样。
- Is the context also used by the tools in order to apply the patch?
Merge 不需要它，它有两个差异，显示每个原始行在每个提示中结束的位置。它确切地知道在哪里获取和放置更改的行。
- How do they deal with changes that do not actually modify source code behavior? For example, swapping function definition places.
他们没有。考虑尝试教 git 哪些语义适用于何处。如果你没有在精神上惊恐地尖叫，那你就没有这样做:-)
您可以提供自己的合并驱动程序。这简单。如果您有一些常见的特殊情况需要自动处理，那就去做吧。从调用内置驱动程序的简单 shell 脚本开始，然后是 seds 或 awks 或任何您可以自动正确处理的冲突。
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的内部结构非常简单。我不是在开玩笑。您可以通过检查来检查模型的可靠性。记住 dag-of-trees 结构和合并操作的方式，试着找到一个具体的问题或关于它的可靠性的问题，我想你会尽快解决任何问题。
如果您要问的是其实施操作的可靠性，它是否正确压缩或传输正确的对象以满足推送或获取或诸如此类的要求，则拼写为 "does git have bugs?"。
关于它们是如何工作的，我想知道低级工作的东西：
- 什么会触发合并冲突？
- 上下文是否也被工具使用以应用补丁？
- 他们如何处理实际上并未修改源代码行为的更改？例如，交换函数定义位置。
关于安全，说实话，巨大的 Linux 内核存储库是他们安全的证明。但我想知道以下几点：
- 是否有任何caveats/limitations用户应该了解的工具？
- 算法是否已被证明不会产生错误的结果？
- 如果没有，是否有 implementations/papers 提议集成测试至少证明它们在经验上没有错误？像这些论文的内容BrianKorver and JamesCoplien.
- 同样，Linux 存储库对于前一点应该足够了，但我想知道更通用的东西。源代码即使更改，也不会发生太大变化（特别是因为实现的算法和语法限制），但是安全性可以推广到通用文本文件吗？
编辑
好的，我正在编辑，因为问题含糊不清，答案没有解决细节问题。
Git/diff/patch 详情
Git 似乎默认使用的统一差异格式基本上输出三样东西：更改、更改周围的上下文以及与上下文相关的行号。这些东西中的每一个都可能会或可能不会同时更改，所以 Git 基本上必须处理 8 种可能的情况。
例如，如果在上下文之前添加或删除了行，行号将不同；但是如果上下文和更改仍然相同，那么 diff 可以使用上下文本身来对齐文本并应用补丁（我不知道这是否确实发生了）。现在，其他情况会发生什么？我想知道 Git 如何决定自动应用更改以及何时决定发出错误并让用户解决冲突的详细信息。
可靠性
我非常确定 Git 是完全可靠的，因为它确实具有完整的提交历史记录并且可以遍历历史记录。我想要的是一些关于学术研究和参考的指针，如果它们存在的话。
仍然与这个主题有点相关，我们知道 Git/diff 将文件视为通用文本文件并在行上工作。此外，diff 使用的 LCS 算法将生成一个补丁，以尽量减少更改次数。
所以这里有一些我也想知道的事情：
- 为什么使用 LCS 而不是其他字符串度量算法？
- 如果使用 LCS，为什么不使用确实考虑了基础语言语法方面的度量的修改版本？
- 如果使用这样一个考虑语法方面的指标，它们能带来好处吗？在这种情况下，好处可以是任何东西，例如，清洁工 "blame log".
同样，这些话题可能很大，欢迎发表学术文章。
What will trigger a merge conflict?
先看最简单的git的merge strategies，recursive，首先：合并两个分支时，说a 和 b，它们有一个共同的祖先 c，git 创建一个补丁以从提交 c 到 a 头部的提交广告，并尝试将该补丁应用于 b 头部的树.如果补丁失败，那就是合并冲突。
git 默认使用 递归 策略，3-way merge。总体思路是相同的：如果 link 中描述的 3 向合并算法失败，因为来自不同分支的两个提交更改了相同的行，那就是合并冲突。
Is the context also used by the tools in order to apply the patch?
是的。如果补丁没有应用到差异文件中存储的确切行号，补丁会根据上下文尝试找到与原始行相邻几行的正确行。
How do they deal with changes that do not actually modify source code behavior? For example, swapping function definition places.
补丁不智能，无法区分此类变化。它将移动的函数视为几行添加和几行删除。如果一个分支上的提交改变了一个函数，而另一个分支上的提交移动了未改变的部分，那么尝试合并总是会给你带来合并冲突。
Are there any caveats/limitations regarding the tools that the user should be aware of?
至于 patch 和 diff：否。两者都使用自 1970 年代初以来就存在的算法，并且非常可靠。只要他们不抱怨，您就可以相当确定他们按照您的意愿行事。
也就是说：git 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?
"wrong results" 在这种情况下是一个相当不明确的术语；我会声称它无法被证明。经验证明，将 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 解释了为什么它会这样工作。 （这不是纯粹的濒海战斗舰。）
diff/patch 格式不安全。 =) 因为他们对您的消息来源一无所知。
这里是我在(OMG)2008画的格式说明。
当源块中的行在实际源文件中不同或被修改时，会触发合并冲突。源块由不以“+”开头的黄线组成。红色勾勒出补丁程序希望在补丁之前找到此源块的行号。如果这些行已经在历史记录中的某处进行了修改，则会出现合并冲突。
是的，上下文行用于检查补丁是否可以正确应用，以及当行号信息（红色）由于之前某处插入的内容而不再正确时找到正确的位置这些行。
patch 实用程序对您的代码行为一无所知 - 它只是插入和删除行，在未找到预期的行（也可能失败或尝试查找偏移量）或当它们已经被修改（合并冲突）
希望这个解释对你的第二个问题有用。
至于可以做些什么，我曾经想出Extensible Changeset Format，让diff格式可以携带额外的数据，用于更智能的补丁工具。我sent idea to subversion mailing list in 2011，但当时那里的热情很高
我在 Google 代码上记录了这个想法，但它被关闭了，所以现在它被埋在了 GitHub 上（没有任何历史记录）： https://github.com/techtonik/rainforce/blob/wiki/ExtensibleChangesetFormat.md
由于缺乏可以从中受益的实际项目，它没有取得任何进展。实际上，我创建了一个知道文件和目录的补丁格式的扩展版本（或者更好的说法是替代版本）。它曾用于在 2008 年为 Wesnoth http://forums.wesnoth.org/viewtopic.php?f=5&t=20132 构建增量更新，但我太贪心了，没有将它发布到开源（或者担心我无法正确支持该工具，它会被一些商业分叉会赚很多钱的公司）。下面是 extended/alternative 版本的路径格式：
[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
鉴于此，任何人都可以自己派生出用于比较目录和修补它们、构建二进制补丁、文本补丁等的工具。仍然没有扩展信息的位置，但是随着更多故事的出现，可以添加这些信息。我当然有兴趣参与此类工具的全职开发（或者更确切地说，我自己的开源工具）。
今天我将添加有关存储库的知识、在应用补丁之前应该失败的测试、对审阅者有用的其他信息（例如检测审阅所需的资格和代码级别）以及许多其他想法..哈希格式来自补丁系列的连续区块链，用于检测补丁是否与整个源代码树中的其他更改正交的多级工具。但这需要资金和不止一个人的军队。
- What will trigger a merge conflict?
找到原始版本，即两个分支都以其开头的版本。 运行 与原始版本的两个差异，一个在左侧分支提示版本，另一个在右侧。两者在重叠变化块中显示不同变化的任何地方都是冲突 git 拒绝自动解决。就是这样。
- Is the context also used by the tools in order to apply the patch?
Merge 不需要它，它有两个差异，显示每个原始行在每个提示中结束的位置。它确切地知道在哪里获取和放置更改的行。
- How do they deal with changes that do not actually modify source code behavior? For example, swapping function definition places.
他们没有。考虑尝试教 git 哪些语义适用于何处。如果你没有在精神上惊恐地尖叫，那你就没有这样做:-)
您可以提供自己的合并驱动程序。这简单。如果您有一些常见的特殊情况需要自动处理，那就去做吧。从调用内置驱动程序的简单 shell 脚本开始，然后是 seds 或 awks 或任何您可以自动正确处理的冲突。
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的内部结构非常简单。我不是在开玩笑。您可以通过检查来检查模型的可靠性。记住 dag-of-trees 结构和合并操作的方式，试着找到一个具体的问题或关于它的可靠性的问题，我想你会尽快解决任何问题。
如果您要问的是其实施操作的可靠性，它是否正确压缩或传输正确的对象以满足推送或获取或诸如此类的要求，则拼写为 "does git have bugs?"。