git-rs

用 Rust 实现 git 以娱乐和教育！

这实际上是我第二次尝试，因此许多大块代码都来自我的第一次尝试。在阅读了更多“Rust 编程”（Blandy, Orendorff）之后，我今年再次尝试。

待办事项

• 从散列存储读取对象
• 从打包存储读取对象
  • 读取打包文件索引
  • 读取 delta 对象
  • 修复接口，以便我们不需要为每个 read 运行 open
  • BUG：某些 OFS deltas 应用错误。
    • 隔离错误情况
    • 修复它
• 从磁盘加载引用
• 解析 Git 签名（"Identity"）
• 创建用于遍历提交图的迭代器
• 创建用于遍历树形的迭代器
  • 将树形实体化到磁盘（在 gitindex 之后？）
• 从打包文件创建索引
  • 将 Storage 特性重命名为 Queryable
  • 从 <Type + Boxed reader> 重构对象加载 API 到“我们接受可写对象”
    • 通过 StorageSet 执行重构
  • 创建索引
  • 用友好的 API 包装它
• refs v2
  • 按需加载引用
  • 加载打包引用
• 支持 .git/index
  • 读取 Git 索引缓存
  • 写入 Git 索引缓存
• 创建用于写入新对象的接口
• 添加基准测试
• 从对象列表创建打包文件（API TKTK）
• 网络协议
  • receive-pack
  • send-pack
• 尝试发布到 crates
  • 编写文档
  • 在其他项目中使用 crate

计划

2019-02-08 更新

• 已经有一段时间了！
• 正如你可能看到的，解决打包文件索引问题迫使对仓库进行了大量修改。
  • 现在有一个 src/pack/read.rs 文件，它包含适用于任何 BufRead + Seek 的通用读取实现。
  • Storage 特性的签名已更改——它不再返回boxed read对象，而是现在接受一个 Write 目标。
  • 此外，Storage 现在是 Queryable（更好的名字！）。
    • 由于我们已从返回boxed对象转换为接受通用 Write，因此我们不能再对 Queryable 进行boxing。
      • 我不知道 Rust 的这一点，所以学到新知识！
    • 由于从返回boxed对象到接受通用 Write 的转换，StorageSet 对象必须重新考虑——它们不能再包含boxed的 Storage 对象。
      • 相反，我们让编译器工作——因为存储集合在编译时已知，我为单元类型实现了Queryable，两个类型()，以及单类型的数组Vec<T>。
      • 这意味着一个StorageSet可以包含一个单个的顶级Queryable，其中可能包含嵌套异构的Queryable定义。
        • 这让我感到很温暖，很舒服 💞
• 你可能还会注意到，我们实际上还没有完成索引打包文件。 😱
  • 这里的情况是：为了创建打包文件索引，你必须在打包文件中的压缩字节上运行CRC32。
  • ZlibDecoder将从底层流中拉取比它需要的更多字节，所以你不能采取将CrcReader交给它的方法来获得良好的结果。
  • 它必须是一个多遍的处理过程。
    • 当前的计划是：运行一次遍历来获取偏移量，未delta'd的shas和类型。
    • 运行第二次遍历来解析CRC和解压缩delta。这可以在并行中进行。

2019-01-23 更新

• 是时候开始索引打包文件了。
  • 这将使我们能够开始与外部服务器通信并克隆东西！
• 然而，这有点痛苦。
  • 打包文件（视为存储）在没有索引的情况下并不非常有用，所以我将它们设计为一个可以接收外部可选索引的对象。
    • 我的想法是，如果没有提供索引，我们将在内存中构建一个。
  • 这在我面前爆炸了，一点。 💥
  • 为了从一个打包文件中构建索引，你必须遍历所有的对象。
    • 对于每个对象，你希望记录该偏移量处的对象的偏移量和SHA1 id。
    • 然而，该对象可能是一个偏移量或引用delta。
      • 这意味着为了索引打包文件，你必须能够读取打包文件中偏移量处的delta'd对象（这意味着你已经有了一个创建的Packfile实例）以及在打包文件外部（这意味着你有一个StorageSet。）
      • 换句话说：我对程序设计的假设是错误的。
  • 所以，在接下来的几天里，我将改变方向。
    • 应该能够生产一个非存储对象的Packfile并遍历它。
    • 打包文件的“存储”形式应该是Packfile和Index（一个PackfileStore）的结合。
      • 这意味着我将把src/stores/mmap_pack的逻辑分成“顺序打包文件读取”和“带索引的随机访问打包文件读取”。
