项目介绍

概述

Gitlet 希望实现 Git 当中一部分的内容。其中主要的功能有：

commit
checkout
log
branches
merge

理论上每一次提交都可以更改多个文件。不过，为了简洁性，下面许多的例子每次都只修改一个文件。

每一个 Commit 都会有父节点，指向上一个提交。因此，可以通过链表的方式来可视化。HEAD 指针代表现在工作工作区的状态。通常，HEAD 指针会在链表的尾部，代表最新的 commit。不过，如果返回到之前某个节点，那么 HEAD 就会指向对应 commit。这时候状态为 detached head state。

注意：Gitlet 中没有 checkout 命令，所以不会出现 detached head state 情况。Gitlet 中的 reset 命令会同时移动 branch 的指针。

当有多个版本的时候，Commit 组成的数据结构就不再是链表，而是树。每个分支的末尾都会有对应分支的指针。在某个时刻，HEAD 只会指向其中一个分支。

需要注意，commit tree 是不能摧毁的。只能将新的节点加入，但不能删除旧节点。

在使用不同对象的时候，不能简单地使用指针，否则如果读入某一个 commit，则所有之前的 commit 也都会被激活。这会导致读入消耗更多的时间。因此，不应该储存指针，而应该储存对应物品的名字。

内部结构

有一些重要的对象：

blobs：储存文件的内容。一个文件可能对应多个 blobs。
trees：目录的数据结构，将相应的名字对应到 blobs 和其他树。
commits：信息，其他 metadata，以及父节点指针。同时储存从 branch heads 到 commit 的 hash 值的指针。

Gitlet 相比于 Git，会进一步简化：

不处理子文件夹
限制 merge 到两个 parents
commit 的 metadata 只有 timestamp 和 message。

最好区分 commits 和 blobs 的 hashing。可以放在不同的文件夹之中。如果两个文件的 hashing 一样，就认为它们的内容一样。

Spec

总体预期

不应该在 Main 类当中做所有事。而应该使用 Repository 类，在 Main 当中做好调用的工作。

所有的 repo 文件储存在 .gitlet 中，并且 gitlet 只有在存在 .gitlet 的时候，才能正常工作（除了 init 命令）。
需要遵循各个命令的运行时间或内存占用要求。
有些命令有明确要求的错误信息，并且都以分号结束
有一些错误情况：
- 如果没有提供命令行参数，打印 Please enter a command. 并退出
- 如果输入的命令不存在，打印 No command with that name exists. 并退出
- 如果输入命令的格式、个数有问题，打印 Incorrect operands. 并退出
- 如果输入的命令需要在初始化后的工作区才能使用，则打印 Not in an initialized Gitlet directory.
只打印 spec 中所说的内容
使用 System.exit(0) 退出，并且就使用 0
Dangerous 表示该命令会修改当前工作区中的文件

开始

万事开头难。这个项目一开始只提供了 Main、Commit 和 Repository 类，并且很简略，剩下的类都需要自己根据需要构造。

Main

在 Main 函数中，应该简短，引用其他函数的内容。因此，首先判断参数的个数。根据第一个参数的内容进行讨论。

init

使用 Repository 类的初始化器来实现新建仓库。在 Main 函数中，也就是一个 new Repository();。

在 Repository 类中，首先创建许多不同的目录。我的目录结构如下：

.gitlet/
- blobs/
- commits/
- branches/
- HEAD

为了实现初始化，需要完成以下任务：

如果已经存在 .gitlet，则视作错误，退出程序
创建各个文件夹
创建初始 Commit
创建初始 Branch —— master
创建头 HEAD
储存上述新建的对象

Commit

在这一步，我仅仅实现了 message、timeStamp 和 parent 作为实例变量，还没有加入文件指针。

对于构造器，输入为信息和父节点。为了存储时间，我使用了 java.sql.Timestamp 类，因为输入看起来比较直接、美观。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


/** Construct a new commit with message and parent. */  
public Commit(String msg, Commit parent) {  
    this.message = msg;  
    this.parent = parent;  
    if (parent == null) {  
        this.timeStamp = EPOCH_TIME.toString();  
    } else {  
        Timestamp timeNow = new Timestamp(System.currentTimeMillis());  
        this.timeStamp = timeNow.toString();  
    }  
}

