git - git如何将Blob与提交树中的文件匹配？

Question

Chapter 3.1 of the the Git book明确指出，只有暂存文件必须作为blob存储在提交树中。

如果像提交对象一样，blob获得了对其内容唯一的哈希ID，那么Git如何设法跟踪跨提交的blob与文件之间的对应关系？由于提交文件的内容不同，因此它们在不同提交中的哈希ID无法匹配。



一个简单的例子：

假设我只是创建了一个没有提交的空仓库。我创建一个文件README.md，暂存并提交。 Git存储一个树对象，该树对象的Blob由README.md内容的哈希标识。

假设我修改了README.md，进行了阶段提交。 Git存储一个树对象，该树对象的Blob由README.md的已修改内容的哈希标识。自然，我们可以期望第二个哈希与第一个提交树中标识README.md的blob的哈希不同。

Git将如何回答有关README.md历史记录的请求？

git log README.md

我的直觉是，它将遍历提交历史并比较相关的Blob，但是我看不到Git如何知道这些Blob对应于同一文件的不同版本，除非是琐碎的情况。

Answer 1

这实际上是一个很好的问题。

提交的内部存储形式部分相关，因此让我们考虑一下。实际上，单个提交很小。这是来自Git的Git存储库中的一个，即commit b5101f929789889c2e536d915698f58d5c5c6b7a：

$ git cat-file -p b5101f929789889c2e536d915698f58d5c5c6b7a | sed 's/@/ /'
tree 3f109f9d1abd310a06dc7409176a4380f16aa5f2
parent a562a119833b7202d5c9b9069d1abb40c1f9b59a
author Junio C Hamano <gitster pobox.com> 1548795295 -0800
committer Junio C Hamano <gitster pobox.com> 1548795295 -0800

Fourth batch after 2.20

Signed-off-by: Junio C Hamano <gitster pobox.com>

（sed 's/@/ /'也许是为了减少Junio Hamano必须获得的电子邮件垃圾邮件的数量：)）。如您所见，提交对象通过另一个提交的哈希ID a562a11983...引用其父提交对象。它还通过哈希ID引用树对象，并且树对象的哈希ID以3f109f9d1a开头。我们也可以使用git cat-file -p来查看这个树对象：

$ git cat-file -p 3f109f9d1a | head
100644 blob de1c8b5c77f7566d9e41949e5e397db3cc1b487c    .clang-format
100644 blob 42cdc4bbfb05934bb9c3ed2fe0e0d45212c32d7a    .editorconfig
100644 blob 9fa72ad4503031528e24e7c69f24ca92bcc99914    .gitattributes
040000 tree 7ba15927519648dbc42b15e61739cbf5aeebf48b    .github
100644 blob 0d77ea5894274c43c4b348c8b52b8e665a1a339e    .gitignore
100644 blob cbeebdab7a5e2c6afec338c3534930f569c90f63    .gitmodules
100644 blob 247a3deb7e1418f0fdcfd9719cb7f609775d2804    .mailmap
100644 blob 03c8e4c613015476fffe3f1e071c0c9d6609df0e    .travis.yml
100644 blob 8c85014a0a936892f6832c68e3db646b6f9d2ea2    .tsan-suppressions
100644 blob 536e55524db72bd2acf175208aef4f3dfc148d42    COPYING

（树上有很多数据，所以我只在这里复制了前十行）。

在树内部，您可以看到模式（100644），类型（blob，这是模式所隐含的，也记录在内部Git对象中；它实际上没有存储在树对象中），哈希ID（< cc>）和blob的名称（de1c8b5c77f...）。您还可以看到.clang-format可以引用其他tree对象，就像tree子树一样。

如果我们使用这个特定的Blob对象哈希ID，我们也可以通过哈希ID查看该对象的内容：

$ git cat-file -p de1c8b5c77f | head
# This file is an example configuration for clang-format 5.0.
#
# Note that this style definition should only be understood as a hint
# for writing new code. The rules are still work-in-progress and does
# not yet exactly match the style we have in the existing code.

# Use tabs whenever we need to fill whitespace that spans at least from one tab
# stop to the next one.
#
# These settings are mirrored in .editorconfig.  Keep them in sync.