• 犯错很有趣 🎉

2019-01-21 更新

• 嗯，那是一个有趣的错误。我们来看看，好吗？
  • 这偶尔会在delta会解码另一个delta'd对象时出现。
    • 我找到了一个可靠的失败加载的哈希值。
    • 我们会因为传入的基本对象与第二个delta的“基本大小”不匹配而失败读取。这里。
    • 移除检查我是否得到了错误的delta会导致线程恐慌——delta的基本大小没有说谎。
  • 首先，我切换回了我旧的非mmap打包文件实现，因为我最近接触了那段代码。“恢复你最近接触的东西”是这些情况中的胜利策略：不需要昂贵的思考，可以快速缩小错误的范围。
    • 唉，旧的打包文件实现也有这个bug。 无济于事。
  • 我比较了这个Git实现与我的JS实现的输出。
    • 我通过将JS实现的输出与vanilla git的hash进行比较来确认JS实现的输出是正确的。
    • 确认之后，我记录了从文件中读取的偏移量和预期的大小。我将这些与添加到git-rs中的类似调试输出进行了比较。
      • 偏移量是发送到打包文件的边界值。对于最外层的读取（"给我代表eff4c6de1bd15cb0d28581e4da17035dbf9e8596的对象"），偏移量来自打包文件索引。
      • 对于OFS_DELTA（"偏移量增量"）类型，起始偏移量是通过从打包文件中读取一个有符号整数并将其从当前起始偏移量中减去来获得的。
    • 偏移量和预期的大小匹配！
      • 这意味着
        1. 我从打包文件中读取了正确的数据
        2. 我正确地读取了有符号整数
        3. 这个bug肯定是在将增量应用到基对象上的应用中
    • 从那里，我在这些状态转换之上添加了日志，注意操作的细节。
      • 我在JS实现中也添加了相同的日志，发现（除了在第二次增量应用之前完全退出）命令是相同的。
      • 所以，问题并不是我的增量代码错了：是我的Read状态机。
  • 这时，我想："这是一个读状态机的bug。 我知道这个。"
    • 所以，这个状态机所做的其中一件事是，如果它不能写入命令的所有字节，它会仔细地退出。("如果还有一个extent要写入，记录下一个状态并退出循环。")
    • 然而，此时我们已经消费了最后一个命令。没有更多的指令了。
    • 所以如果这个函数再次被调用，...
      • 我们将礼貌但坚定地告诉调用者离开（written == 0，在这里）。
  • 修复很简单，像这些修复通常一样。
    • (我知道我需要为此编写一个测试。我知道。把你的羞愧加在我身上吧。)
• 那么 我们学到了什么？
  • 请始终测试你的状态机，朋友们。
  • (我说过一次，现在再说一次。) 可塑的参考实现会救你于水火。
    • 确保你可以信任你的参考实现。
• 无论如何。树读取器现在工作正常了！ 🌲🌳🌲

2019-01-19 更新

• 它稍微快一点了！ 🎉
  • mmap很好地加速了过程，将我们的运行时间减少了20毫秒。
  • 尽管如此，我们仍然比git慢。这可能是因为我们立即加载了refset。
  • 我保留了不可变的"每个读取一个文件"的打包文件存储；我认为它在将来可能会派上用场。
  • 如果能将其作为一个基准来捕获而不是临时运行将是极好的。
• 我集成了树遍历迭代器，得到了一个惊喜
  • 我的OFS delta代码中有一个bug！
  • 这很奇怪，因为它只在某些存储库的某些blob中出现。
    • 否则其他OFS delta似乎可以干净地解析。
    • 案例分析：我作为提交遍历器的测试，加载了许多经过OFS-delta处理的提交。
  • 还有一点值得关注：我已经将 src/bin.rs 分离出来，为树遍历和提交遍历创建了专门的二进制文件。