Branch 和 HEAD

为了实现指针的功能，我创建了 Pointer 类，相当简单。

1
2
3
4
5
6
7


public class Pointer implements Serializable {  
    public String next;  
  
    public Pointer(String sha1) {  
        next = sha1;  
    }  
}

Branch 类代表分支指针。显然，分支指针可能有多个名字，因此增加相应实例变量 name。

1
2
3
4
5
6
7


public class Branch extends Pointer {  
    private String name;  
    public Branch(String sha1, String name) {  
        super(sha1);  
        this.name = name;  
    }
}

Head 类代表头指针。只用继承 Pointer 类的构造器就行。

Hash 与储存

Commit 需要使用 sha 1 算法。在提供的 Utils.sha1(Object... vals) 中，支持字节数组或者字符串的混合输入。调用该方法，得到 Commit 的 toSha1() 方法：

1
2
3
4


/** Convert message and timeStamp to sha1. */  
public String toSha1() {  
    return Utils.sha1(message, timeStamp);  
}

为了储存 hash，在 Repository 中创建 storeInHashTable(File path, Serializable o , String sha1) 方法。可以利用 hash 值得前两个字符创建文件夹，这样就起到了哈希表的作用，方便查找。

1
2
3
4
5
6
7
8
9


/** Using object and its sha1 to store in path. */ 
public static void storeInHashTable(File path, Serializable o , String sha1) {  
    File folder = join(path, sha1.substring(0, 2));  
    File file = join(folder, sha1);  
    if (!folder.exists()) {  
         folder.mkdir();  
    }  
    writeObject(file, o);  
}

因此，可以实现 Commit 的 store() 方法。

1
2
3


public void store() {  
    Repository.storeInHashTable(Repository.COMMITS_DIR, this, toSha1());  
}

对于 master 和 HEAD 来说，直接利用名字来储存。在 Repository 中创建方法：

1
2
3
4
5


/** Store current object by name. */  
public static void storeInName(File path, Serializable o, String name) {  
    File file = join(path, name);  
    writeObject(file, o);  
}

实现

最后，就完成了 init 命令的初始化，对应代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public Repository() {  
    if (GITLET_DIR.exists()) {  
        Main.exitWithMessage("A Gitlet version-control system "  +  
                "already exists in the current directory.");  
    }  
    GITLET_DIR.mkdir();  
    BLOBS_DIR.mkdir();  
    COMMITS_DIR.mkdir();  
    BRANCHES_DIR.mkdir();  
    Commit initCommit = new Commit("initial commit", null);  
    Branch master = new Branch(initCommit.toSha1(), "master");  
    Head head = new Head(initCommit.toSha1());  
    initCommit.store();  
    master.store();  
    head.store();  
}

add

Blob 与 Commit

这个类是用来存储文件的，只有一个实例变量 text。方法包括 toSha1()，store() 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


public class Blob {  
    public String text;  
    public Blob(String text) {  
        this.text = text;  
    }  
  
    public String toSha1() {  
        return Utils.sha1(text);  
    }  
  
    /** Store text in hash name. */  
    public void store() {  
        String sha1 = sha1(text);  
        File folder = join(Repository.BLOBS_DIR, sha1.substring(0, 2));  
        File file = join(folder, sha1);  
        if (!folder.exists()) {  
            folder.mkdir();  
        }  
        writeContents(file, text);  
    }
}

在 Commit 类中，构造 read() 方法，从而根据 HEAD 指针来获取当前的提交节点。

1
2
3
4


public static Commit read(String sha1) {  
    File file = Repository.fileFromHashTable(Repository.COMMITS_DIR, sha1);  
    return readObject(file, Commit.class);  
}

Main 与 Repository

在 Main 函数中确认参数个数，并且使用 Repository 的 load () 方法来加载得到新的 Repo，然后使用 add(String name) 方法。

1
2
3
4
5


case "add":  
    validateArgsNum(args, 2);  
    Repository currRepo = Repository.load();  
    currRepo.add(args[1]);  
    break;

