完结撒花

今天我终于把UC Berkeley CS61B中的第二个项目Gitlet写完了，总共花费17个小时（不包含读文档的时间）。我也不知道是算快？还是慢，反正除了merge命令我都写的挺爽的。

1778067084558.png

这个项目旨在让学生用 Java 完成一个小型版的 Git 版本管理系统，包含基本的add，commit，status，log，merge等功能，但也对真实的 Git 的功能做了一些简化。其中远程仓库的内容是可选的加分项，所以我并没有写

btw，这应该是我成年前发的最后一个文章、写的最后一个项目。祝我自己18岁生日快乐。

一些提交记录：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
carkree@MacBook-Air skeleton-sp21 % git log --pretty=format:"%h %ad | %s" --date=local   
133a3f5 Wed May 6 17:07:04 2026 | Complete Project 2 Gitlet
a70064c Wed May 6 16:36:57 2026 | Refactor merge method
323ced0 Wed May 6 13:27:46 2026 | Implement merge command
31edc32 Tue May 5 13:51:42 2026 | Implement initial merge method
e5f3acd Sun May 3 18:50:50 2026 | Refactor Commit class structure
f742308 Sat Apr 25 23:57:06 2026 | Refactor checkout/reset and add minor improvements
f4f3cb2 Sat Apr 25 21:43:59 2026 | Implement all commands and pass all tests except merge
0d85c88 Sat Apr 25 20:46:50 2026 | Implement reset in main, correct log behavior
48eb736 Sat Apr 25 19:31:48 2026 | Implement reset method
d32562d Sat Apr 25 15:13:36 2026 | Implement branch and rm-branch command, and adjust the structure
12677c7 Fri Apr 24 22:20:17 2026 | Implement rm, global-log, find and status method in Proj2
67243d5 Fri Apr 24 17:09:23 2026 | Implement checkout method in Proj2. Complete the Checkpoint.
1479ddd Fri Apr 24 15:39:40 2026 | Implement log method in Proj2
9d0418c Fri Apr 24 14:43:32 2026 | Implement commit method in Proj2, summarize some helper private method
d455066 Fri Apr 24 13:04:05 2026 | Implement init and add method in Proj2

项目总结

开始前的建议

学完 20. Heaps and PQs 就可以开始正式做这个项目了，可以完成除了 merge 命令以外的所有内容。

哪怕还没有学到 20. Heaps and PQs，我也建议可以提前开始读spec。因为这个的spec真的很长，可以闲得没事干的时候就去看一眼。spec中也额外要求了几个intro和lab，记得完成他们。

学完 22. Graph Traversals and Implementations 就可以做 merge 命令了

在做项目的过程中，先自己想，但是超过30分钟还想不出来的话，我认为是可以用AI辅助的，但是不要让它直接生成代码，而是让它为你解释spec、交流思路。如果是因为没能看懂需求而一直卡着，那我觉得浪费这个时间很没有意义。

我的基础结构与思路

项目需要在工作文件夹创建一个.gitlet目录，结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
.gitlet/
    |--objects/
    |     |--commit/
    |     |--blob/
    |
    |--refs/
    |     |--heads/
    |           |--master
    |
    |--HEAD
    |
    |--addstage/
    |--removestage/

Commit 的实现

  • 每个 commit 都是一个 Commit 类的实例。
  • 每次执行 commit 命令时，都会创建一个新的 Commit 对象。
  • Commit 类内部有一个 parent 成员变量，用于存储上一个提交的 ID，由此形成一种链式结构。
  • Commit 类需要 implements Serializable，这样才能将对象序列化后写入文件，并存放到 .gitlet/objects/commit 目录下。
  • 后续实现 merge 后，一个 commit 可能同时拥有两个父提交，因此需要再增加一个“父提交“成员变量，此时整体结构将从链表演变为一个有向无环图。

重要概念：什么是 Blob？

  • 在 Gitlet 中，每个文件都会以 blob 的形式存储。
  • Blob 保存文件的内容本身，不包含文件名

1778059584188.png

  • Commit 类负责将“文件名”和“文件内容”关联起来。
  • Commit 类中有一个成员变量，通常以 HashMap<String, String> 的形式存储：
    • 键（Key）：文件名
    • 值（Value）：该文件对应 blob 的 ID

