15

关于它们是如何工作的，我想知道低级的工作内容：

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

关于安全性，说实话，庞大的 Linux 内核存储库证明了它们的安全性。但我想知道以下几点：

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

编辑

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

Git/diff/补丁详细信息

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

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

可靠性

我很确定 Git 是完全可靠的，因为它确实有完整的提交历史并且可以遍历历史。我想要的是一些关于这方面的学术研究和参考的指针，如果它们存在的话。

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

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

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

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

4

3 回答 3

6

什么会触发合并冲突？

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

git 默认使用递归策略，即3-way merge。大体思路是一样的：如果链接中描述的 3 路合并算法失败，因为来自不同分支的两次提交更改了相同的行，这就是合并冲突。

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

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

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

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

关于用户应该注意的工具是否有任何警告/限制？

至于补丁和差异：不。两者都使用自 1970 年代初就已经存在并且非常强大的算法。只要他们不抱怨，你就可以相当肯定他们做了你想做的事。

话虽如此：git merge尝试自行解决合并冲突。在极少数情况下，这里可能会出错 -此页面有一个接近尾声的示例。

算法是否被证明不会产生错误的结果？如果没有，是否有建议集成测试的实现/论文至少证明它们在经验上是无错误的？

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

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

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

我很确定 Git 是完全可靠的，因为它确实有完整的提交历史并且可以遍历历史。我想要的是一些关于这方面的学术研究和参考的指针，如果它们存在的话。

git 中的提交是带有元数据的树的快照，而不是与相邻版本的差异。补丁和差异根本不参与修订遍历。（但在表面之下一层，git 然后在使用 delta 压缩算法的包文件中组织 blob 。这里的错误很容易发现，因为 git 内部使用 sha1 和来识别文件，如果发生错误，总和会改变。 )

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

git 默认使用 Myers 算法。原始论文解释了为什么它会以这种方式工作。（这不是纯粹的 LCS。）

于 2015-11-09T18:14:46.990 回答
4

diff/patch 格式不安全。=) 因为他们对您的消息来源一无所知。

这是我在 (OMG) 2008 中绘制的格式的描述。 统一差异格式

  1. 当源块中的行不同或在实际源文件中被修改时，会触发合并冲突。源块由不以“+”开头的黄线组成。红色勾勒出补丁程序希望在补丁之前找到此源块的行号。如果这些行已经在历史记录中的某个地方进行了修改，则会出现合并冲突。

  2. 是的，上下文行用于检查补丁是否可以正确应用，以及当行号信息（红色）由于在这些行之前某处插入的东西而不再正确时找到正确的位置。

  3. patch 实用程序对您的代码行为一无所知 - 它只是插入和删除行，在未找到预期行（也可能失败或尝试查找偏移量）或已经修改（合并冲突）时向您发出警告

希望这个解释适用于您的第二个问题。

至于能做什么，我曾经提出过Extensible Changeset Format，这样diff 格式就可以携带额外的数据，用于更智能的补丁工具。我在 2011 年将想法发送到 subversion 邮件列表，但当时那里的热情很高。

我在 Google Code 上记录了这个想法，但它被关闭了，所以现在它被埋在 GitHub 上（没有任何历史记录）： https ://github.com/techtonik/rainforce/blob/wiki/ExtensibleChangesetFormat.md

由于缺乏可以从中受益的实际项目，它没有取得任何进展。实际上，我创建了一个了解文件和目录的补丁格式的扩展版本（或者更好地说是替代版本）。它被用来在 2008 年为 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

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

今天我将添加关于存储库的知识，在应用补丁之前应该失败的测试，对审阅者有用的附加信息（例如检测审查所需的资格和代码级别）以及许多其他想法.. 散列格式以制作连续的区块链从补丁系列中，多级工具检测补丁是否与整个源代码树中的其他更改正交。但这需要资金和不止一人的军队。

于 2015-11-09T19:45:07.997 回答
2
  1. 什么会触发合并冲突？

找到原始版本，两个分支都开始使用的那个。对原始版本运行两个差异，一个在左侧分支提示版本，另一个在右侧。两者在重叠更改块中显示不同更改的任何地方都是 git 拒绝自动解决的冲突。就是这样。

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

合并不需要它，它有两个差异，显示每个原始行在每个提示中结束的位置。它确切地知道在哪里获取和放置更改的行。

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

他们没有。考虑尝试教 git 什么语义适用于何处。如果您没有在恐惧中尖叫，那您就没有这样做:-)

您可以提供自己的合并驱动程序。这简单。如果您有一些想要自动处理的常见特殊情况，那就去做吧。从调用内置驱动程序的简单 shell 脚本开始，然后调用seds 或awks 或任何您可以自动正确处理的冲突。

我很确定 Git 是完全可靠的，因为它确实有完整的提交历史并且可以遍历历史。我想要的是一些关于这方面的学术研究和参考的指针，如果它们存在的话。

Git 的内部结构非常简单。我不是在开玩笑。您可以通过检查来检查模型的可靠性。牢记 dag-of-trees 结构以及合并的运作方式，尝试找到有关其可靠性的具体问题或问题，我认为您会尽快解决任何问题。

如果您要询问其实现操作的可靠性，它是否正确压缩或传输正确的对象以满足推送或获取或诸如此类的要求，则拼写为“git 有错误吗？”。

于 2015-11-10T19:25:42.803 回答