在 Repository 类中，如果发现文件不存在，就报错。否则，阅读文件的内容，存储到 Blob 类中。然后，读取当前 Commit。检查当前 Commit 的文件列表中是否包含暂存区中对应文件。如果包含且 sha 1 值相等，就代表这个文件应该从暂存区中移除，同时结束程序。然后，储存 blob，将文件加入暂存区，并且储存暂存区。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public void add(String fileName) {  
    File file = join(CWD, fileName);  
    if (!file.exists()) {  
        Main.exitWithMessage("File does not exist");  
    }  
    String fileContents = Utils.readContentsAsString(file);  
    Blob blob = new Blob(fileContents);  
    String sha1 = blob.toSha1();  
    Commit currCommit = Commit.read(head.next);  
    if (currCommit.getFiles().get(fileName) != null &&  
            currCommit.getFiles().get(fileName).equals(sha1)) {  
        area.removeFileAddition(fileName, sha1);  
        System.exit(0);  
    }  
    blob.store();  
    area.addFileAddition(fileName, sha1);  
    area.store();  
}

Commit

Main 和 Repo

如果只有一个参数，需要输出 Please enter a commit message.。接着，使用 Repository 的 commit(String msg) 方法。

为了提交，首先需要检查暂存区中是否有更改。如果没有就输出 No changes added to the commit. 并退出。否则，读取当前 Commit。然后，根据当前 Commit 创建新的 Commit，并且更新其中文件。接着，清理暂存区，更新 HEAD，储存新的 Commit，储存暂存区和 HEAD。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public void commit(String msg) {  
    if (area.additionArea.isEmpty() && area.removalArea.isEmpty()) {  
        Main.exitWithMessage("No changes added to the commit.");  
    }  
    Commit currCommit = Commit.read(head.next);  
    Commit newCommit = currCommit.newCommit(msg);  
    newCommit.updateFiles(area);  
    area.clear();  
    head.next = newCommit.toSha1();  
    newCommit.store();  
    area.store();  
    head.store();  
}

Commit

首先，需要修改原先的初始化器。并且加入了 files 变量来储存文件和指针的对应关系。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public Commit(String msg, String parent) {  
    this.message = msg;  
    this.parent = parent;  
    if (parent.isEmpty()) {  
        this.timeStamp = EPOCH_TIME.toString();  
        this.files = new HashMap<>();  
    } else {  
        Timestamp timeNow = new Timestamp(System.currentTimeMillis());  
        this.timeStamp = timeNow.toString();  
		this.files = read(parent).files;
    }  
}

要从当前节点创建新的节点，显然要输入当前节点的 sha 1 值。

1
2
3


public Commit newCommit(String msg) {  
    return new Commit(msg, this.toSha1()); 
}

因为 Utils.sha1() 只接受多个字符串或者字节矩阵作为输入，因此要输入文件列表中的 hash 值，就需要遍历 files。

1
2
3
4
5
6
7


public String toSha1() {  
    StringBuilder tmp = new StringBuilder();  
    for (String name : files.keySet()) {  
        tmp.append(files.get(name));  
    }  
    return Utils.sha1(message, timeStamp, parent, tmp.toString());  
}

rm

Repository

如果要删除的文件名在暂存区的增加列表当中，就去除。如果在当前提交中也有要删除的文件名，就需要将该文件加入暂存区的删除区域，并且手动删除这个文件。如果上面两个都没有发生，就退出并打印 No reason to remove the file.。最后储存暂存区。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public void rm(String fileName) {  
    boolean flag = false;  
    String result1 = area.getAdditionArea().remove(fileName);  
    if (result1 != null) {  
        flag = true;  
    }  
    Commit currCommit = Commit.read(head.next());  
    if (currCommit.files().containsKey(fileName)) {  
        String sha1 = currCommit.files().get(fileName);  
        area.getRemovalArea().put(fileName, sha1);  
        File rmFile = join(CWD, fileName);  
        Utils.restrictedDelete(rmFile);  
        flag = true;  
    }  
    if (!flag) {  
        Main.exitWithMessage("No reason to remove the file.");  
    }  
    area.store();  
}

log

为了显示记录，需要首先打印当前提交的信息。然后让指针指向上一个节点，继续打印相应信息，重复直到到达最初的提交。

Commit

首先，让 Commit 类继承 Dumpable 接口。然后，按照格式打印。这里的时间用到了 SimpleDateFormat。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


