git如何检测类似文件的重命名检测？

Question

维基百科解释了自动重命名检测:

简而言之,给定修订版N中的文件,修订版N-1中的同名文件是其默认祖先.但是,当修订版N-1中没有同名文件时,Git会搜索仅存在于修订版N-1中的文件,并且与新文件非常相似.

重命名检测显然归结为类似的文件检测.这个算法记录在哪里吗？很高兴知道自动检测到哪种变换.

Answer 1

Git跟踪文件内容,而不是文件名.因此,重命名文件而不更改其内容很容易被git检测.(GIT不跟踪,而是执行检测 ;使用git mv或git rm和git add.实际上是相同)

将文件添加到存储库时,文件名位于树对象中.实际文件内容作为二进制大对象(blob)添加到存储库中.Git不会为包含相同内容的其他文件添加另一个blob.事实上,GIT中不能作为内容存储在与哈希为目录名和其余的是在它的文件名的前两个字符的文件系统.因此,检测重命名是一个比较哈希的问题.

为了检测重命名文件的微小变化,Git使用某些算法和阈值限制来查看这是否是重命名.例如,看一下-M标志git diff.还有配置值,例如merge.renameLimit(合并期间执行重命名检测时要考虑的文件数).

要了解git如何处理类似文件(即,哪些文件转换被视为重命名),请探索可用的配置选项和标志,如上所述.你不需要考虑如何.要了解git如何实际完成这些任务,请查看用于查找文本差异的算法,并阅读git源代码.

算法仅适用于差异,合并和日志目的 - 它们不会影响git如何存储它们.文件内容的任何小变化都意味着为其添加了新对象.该级别没有增量或差异.当然,稍后,对象可能被打包,其中增量存储在packfiles中,但这与重命名检测无关.

Answer 2

该算法是否记录在任何地方？

至少在 Git 2.33（2021 年第 3 季度）中对此进行了说明，其中有关“ git diff -l<n>” ^（man）的文档已diff.renameLimit更新，并且这些限制的默认值已提高。

请参阅Elijah Newren ( )的提交 94b82d5、提交 9dd29db、提交 6623a52、提交 05d2c61（2021 年 7 月 15 日）。^{（由Junio C Hamano 合并 -- --提交268055b，2021 年 7 月 28 日）}newren
gitster

rename：再次默认碰撞限制

^{签署人：伊利亚·纽伦}

这些最后在提交 92c57e5中被修改（“再次修改重命名限制默认值”，2011-02-19，Git v1.7.5-rc0 -- merge），并且被修改是因为处理器变得更快，而且因为人们导致问题的丑陋合并并将其报告给邮件列表（表明人们愿意花更多时间等待）。

从那之后：

• Linus 继续建议内核人员设置 diff.renameLimit=0 （当前映射到 32767）
• 一旦代码支持这一点，拥有大量重命名的存储库的人们很乐意将其设置merge.renameLimit为高于 32767，以获得正确的选择
• 处理器变得更快
• 发现上次使用的计时方法可能使用了太大的示例文件。

最后一点可能值得解释一下：

• 使用的“平均”文件大小似乎是当时 Linux 内核历史记录中的平均 blob 大小（可能是 v2.6.25 或接近的版本）。
• 由于较大的文件被更频繁地修改，因此这种计算权重更大的文件。
• 随着时间的推移，较大的文件可能更有可能被修改，但不会更有可能被重命名——树中的 blob 大小的平均值和中位数略高于历史记录中 blob 大小的平均值和中位数。 Linux 内核的版本。
• v2.6.25 中的平均 blob 大小是该点历史上平均 blob 大小的一半
• v2.6.25 中的中位 blob 大小约为 v2.6.25 中的平均 blob 大小的 40%。
• 由于平均 Blob 大小是中值 Blob 大小的两倍以上，因此任何与平均值一样大的文件都不会与任何中值大小或更小的文件进行比较（因为它们的相似度超过 50%）。
• 由于提供行为的是比较的文件数量O(n^2)，因此中等大小的文件应该比平均大小的文件更重要。

上述综合影响是过去计算中使用的文件大小可能大了大约 5 倍。
结合大约 30% 的 CPU 性能改进，我们可以将限制增加 1 倍sqrt(5/(1-.3)) = 2.67，同时保持原来规定的时间限制。

