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

Question

Git手册的第3.1章明确指出，只有暂存文件才能作为blob存储在提交树中。

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

---

一个简单的例子：

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

让我们假设我修改了README.md，stage和commit。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（de1c8b5c77f...）和名称（.clang-format）一滴 您还可以看到tree可以引用其他tree对象，就像.github子树一样。

如果我们使用这个特定的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构建的高速缓存b5101f929789889c2e536d915698f58d5c5c6b7a将说出该名称。.clang-format具有mode 100644和blob-hash de1c8b5c77f7566d9e41949e5e397db3cc1b487c，而name .github/CONTRIBUTING.md具有mode 100644和blob-hash 64e605a02b71c51e9f59c429b28961c3152039b9。

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

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

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

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

我们在这里回答的真正问题与身份有关。在版本控制系统中，文件的身份确定该文件在两个不同版本中是否为“相同”文件（但是版本控制系统本身定义了版本）。这涉及到身份的根本哲学问题，如中概述的思想实验有关Thesus的船舶此维基百科的文章：我们怎么知道的东西，甚至有的一个，是我们认为的是谁还是什么？如果您在表弟鲍勃（Bob）很小的时候遇到了他，并且又遇到了一个名叫鲍勃（Bob）的人，他是您的表弟吗？你和他那时很小。现在您越来越大，经验也有所不同。在现实世界中，我们从环境中寻求线索：鲍勃（Bob）是父母的兄弟姐妹的孩子吗？如果是这样，即使鲍勃（和您）现在看起来很不一样，鲍勃可能就是您很久以前见过的堂兄鲍勃。

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

git diff 提供额外的服务

在我们的日常开发中，有时有时需要重命名文件。命名的文件a/b.c可能会被重新命名，以d/e.f或d/e.c出于某种原因。

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

但是，假设我们要求的Git来比较 a123456同f789abc。Git 只能告诉我们：要更改a123456为f789abc，请删除a/b.c并创建d/e.f包含这些内容的新文件。 这是什么git checkout没有和它足够了。但是，如果内容完全匹配怎么办？这是更有效的Git的告诉我们：要更改a123456到f789abc，重命名a/b.c到d/e.f。 实际上，只要有正确的选择，git diff 就能做到：

git diff --find-renames a123456 f789abc

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

查找文件身份

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

因为GIT中物体的性质的散列-他们是完全确定性的，基于文件的内容，这是很容易 GIT中，以检测a/b.c在大号是100％相同的d/e.f中- [R 。在这种情况下，它们将具有完全相同的哈希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会将这两个文件配对并声明它们具有相同的身份。

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

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

打破不正确的比赛

该git diff命令提供了另一项服务。请注意，我们首先假设，如果提交L和R具有相同名称的文件，即使内容不同，这些文件也都是相同的文件。但是，如果不是这样呢？如果file在大号得到改名为bettername在[R ，并且有人创建了一个新file的R'

要解决此问题，请git diff提供-B（或“中断配对”）选项。随着-B生效，即开始了由名称标识的文件都会有自己配对打破，如果他们太DIS -similar。也就是说，Git将检查两个blob哈希是否匹配，否则，Git将计算相似性索引。如果索引低于某个阈值，则Git将中断配对并将两个文件放入重命名检测队列，然后再运行--find-renames样式重命名检测器。

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

git merge 用途 git diff --find-renames

当您使用git merge进行三方合并，有三个输入：

• 合并基础提交，这是两个提示提交的祖先；和
• 左右提交，--ours以及--theirs。

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

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

git log --follow 也使用重命名检测器

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

结论

文件身份就是这一切。由于Git先验地不知道，a/b.c提交L中的文件d/e.f与提交R中的文件是“不是”文件，因此Git可以使用重命名检测来确定。在某些情况下（例如检出提交L或R），这一点都没有关系。在某些情况下，例如将两个提交区分开，这很重要，但仅对我们人类试图了解所发生的事情具有重要意义。但是在某些情况下，例如合并，这非常重要。