@Override  
public void dump() {  
    System.out.println("===");  
    System.out.println("commit " + toSha1());  
    SimpleDateFormat dateFormat = new SimpleDateFormat("EEE MMM d HH:mm:ss yyyy Z", Locale.ENGLISH);  
    dateFormat.setTimeZone(TimeZone.getTimeZone("GMT+8:00"));  
    String formattedDate = dateFormat.format(timeStamp);  
    System.out.println("Date: " + formattedDate);  
    System.out.println(message);  
    System.out.println();  
}

Repository

只需要使用一个指针遍历即可。

1
2
3
4
5
6
7
8


public void log() {  
    Head p = head;  
    while (!p.next().isEmpty()) {  
        Commit currCommit = Commit.read(p.next());  
        currCommit.dump();  
        p.updateNext(currCommit.getParent());  
    }  
}

中间部分

Checkout 1

Checkout 的第一个命令可以让文件恢复到当前 commit 的状态。该命令会覆盖当前工作区中的文件。

在 Main 中，调用 checkoutFile(String fileName)。其代码如下：

1
2
3
4


case "checkout":  
    if (args.length == 3) {  
        currRepo.checkoutFile(args[2]);  
    }

在 Repo 中，实现该方法：

1
2
3
4
5
6
7
8


public void checkoutFile(String fileName) {  
    String sha1 = currCommit.files().get(fileName);  
    if (sha1 == null) {  
        Main.exitWithMessage("File does not exist in that commit.");  
    }  
    Blob blob = Blob.read(sha1);  
    blob.writeToCWD(fileName);  
}

Blob 的 writeToCWD 方法如下：

1
2
3
4


public void writeToCWD(String fileName) {  
    File file = join(Repository.CWD, fileName);  
    Utils.writeContents(file, text);  
}

Checkout 2

这个 checkout 命令可以回退到特定 commit 的特定文件，然后覆盖当前工作区。在 Main 中：

1
2
3


else if (args.length == 4) {  
    currRepo.checkoutCommitFile(args[1], args[3]);  
}

在 Repo 中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


public void checkoutCommitFile(String pSha1, String fileName) {  
    File commitFile = fileFromHTPrefix(COMMITS_DIR, pSha1);  
    if (commitFile == null) {  
        Main.exitWithMessage("No commit with that id exists.");  
        return;  
    }  
    Commit commit = Commit.read(commitFile.getName());  
    String blobSha1 = commit.files().get(fileName);  
    if (blobSha1 == null) {  
        Main.exitWithMessage("File does not exist in that commit.");  
    }  
    Blob blob = Blob.read(blobSha1);  
    blob.writeToCWD(fileName);  
}

其中，fileFromHTPrefix 可以实现根据 sha 1 值的前面一部分，找到对应的文件并返回。然后，根据文件读入 commit，并找到相应 blob 的 sha 1。最后，将 blob 写入当前工作区。

要想从 hashTable 中根据 sha 1 的前缀读取文件，需要如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public static File fileFromHTPrefix(File path, String pSha1) {  
    File folder = join(path, pSha1.substring(0, HASH_PREFIX_LENGTH));  
    List<String> fileSha1s = plainFilenamesIn(folder);  
    if (fileSha1s != null) {  
        for (String sha1 : fileSha1s) {  
            if (sha1.startsWith(pSha1)) {  
                return join(folder, sha1);  
            }  
        }  
    }  
    return null;  
}

这里用到了 String 的 startsWith 方法。

Status

因为后面涉及到分支，之前我设计的 branch 实际上不方便读取、存储。因此，改成 branches 类，直接存储所有分支，以及当前的分支。Branches 类拥有以下变量：

1
2
3
4


private Map<String, String> nameToSha1;  
private String activeBranchName;  
private String activeBranchSha1;  
private static final String name = "BRANCHES";

Status 可以呈现当前的状态。首先，实现 branches 和 area 的 dump 方法，也就是输出对应的内容。然后很容易实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