保持相同的大致时间限制可能是有意义的（例如^（man）diff.renameLimit中没有进度反馈），但上述经验表明可以显着延长。 事实上，对 进行无限制的默认设置可能是有意义的，但这可能需要与进度显示方式的更改相结合。 （有关该区域的详细信息，请参阅https://lore.kernel.org/git/YOx+Ok%2FEYvLqRMzJ@coredump.intra.peff.net/ 。） 现在，我们将大约时间限制从 10 秒提高到 1 分钟。git log -pmerge.renameLimit
merge.renameLimit

（注意：我们不想使用实际的时间限制，因为获得取决于当天系统负载情况的结果感觉很糟糕，并且因为我们没有发现我们不会获得所有重命名，直到我们完成之后投入大量工作，而不仅仅是预先告诉用户涉及的文件太多。）

使用 2 秒的原始时间限制diff.renameLimit，并merge.renameLimit从 10 秒增加到 60 秒，我使用此提交消息末尾的简单脚本发现了以下计时（在 AWS 上c5.xlarge报告为“Intel(R) Xeon(R) Platinum 8124M”） CPU@3.00GHz”）：

N   Timing
0    1.995s
0   59.973s

因此，让我们向下舍入为漂亮的偶数，并从400->1000,和 中提高限制1000->7000。

这是measure_rename_perf脚本（改编自https://lore.kernel.org/git/20080211113516.GB6344@coredump.intra.peff.net/，特别是为了避免触发基名引导的重命名检测的线性处理）：

#!/bin/bash

n=$1; shift

rm -rf repo
mkdir repo && cd repo
git init -q -b main

mkdata() {
  mkdir $1
  for i in `seq 1 $2`; do
    (sed "s/^/$i /" <../sample
     echo tag: $1
    ) >$1/$i
  done
}

mkdata initial $n
git add .
git commit -q -m initial

mkdata new $n
git add .
cd new
for i in *; do git mv $i $i.renamed; done
cd ..
git rm -q -rf initial
git commit -q -m new

time git diff-tree -M -l0 --summary HEAD^ HEAD

git config现在包含在其手册页中：

-l。如果未设置，当前默认值为 1000。

git config现在包含在其手册页中：

目前默认为 7000。

并且，仍然使用 Git 2.33（2021 年第 3 季度）：

请参阅Elijah Newren ( )的提交 94b82d5、提交 9dd29db、提交 6623a52、提交 05d2c61（2021 年 7 月 15 日）。^{（由Junio C Hamano 合并 -- --提交268055b，2021 年 7 月 28 日）}newren
gitster

doc：澄清重命名/复制限制的文档

^{签署人：伊利亚·纽伦}

文档中的一些地方暗示重命名/复制检测始终是二次的，或者所有（未配对的）文件都涉及重命名/复制检测的二次部分。
以下两个提交各自引入了一个例外：

• 9027f53（“执行线性时间/空间重命名逻辑以实现精确重命名”，2007-10-25，Git v1.5.4-rc0 -合并）
• bd24aa2（“ diffcore-rename：指导基于基名的不精确重命名检测”，2021-02-14，Git v2.31.0-rc1 -合并）

（作为旁注，对于复制检测，关闭基本名称引导的不精确重命名检测，并且精确重命名只会导致从二次检测中使用的文件集中删除源（不带目标）。
因此，对于复制检测，文档更接近正确。）

避免暗示重命名/复制检测中涉及的所有文件均受完整二次算法的影响。
同时，还要注意所有这些设置的默认值。

git config现在包含在其手册页中：

在复制/重命名检测的详尽部分中要考虑的文件数量；相当于 'git diff' 选项-l。
如果未设置，当前默认值为 400。
如果重命名检测关闭，则此设置无效。

git config现在包含在其手册页中：

合并期间重命名检测的详尽部分要考虑的文件数量。

如果未指定，则默认为 的值diff.renameLimit。
如果 或merge.renameLimit均未diff.renameLimit指定，则当前默认为 1000。
如果重命名检测关闭，则此设置无效。

diff-options现在包含在其手册页中：

和选项涉及一些初步步骤，可以廉价地检测重命名/副本的子集，然后是详尽的后备部分，将所有剩余的未配对目的地与所有相关源进行比较-M。 （对于重命名，只有剩余的未配对源是相关的；对于副本，所有原始源都是相关的。）-C

对于 N 个源和目的地，此详尽检查是O(N^2)。

如果涉及的源/目标文件数量超过指定数量，此选项可防止运行重命名/复制检测的详尽部分。
默认为diff.renameLimit.