分支（Branch）

  • 所有分支保存在refs/heads 目录下，每个分支都对应着一个文件。
  • 默认的初始分支是master
  • 该目录下每个文件中存储着对应分支当前指向的 commit ID。
  • 因此，分支本质上可以理解为一个“可移动的提交指针”，也就是某一分支的头指针。每次做新的commit，就更新这个头指针，让对应的文件中存放新的commit ID。

HEAD

  • HEAD 文件用于记录当前所在的分支。
  • 该文件中存储当前分支的路径，例如：“refs/heads/master“

暂存区（Stage）

  • Gitlet 中有两个暂存区：
    • 添加暂存区（add stage）
    • 删除暂存区（remove stage）
  • 暂存区本质上可以看作一个 HashMap：
    • 键（Key）：文件名
    • 值（Value）：对应 blob 的 ID
  • 执行commit命令时，则要根据暂存区哈希表来更新commit哈希表

除此以外，代码中还需要用到项目提供的 Utils 类，其中封装了许多实用的方法，例如将内容写入文件、将对象序列化并写入文件，以及获取当前目录下的文件列表等操作。

在完成整个项目的过程中，也需要适当地提炼一些私有辅助方法，这不仅能减少重复代码，也方便后续功能的实现和维护。

Merge命令的实现

merge 是最为复杂的一个命令，光是错误情况就有很多种。

在执行 merge 后，所有的 commit 将不再是树状结构，而是组成一个有向无环图（DAG），因此需要用到图遍历（graph traversal）的相关思路。其中，最重要的是找到 split point（分裂点），即分支开始分叉的位置。split point 一定是两条分支最新的共同祖先。

这里我使用了 BFS（广度优先搜索）。首先沿着目标分支进行搜索，将所有 commit ID 存储到一个 HashSet 中；接着，再搜索当前分支，直到找到第一个出现在该 HashSet 中的提交，它就是 split point。

接下来，需要比较当前分支最新提交、目标分支最新提交以及 split point 三者之间的关系，以决定是执行 checkout、rm，还是处理冲突。我首先遍历了这三个提交，获得了一个存储所有文件名的 HashSet。随后，对该 HashSet 进行遍历，并在循环中分别使用 currChanged、targetChanged 和 sameResults 三个变量记录三者之间的变更关系。

剩下的就是根据这些变更关系进行判断。Spec 中对此写得非常详细（但是就是快给我看晕了）。如果两条分支的处理方式不同，例如一个修改一个删除，或是修改的内容不一样，就属于冲突。 基本思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
- 如果当前分支和分裂点没有不同（`currChanged` 为假）
  - 检查目标分支
    - 如果目标分支和分裂点也没有不同（`targetChanged` 为假）
      - 什么都不做
    - 如果目标分支和分裂点有不同（`targetChanged` 为真）
      - 如果目标分支没有这个文件
        - 删除文件（`rm`）
      - 如果目标分支有这个文件
        - `checkout` 目标版本并 `add`
- 如果当前分支和分裂点有不同（`currChanged` 为真）
  - 检查目标分支
    - 如果目标分支和分裂点没有不同（`targetChanged` 为假）
      - 保留当前分支版本（什么都不做）
    - 如果目标分支和分裂点也有不同（`targetChanged` 为真）
      - 如果当前分支和目标分支结果相同（`sameResults` 为真）
        - 什么都不做
      - 如果当前分支和目标分支结果不同（`sameResults` 为假）
        - 发生冲突（`solveConflict`）

结语

这个项目还是很大程度上提升了我的能力的，除Main的错误情况外，全程古法编程。我写项目的经历本身就不是很多，都是在搞一些乱七八糟的杂东西，所以我从这之中收获很大。这也是我用Java写过最大的东西了，在上CS61B之前我只会python。

未来，可能还会把下面的课都学完，但是Project3我不是很确定有没有时间做了。

本文使用CC BY-NC-SA 4.0协议进行许可

许可协议

如没有特别声明，本文采用CC BY-NC-ND 4.0协议进行许可，转载请标明出处。

快来参与讨论吧~