/** Print out current status. */  
public void status() {  
    System.out.println("=== Branches ===");  
    branches.dump();  
    System.out.println();  
    System.out.println("=== Staged Files ===");  
    area.dumpStagedFiles();  
    System.out.println();  
    System.out.println("=== Removed Files ===");  
    area.dumpRemovedFiles();  
    System.out.println();  
    System.out.println("=== Modifications Not Staged For Commit ===");  
    System.out.println();  
    System.out.println("=== Untracked Files ==="); 
    System.out.println();  
}

其中，branches 的 dump 方法要遍历 Map，按照字符串的顺序，然后在当前所在分支前加上星号。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


@Override  
public void dump() {  
    Set<String> strs = nameToSha1.keySet();  
    String[] names = Repository.setToArray(strs);  
    Arrays.sort(names);  
    for (String name : names) {  
        if (name.equals(activeBranchName)) {  
            System.out.println("*" + name);  
        } else {  
            System.out.println(name);  
        }  
    }  
}

Global-log

全局 log 需要遍历所有的 commit，然后打印出来，不限次序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public void globalLog() {  
    List<String> folderNames = plainFilenamesIn(COMMITS_DIR);  
    if (folderNames == null) {  
        System.out.println("COMMITS NOT EXIST!!!");  
        return;  
    }  
    for (String folderName : folderNames) {  
        File folder = join(COMMITS_DIR, folderName);  
        List<String> commitSha1s = plainFilenamesIn(folder);  
        for (String sha1 : commitSha1s) {  
            Commit commit = Commit.read(sha1);  
            commit.dump();  
        }  
    }  
}

Find

Find 需要遍历所有的 commits，然后找到具有相应 message 的 commit，打印出对应的 sha 1 值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


public void find(String msg) {  
    String[] folderNames = COMMITS_DIR.list();  
    if (folderNames.length == 0) {  
        System.out.println("COMMITS NOT EXIST!!!");  
        return;  
    }  
    for (String folderName : folderNames) {  
        File folder = join(COMMITS_DIR, folderName);  
        List<String> commitSha1s = plainFilenamesIn(folder);  
        for (String sha1 : commitSha1s) {  
            Commit commit = Commit.read(sha1);  
            if (commit.getMessage().equals(msg)) {  
                System.out.println(commit.toSha1());  
            }  
        }  
    }  
}

后期部分

此时，需要进一步完成 branches 的功能，实现 checkout 3 功能，完成 branch、rm-branch 和 reset 命令。

Branches 功能

为了实现 branches 的更新当前分支功能，可以创建 setActiveBranch 方法，根据 branch 名称来切换到相应的 branch。

1
2
3
4
5
6
7
8
9


/** Set active branch. */  
public void setActiveBranch(String name) {  
    String sha1 = nameToSha1.get(name);  
    if (sha1 == null) {  
        Main.exitWithMessage("Branch name not found!!!");  
    }  
    activeBranchName = name;  
    activeBranchSha1 = sha1;  
}

为了创建新的 branch，创建 putBranch 方法。

1
2
3
4


/** Put branch into branches. */  
public void putBranch(String name, String sha1) {  
    nameToSha1.put(name, sha1);  
}

Branch

在 Repository 中创建 branch 方法。如果当前的名字已经存在，就返回报错。否则，就创建新的 branch 指向当前节点。

1
2
3
4
5
6
7
8


/** Create new branch. */  
public void branch(String branchName) {  
    if (branches.getMap().containsKey(branchName)) {  
        Main.exitWithMessage("A branch with that name already exists.");  
    }  
    branches.putBranch(branchName, head.next());  
    saveState();  
}

Rm-branch

Rm-branch 可以移除一个不是当前 branch 的 branch。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


/** Remove branch with that name. */  
public void rmBranch(String branchName) {  
    if (!branches.getMap().containsKey(branchName)) {  
        Main.exitWithMessage("A branch with that name does not exists.");  
    }  
    if (branches.getActiveBranchName().equals(branchName)) {  
        Main.exitWithMessage("Cannot remove the current branch.");  
    }  
    branches.removeBranch(branchName);  
    saveState();  
}

其中，Branches 类的 removeBranch 方法如下：

1
2
3
4


/** Remove branch. */  
public void removeBranch(String name) {  
    nameToSha1.remove(name);  
}

Checkout 3

