git - 代表 Git 仓库的数学结构是什么

Question

我正在学习 Git，如果我能描述代表 Git 存储库的数学结构，那就太好了。例如:它是一个有向无环图；它的节点代表提交；它的节点有代表分支等的标签(每个节点最多一个标签，没有标签使用两次)。(我知道这个描述不正确，我只是想解释我在找什么。)

Answer 1

除了 Nevik Rehnel 评论中的链接(根据要求复制在这里: eagain.net/articles/git-for-computer-scientists和 gitolite.com/gcs ), 和 sehe's point that the commit graph forms a Merkle Tree ，我会添加一些注释。

• 对象存储中有四种对象类型:commit、tree、annotated-tag 和 blob(文件)。
• 一个提交对象只包含一个 tree-ref(当然可以指向更多的树)，一个可能为空的父 SHA-1 哈希列表(必须是更多的提交)，一个作者(姓名，电子邮件，和时间戳)、提交者(与作者相同的形式)和提交文本。
• 树对象包含重复 0 次或更多次的(模式、子对象、文件名)列表。如果子对象是另一棵树，则文件名表示一个目录。如果它是一个 blob，则它代表一个文件。该模式看起来像 POSIX 文件模式，如果它是 120000(符号链接(symbolic link)的文件模式)，则文件的“内容”实际上是符号链接(symbolic link)目标。某些模式值(ab)用于子模块，但我忘记了。不存储 R 和 W 模式位，仅存储 X 位(如果 repo 配置要求忽略它们，即使这样它们也会被忽略)。
• 带注释的标记对象包含对象引用、标记器(名称、电子邮件和时间戳)和标记文本。引用的对象通常是提交，但标签对象可以指向任何对象(甚至是另一个标签对象)。
• 标签(分支和标记以及 reflog-references 等)位于对象存储之外。对于带注释的标签，外面有一个标签，指向对象库内的带注释的标签对象。对于轻量级标签，外部标签指向提交。
• 不限制只有一个根提交。任何没有 parent 的提交都是根。
• Git 几乎从不创建一个空树(这将代表一个空目录)，除了两种情况:在每个 repo 中始终有一个空树，并且如果您进行初始空提交(使用 git commit --allow-empty) 它使用那棵空树。 (由于空树没有子对象，its SHA-1 hash value is a constant。)
• “DAG”描述通常是指通过关闭提交父哈希形成的树。然而，一个树对象通常不应该在它的任何子树中包含自己，如果你设法创建一个循环树结构，你将无法检查它(因为它无限递归)。假设您不能创建具有相同校验和的两棵不同的树(如果可以的话，您会破坏 git)，您将找不到包含树 T2 的树 T1 和包含校验和为 T1 的不同树的树 T2。所以树也是一个隐含的 DAG，并且附加到提交 DAG，它们形成一个更大的 DAG。 :-)
• 对象存储中未引用的对象将由 git gc 进行垃圾收集。空树似乎不受收集影响。 refs/ 和 logs/ 目录和文件 packed-refs 中的任何内容(在 .git 中，或用于bare repos 或当 $GIT_DIR 被设置时，在任何其他地方)充当引用，特殊名称(HEAD、ORIG_HEAD 等)也是如此。 );我不确定其他随机文件(如果在 .git 中创建并包含有效的 SHA-1)是否可以作为引用。
• 索引有一些我从未研究过的格式。它包含对对象存储中对象的引用。当您 git add 一个文件时，git 将该文件放入对象存储并将(非文本)SHA-1 哈希放入索引文件中。这些是防止垃圾回收的有效引用。