• 今天的主题：在一个测试用例中隔离故障。
  • 更新：有一个参考实现是非常有帮助的。
  • 我已经确认，参考实现可以读取破坏这个项目的对象。
    • 我们读取的偏移量也是一样的（谢天谢地）
  • 我进一步确认，将包文件实现更换为较旧、较慢的包文件不会影响任何东西。
  • 我怀疑 这意味着可能存在我的delta代码（可能性很大！）我的varint解码代码（可能性非常大），或者是Deltas的Read实现的问题。哇，缩小了结果范围！

2019-01-15 更新

• 我添加了一个（实验性的）git_rs::walk::tree 迭代器，它可以接受一个树并为每个项目产生一个路径和blob。
  • 它可能比应有的要慢：对于每个项目，它必须克隆一个 PathBuf，因为我没有弄清楚生命周期。
  • 如果你知道如何修复它，请 打开一个问题 并让我知道 💞
• 我花了些时间清理构建过程中的警告。
  • 哦！我还安装了 Clippy，它会警告Rust中的高级反模式！
• 我还在思考原始git和我们的git之间 2-3倍 的速度下降。
  • 我想我可能要创建两个包文件接口——一个是“通用”的，另一个是“mmap”的，看看哪一个可以提高性能。
    • 这也具有一个优点，即它是有风险的代码，这是我在Rust中还没有使用过的！

2019-01-06 更新

• 我编写了一个提交迭代器！第一次尝试保留了一个 Vec，包含 (Id, Commit)，这样我们就可以始终从图中选择最近的“下一个”提交（因为提交可能有多个父提交）。
  • 但在完成“Rust编程”的集合部分时，我注意到 BinaryHeap 可用，它保持条目排序。在JS中，你很少能选择集合的底层存储机制，所以这没想到！
  • 无论如何。我在这个提交中用 BinaryHeap 代替了 Vec —— 这里。因为这将排序推入类型的 Ord 实现中，这为使用多个不同排序的单个迭代器定义打开了可能性。很酷！
• 在几个长期存在的仓库上进行测试，git_rs 的结果与 git 完全相同！
  • 然而，它花费的时间大约是 两倍：git_rs 需要 60ms，而 git 需要 30ms。
  • 我认为我在这方面有所突破，这与包文件存储有关：每次从包文件中读取都会打开一个新的 File 实例。
• 我已经添加了一个 待办事项 部分，以跟踪接下来要做什么！

2019-01-02 更新

• 我实现了 引用加载。这有点痛苦！将 Path 类型翻译过来和过去花了一些功夫。
• 我一直试图了解Rust的惯用用法——我找到了一些资源
  • 《Rust API指南》 文档非常实用。
  • @mre 的 idiomatic rust 仓库 收集了许多有趣的链接。
  • 我还随意浏览了 2018年RustConf的视频
• 因此，我为 Id 实现了 FromStr，希望它能提供更符合惯用法的API —— let id: Id = str.parse()?

2018-12-27 更新

• Rust的感觉更加自然。 这个链 写起来感觉很自然。我甚至只用最小的努力就 交叉索引了一个列表。
• 我将对象接口拆分为Type +boxed读取，并提供了一个将数据还原为Object的方法。这感觉很好！它让人们可以检查，例如，他们是否在引用Blob，而不必将整个Blob加载到内存中。
• 松散接口的闭包接口工作得相当不错，但由于REF_DELTA对象，打包接口需要能够请求一个存储集合的引用。这有点糟糕，因为它很快就会变成“与借用检查器斗争”。目前我认为前进的方向是构建一个包含异构Box<Storage>对象的存储集，其中Storage是一个新的特质，它指定了get(&Id, &StorageSet)。
  • 关于松散存储的备注：必须产生一个git_rs::Error而不是一个std::io::Error，这感觉有点奇怪。还有改进的空间！
• 哦！向这个lib crate添加二进制文件非常容易。现在我们可以使用git log查看其他仓库了！

2018-12-21 更新

• 决定放慢速度，并确保这次我为原始数据结构编写了测试。
• 我放弃了原来的Box<Write>特质对象设计，改为使用泛型进行对象实例读取和存储格式。