这个命令输入相应的 branch 名称，然后 checkout 到相应的 commit 上。如果不存在相应 branch 名称，或者就是当前的 branch，那么就报错退出。否则，获取相应 branch 的 sha 1，再来到相应的 commit。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/** Checkout branch. */  
public void checkoutBranch(String branchName) {  
    if (!branches.getMap().containsKey(branchName)) {  
        Main.exitWithMessage("No such branch exists.");  
    }  
    if (branches.getActiveBranchName().equals(branchName)) {  
        Main.exitWithMessage("No need to checkout the current branch.");  
    }  
    String checkoutCommitSha1 = branches.getMap().get(branchName);  
    checkoutCommit(checkoutCommitSha1);  
    branches.setActiveBranch(branchName);  
    saveState();  
}

其中，checkoutCommit 方法有些复杂。首先，获取当前工作区文件名列表。如果其中有没有标记的文件，就报错退出。否则，读取需要 checkout 的 commit，然后得到文件列表，写入当前工作区。接着，再次遍历原先文件列表，如果原先文件名不在现在的 commit 中，那么就删除相应的文件。最后，将 head 更新为这个 commit，并且清空缓存区。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


/** Checkout to commit. */  
private void checkoutCommit(String commitSha1) {  
    List<String> fileNames = plainFilenamesIn(CWD);  
    if (fileNames != null) {  
        for (String fileName : fileNames) {  
            if (!isTrackedFile(fileName)) {  
                Main.exitWithMessage("There is an untracked file in the way;" +  
                        " delete it, or add and commit it first.");  
            }  
        }  
    }  
    Commit checkoutCommit = Commit.read(commitSha1);  
    Map<String, String> newFiles = checkoutCommit.getFiles();  
    for (String fileName : newFiles.keySet()) {  
        Blob blob = Blob.read(newFiles.get(fileName));  
        blob.writeToCWD(fileName);  
    }  
    if (fileNames != null) {  
        for (String fileName : fileNames) {  
            if (!newFiles.containsKey(fileName)) {  
                File delFile = join(CWD, fileName);  
                restrictedDelete(delFile);  
            }  
        }  
    }  
    head.updateNext(commitSha1);  
    area.clear();  
}

其中，isTrackedFile 检查文件是否被标记。

1
2
3
4
5
6
7
8


/** Check whether tracked a file with that name. */  
public boolean isTrackedFile(String fileName) {  
    if (area.getRemovalArea().containsKey(fileName)) {  
        return false;  
    }  
    return currCommit.getFiles().containsKey(fileName)  
            || area.getAdditionArea().containsKey(fileName);  
}

Reset

Reset 接受一个参数，就是相应 commit 的 id，然后跳转到相应的 commit。

如果不能获取相应 commit，就报错退出。否则，checkout 相应 commit，然后将当前的 branch 指向对应 commit。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


/** Reset to commit id. */  
public void reset(String commitId) {  
    File commitFile = fileFromHTPrefix(COMMITS_DIR, commitId);  
    if (commitFile == null) {  
        Main.exitWithMessage("No commit with that id exists.");  
    }  
    Commit commit = Commit.read(commitFile);  
    checkoutCommit(commit.toSha1());  
    String branchName = branches.getActiveBranchName();  
    branches.getMap().put(branchName, commit.toSha1());  
    saveState();  
}

最后的 Merge

这部分我拖到了 10 月 4 号才写，放了一个多月，可能写得不好，见谅。

该函数接受一个 branch 作为输入，然后看当前头结点仍否和指定的 branch 进行合并。

首先，需要做一些基础的判断——当前工作区是否为空，输入的 branch 名字是否存在，以及是否当前已经处在了 branch 中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


public void merge(String branchName) {  
    if (!area.isClean()) {  
        Main.exitWithMessage("You have uncommitted changes.");  
    }  
    if (branches.getMap().get(branchName) == null) {  
        Main.exitWithMessage("A branch with that name does not exist.");  
    }  
    if (branches.getActiveBranchName().equals(branchName)) {  
        Main.exitWithMessage("Cannot merge a branch with itself.");  
    }
}

接着，代码需要根据相应的分支名字，找到分支对应的节点。然后，根据当前节点和分支节点，找到两者共同的第一个节点。这个其实是一个常见的链表题目，leetcode 上面也有。只需要两个节点都遍历完整个链表，分别拥有两个长度。然后，对齐两个长度，让两个指针每次都往前走一步，这样就可以找到公共节点。在这里，我使用 findSplitPoint 函数来实现这个功能。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


