CS61B Gitlet 完结撒花

完结撒花

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

这个项目旨在让学生用 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、交流思路。如果是因为没能看懂需求而一直卡着，那我觉得浪费这个时间很没有意义。

我的基础结构与思路

我参考了CS61B Gitlet入坑指南这一文章。

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

重要概念：什么是 Blob？

• 在 Gitlet 中，每个文件都会以 blob 的形式存储。

• blob 保存的是文件的内容本身，与文件名无关。
• 真正负责将“文件名”和“文件内容”关联起来的是 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将不再是树状，而是组成一个有向无环图，因此需要用的图的traversal的相关想法。其中，最重要的是找到“split point“（分裂点），即分支开始的地方，分裂点一定是两条分支的最新共同祖先。

这里我使用了BFS（广度优先搜索），先沿着目标分支搜索，存储所有的commit ID到一个HashSet中。接着，再搜索当前分支，直到找到第一个出现在该HashSet中的提交，即为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
19

- 如果当前分支和分裂点没有不同（currChanged 为否）
    - 检查目标分支        
        - 如果目标分支和分裂点也没有不同（targetChanged 为否）            
            - 什么都不做                
        - 如果目标分支和分裂点有不同（targetChanged 为是）            
            - 如果目标分支没有这个文件                
                - 删除文件（rm）                    
            - 如果目标分支有这个文件                
                - checkout 目标版本并 add               
                
- 如果当前分支和分裂点有不同（currChanged 为是）
    - 检查目标分支        
        - 如果目标分支和分裂点没有不同（targetChanged 为否）            
            - 保留当前分支版本（什么都不做）                
        - 如果目标分支和分裂点也有不同（targetChanged 为是）            
            - 如果当前分支和目标分支结果相同（sameResults 为是）                
                - 什么都不做                    
            - 如果当前分支和目标分支结果不同（sameResults 为否）                
                - 发生冲突（solveConflict）

结语

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

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

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