（同样，由于文件很长，我已将副本截断了10行）。

只是为了说明，我们也来看看.github子树：

$ git cat-file -p 7ba15927519648dbc42b15e61739cbf5aeebf48b
100644 blob 64e605a02b71c51e9f59c429b28961c3152039b9    CONTRIBUTING.md
100644 blob adba13e5baf4603de72341068532e2c7d7d05f75    PULL_REQUEST_TEMPLATE.md

然后，Git所做的就是根据需要递归地读取提交中的树对象。 Git会将它们读入一个称为索引或缓存的数据结构中。 （从内存的角度来讲，从技术上讲，这是缓存的数据结构，尽管Git文档倾向于在何时使用哪个名称上有些松懈。）因此，例如，通过读取commit .github构建的缓存会说，名称b5101f929789889c2e536d915698f58d5c5c6b7a具有模式.clang-format和blob哈希100644，而名称de1c8b5c77f7566d9e41949e5e397db3cc1b487c具有模式.github/CONTRIBUTING.md和blob-hash 100644。

请注意，实际上，各种名称组件（64e605a02b71c51e9f59c429b28961c3152039b9加.github）已加入到内存缓存中。 （以磁盘格式，通过算法欺骗将它们压缩。）

内存缓存可帮助Git匹配文件名

最后，是内部（内存中的）高速缓存保存<文件名，文件模式，blob哈希>元组。如果您要求Git将提交CONTRIBUTING.md与其他提交进行比较，则Git还将另一个提交读入内存缓存中。该其他高速缓存具有一个名为b5101f929789889c2e536d915698f58d5c5c6b7a的条目，或者没有。

如果两个提交的文件都具有相同的名称，则Git假定（出于这一比较的目的，Git现在正在执行此操作，请参见下文），这些文件是同一文件。不管blob哈希是否相同，都是如此。

我们在这里回答的真正问题与身份有关。在版本控制系统中，文件的身份确定该文件在两个不同版本中是否为“同一”文件（但是版本控制系统本身定义了版本）。正如this Wikipedia article on the thought experiment about the Ship of Thesus中概述的那样，这与身份的基本哲学问题有关：我们如何知道某个人，甚至某个人，是我们认为的是谁或什么？如果您在表弟鲍勃（Bob）很小的时候遇到了他，并且又遇到了一个名叫鲍勃（Bob）的人，他是您的表弟吗？你和他那时很小。现在，您越来越大，年龄也越来越长。在现实世界中，我们从环境中寻求线索：鲍勃（Bob）是父母的兄弟姐妹的孩子吗？如果是这样，即使鲍勃（和您）现在看起来很不一样，鲍勃可能就是您很久以前见过的表兄。

Git当然不会做任何事情。在大多数情况下，两个文件都被命名为.github/CONTRIBUTING.md的简单事实足以将它们标识为“同一文件”。名称相同，到此完成。

.github/CONTRIBUTING.md提供额外的服务

在日常开发中，有时有时需要重命名文件。出于某些原因，名为git diff的文件可能会重命名为a/b.c或d/e.f。

假设我们正在提交d/e.c，文件名为a123456。然后，我们提交a/b.c。第二个提交没有f789abc，但是确实有a/b.c。 Git会简单地从索引（缓存的磁盘形式）和工作树中删除d/e.f，并将新的a/b.c填充到我们的索引和工作树中，一切都很好。

但是假设我们要求Git将d/e.f与a123456进行比较。 Git可以告诉我们：要将f789abc更改为a123456，请删除f789abc并使用这些内容创建一个新的a/b.c。这就是d/e.f所做的，足够了。但是，如果内容完全匹配怎么办？ Git告诉我们的效率更高：要将git checkout更改为a123456，将f789abc重命名为a/b.c。实际上，使用正确的选项，d/e.f可以做到这一点：

git diff --find-renames a123456 f789abc

Git如何管理这个技巧？答案在于计算文件身份。

查找文件身份

假设提交L（对于左侧）具有不在提交R（对于右侧）中的某个文件（git diff）。进一步假设提交R包含不在提交L中的某个文件（a/b.c）。与其立即告诉我们：您应该删除L文件并使用R文件，Git现在可以比较两个文件的内容。