private String findSplitPoint(String branchName) {
	// my thought comes from https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.
	// 07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html#%E6%80%9D%E8%B7%AF
	int lenA = ancestorLength(branches.getActiveBranchSha1());
	int lenB = ancestorLength(branches.getMap().get(branchName));
	String curA = head.next();
	String curB = branches.getMap().get(branchName);
	if (lenB > lenA) {
		int tmpNum = lenA;
		lenA = lenB;
		lenB = tmpNum;
		String tmpStr = curA;
		curA = curB;
		curB = tmpStr;
	}
	int gap = lenA - lenB;
	while (gap > 0) {
		curA = ancestor(curA);
		gap -= 1;
	}
	while (!curA.isEmpty()) {
		if (curA.equals(curB)) {
			return curA;
		}
		curA = ancestor(curA);
		curB = ancestor(curB);
	}
	return null;
}

接下来，还有一些特殊情况。

如果公共节点就是要切换的节点，那么说明要切换的节点就是当前节点的父节点，不用进行操作。
如果公共节点就是当前节点，那就直接 checkout 到那个 branch 就可以（fast-forward）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


String splitPointSha1 = findSplitPoint(branchName);  
String mergeCommitSha1 = branches.getMap().get(branchName);  
String currentCommitSha1 = head.next();  
if (splitPointSha1.equals(mergeCommitSha1)) {  
    Main.exitWithMessage("Given branch is an ancestor of the current branch.");  
}  
if (splitPointSha1.equals(currentCommitSha1)) {  
    checkoutBranch(branchName);  
    Main.exitWithMessage("Current branch fast-forwarded.");  
}

接下来，创建一个集合，其中储存着三个节点当中所有出现过的文件。

1
2
3
4
5


Commit splitCommit = Commit.read(splitPointSha1);  
Commit mergeCommit = Commit.read(mergeCommitSha1);  
Set<String> fileNames = new HashSet<>(splitCommit.files().keySet());  
fileNames.addAll(mergeCommit.files().keySet());  
fileNames.addAll(currCommit.files().keySet());

然后，遍历这些文件，对于每一个文件分别判断。这里的情况超级多，我现在都有些忘了，只能把这个辅助函数放在这里。这个函数接受三个节点中文件的 sha 1作为输入，然后返回合并后应该存在的文件。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


/** Return the result blob SHA1 of merge. */
private String mergeFile(String splitSha1, String headSha1, String otherSha1) {
	if (headSha1 == null && otherSha1 == null) {
		// case 3 special
		return "";
	}
	if (splitSha1 == null && headSha1 == null) {
		// case 5
		return otherSha1;
	}
	if (splitSha1 == null && otherSha1 == null) {
		// case 4
		return headSha1;
	}
	if (splitSha1 == null) {
		if (otherSha1.equals(headSha1)) {
			// case 3
			return otherSha1;
		} else {
			Blob newBlob = createMergeBlob(headSha1, otherSha1);
			newBlob.store();
			return newBlob.toSha1();
		}
	}
	if (splitSha1.equals(otherSha1) && headSha1 == null) {
		// case 7
		return "";
	} else if (splitSha1.equals(headSha1) && otherSha1 == null) {
		// case 6
		return "";
	} else if (splitSha1.equals(headSha1) && !splitSha1.equals(otherSha1)) {
		// case 1
		return otherSha1;
	} else if (!splitSha1.equals(headSha1) && splitSha1.equals(otherSha1)) {
		// case 2
		return headSha1;
	} else if (!splitSha1.equals(headSha1) && headSha1.equals(otherSha1)) {
		// case 3
		return headSha1;
	} else {
		Blob newBlob = createMergeBlob(headSha1, otherSha1);
		newBlob.store();
		return newBlob.toSha1();
	}
}

遍历之后，还需要经过一些判断，决定对当前工作区的操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


boolean hasMergeConflict = false;
	for (String fileName : fileNames) {
		String splitSha1 = splitCommit.files().get(fileName);
		String headSha1 = currCommit.files().get(fileName);
		String otherSha1 = mergeCommit.files().get(fileName);
		String newFileSha1 = mergeFile(splitSha1, headSha1, otherSha1);
		if (newFileSha1.isEmpty() && !(headSha1 == null)) {
			rm(fileName);
		} else if (!newFileSha1.equals(headSha1) && !newFileSha1.isEmpty()) {
			if (!newFileSha1.equals(otherSha1)) {
				hasMergeConflict = true;
			}
			Blob blob = Blob.read(newFileSha1);
			blob.writeToCWD(fileName);
			area.getAdditionArea().put(fileName, newFileSha1);
		}
	}

最后，打印相关的信息，提交新的 commit，并且保存当前状态。

1
2
3
4
5
6
7
8


String message = "Merged " + branchName + " into "
		+ branches.getActiveBranchName() + ".";
if (hasMergeConflict) {
	System.out.println("Encountered a merge conflict.");
}
commit(message, mergeCommitSha1);

saveState();

总结

不得不说，Gitlet 确实富有挑战性，同时相当有收获。

这个项目开始时，看上去相当复杂，有许多许多的部分需要考虑。“万事开头难”，这时候正是让人最迷茫的时候。在这个项目之前，接触到的许多编程作业，都会给你一些框架代码。区分起来大概如下：

完全搭建好了整体的框架，包括具体的每一个函数，只是函数的内容空缺。给出详细的每个函数需要完成的功能，只需要按部就班完成函数就可以。
部分搭建了整体的框架，拥有一些函数，但是有些函数实现起来较为复杂，需要自己分解任务。
完全没有框架，只告诉你达成的效果怎么样，具体使用哪些类，都需要自己创造。

Gitlet 属于上述的第三种。好在，Gitlet 提供了许多视频资源，其中复现了 Gitlet 在背后应该做一些什么事。根据这些资源，你可以思考需要构建哪些类，然后，根据类去编写相应的方法，实现抽象。然后，自己根据类创建实例，达到相应的功能。

经过统计，这个项目单纯代码有 13 个类， 1000 多行，注释有 300 行，空白有 150 行。通过这样的工程，也确实锻炼了规范写代码的能力，以及 Debug 的能力。

最后，感慨一下 cs61b 的课程设计。在临近最后的课当中，教授反思了近年来这个课的 project。当年 gitlet 第一次提出的时候，没有详细的教学视频，也没有做好的集成测试，导致学生们经历了惨状。之后，随着资源的引入，这个项目的难度适当降低，不过学生们的反应各有千秋——有的觉得这个项目完全打击了他的自信心，让他之后不想投身编程；有的觉得这个项目虽然很麻烦，但是说活颇丰。

教授充分展示了学生们对课程的评价，每一年都根据反馈，不断优化课程，力求在难度、有趣程度和有用程度上达到平衡。我不紧反思起我国的计算机教育。身为某个 985 大学的学生，我所感受到的计算机课程，是十几年亘古不变的教材，是上世纪传承下来的 ppt，老师照着念一念，课程的作用要么十分书面，缺少实践，要么只给你一个大方向，没有详细的指导。

至于学生们对课程的反馈，那更是单向的，在不知名的教务平台上填写，没什么作用。以至于在官方平台之外，有其他的平台出现，起到了课程评价的效果。只有在其他平台，学生们才会说出自己对课程的真实想法，然而老师们是不关心这个的。

正如 csdiy 最后所说，希望随着今后的发展，该网站不再有用，因为学生们可以在课堂上接受最好的教育。我也希望之后某一天，不用再在其他平台对课程做出评价，而是可以通过官方的途径，直接向老师反馈，而老师也会给出回应。至于这究竟是不是我的异想天开，也只能之后再来看了。

CS61B project2 学习笔记

包括project2的思路与实现细节

项目介绍

概述

内部结构

Spec

总体预期

开始

Main

init

Commit

Branch 和 HEAD

Hash 与储存

实现

add

Blob 与 Commit

Main 与 Repository

Commit

Main 和 Repo

Commit

rm

Repository

log

Commit

Repository

中间部分

Checkout 1

Checkout 2

Status

Global-log

Find

后期部分

Branches 功能

Branch

Rm-branch

Checkout 3

Reset

最后的 Merge

总结