由于Git对象哈希的性质（它们是完全确定的，基于文件内容），对于Git来说，很容易检测到L中的d/e.f与R中的a/b.c 100％相同。在这种情况下，它们将具有完全相同的哈希ID！因此，Git做到了：如果某个文件已从L消失，而另一些文件已出现在R中，并且要求Git查找重命名，则Git会检查哈希ID是否匹配。如果找到某些文件，它将对这些文件进行配对（并将它们从不匹配文件的队列中删除-包含L和R中的文件的该队列是“重命名检测队列”）。

那些名称不同的文件已被标识为同一文件。小表弟Bob毕竟和大表弟Bob一样，但在这种情况下，你们两个都还需要很小。

因此，如果此重命名检测尚未将L中的文件与R中的文件配对，Git将更加努力。现在，它将提取实际的斑点，并计算出一种“匹配百分比”。这使用了一个复杂的小算法，在这里我不会描述，但是如果两个文件中足够的子字符串匹配，Git将声明这些文件的相似性为50％，60％，75％或更多。

在重命名队列中找到一对彼此相似程度为72％的文件后，Git继续将这些文件与所有其他文件进行比较。如果发现这两个中的一个与另一个的94％相似，则相似性配对优于72％的相似性配对。如果不是，那么72％的相似度就足够了（至少50％），因此Git会将这两个文件配对并声明它们具有相同的身份。

无论如何，如果匹配足够好并且是所有未配对文件中最好的匹配，则采用该特定匹配。再一次，小堂兄鲍勃毕竟和大堂兄鲍勃一样。

在所有不匹配的文件对上运行此测试后，d/e.f获取匹配的结果并调用那些文件重命名。同样，这仅在使用git diff（或--find-renames）时发生，并且可以根据需要将阈值设置为50％以外的值。

打破不正确的比赛

-M命令提供另一项服务。请注意，我们首先假设，如果提交L和R具有相同名称的文件，则即使内容不同，这些文件也都是相同的文件。但是，如果不是这样呢？如果L中的git diff重命名为R中的file，并且有人在R中创建了新的bettername怎么办？

为了解决这个问题，file提供了git diff（或“中断配对”）选项。启用-B时，如果名称不太相似，则以名称开头的文件将失去配对。也就是说，Git将检查两个blob哈希是否匹配，如果不匹配，则Git将计算相似性索引。如果索引低于某个阈值，则Git将破坏配对并将两个文件放入重命名检测队列，然后再运行-B样式的重命名检测器。

作为一种特殊的改进，Git会重新配对残破的配对，除非它们非常相似，以至于您不希望这样做。因此，对于--find-renames，您实际上指定了两个相似性阈值：第一个数字是何时暂时断开配对，第二个数字是何时永久断开配对。

-B使用git merge

使用git diff --find-renames执行三向合并时，有三个输入：


合并基础提交，这是两个提示提交的祖先；和
左提交和右提交git merge和--ours。


Git在内部运行两个--theirs命令。一个将基数与L比较，另一个将基数与R比较。

这两个差异均在启用git diff的情况下运行。如果从base到L的差异找到一个重命名，则Git知道使用该重命名中显示的更改。同样，如果从base到R的差异找到一个重命名，则Git知道使用这些更改。如果两个差异都显示重命名，它将合并两组更改，并尝试（但通常失败）合并两个重命名。

--find-renames也使用重命名检测器

使用git log --follow时，Git遍历提交历史记录，一次提交一对（父级和子级），从父级到子级进行比较。它打开有限形式的重命名检测代码，以查看您正在抄送的一个文件是否在该提交对中被重命名。如果是这样，git log --follow移至父级后，它将立即更改其查找的名称。该技术效果很好，但是在合并时会遇到一些问题（因为合并提交有多个父项）。

结论

文件身份就是这一切。由于Git先验不知道，提交L中的文件--follow与提交R中的文件git log是“不是”文件，因此Git可以使用重命名检测来确定。在某些情况下（例如检出提交L或R），这一点无关紧要。在某些情况下，例如将两个提交区分开，这很重要，但仅对我们试图理解所发生情况的人类有用。但是在某些情况下，例如合并，这非常重要。