1 简介

在git中版本管理使用了递归树状结构。

每个目录对应一个独立的tree对象，包含子tree（目录）和blob（文件）的条目。

构建tree时，Git递归遍历目录层次，从叶子节点向上构建tree对象，确保每个子目录的tree哈希被包含在上层tree中。

2 示例：

这个教学实现只做“扁平树”（直接存“路径→blob 哈希”），且只在 checkout 里对已跟踪文件做最小清理；

未实现复杂的工作区脏检查与冲突检测，实际应用环境要更严格。

package main

import (
    "bufio"
    "bytes"
    "crypto/sha1"
    "encoding/hex"
    "encoding/json"
    "errors"
    "fmt"
    "io"
    "os"
    "path/filepath"
    "sort"
    "strings"
    "time"
)

const (
    repoDir      = ".tinyvcs"
    objectsDir   = ".tinyvcs/objects"
    refsHeadsDir = ".tinyvcs/refs/heads"
    headFile     = ".tinyvcs/HEAD"
    indexFile    = ".tinyvcs/index"
)

type Commit struct {
    Tree      string `json:"tree"`
    Parent    string `json:"parent,omitempty"`
    Message   string `json:"message"`
    Author    string `json:"author"`
    Timestamp int64  `json:"timestamp"`
}

type Index map[string]string // path -> blobHash

func main() {
    if len(os.Args) < 2 {
        usage()
        return
    }
    cmd := os.Args[1]
    switch cmd {
    case "init":
        must(initRepo())
    case "add":
        must(ensureRepo())
        if len(os.Args) < 3 {
            fatal("tinyvcs add <file...>")
        }
        must(addFiles(os.Args[2:]))
    case "commit":
        must(ensureRepo())
        msg := parseCommitMessage(os.Args[2:])
        if msg == "" {
            fatal(`tinyvcs commit -m "message"`)
        }
        must(commit(msg))
    case "branch":
        must(ensureRepo())
        if len(os.Args) == 2 {
            must(listBranches())
        } else {
            must(createBranch(os.Args[2]))
        }
    case "checkout":
        must(ensureRepo())
        if len(os.Args) != 3 {
            fatal("tinyvcs checkout <branch>")
        }
        must(checkoutBranch(os.Args[2]))
    case "log":
        must(ensureRepo())
        must(showLog())
    case "status":
        must(ensureRepo())
        must(showStatus())
    default:
        usage()
    }
}

func usage() {
    fmt.Println(`tinyvcs - a tiny VCS in Go

Usage:
  tinyvcs init
  tinyvcs add <file...>
  tinyvcs commit -m "message"
  tinyvcs branch              # list
  tinyvcs branch <name>       # create
  tinyvcs checkout <name>
  tinyvcs log
  tinyvcs status
`)
}

func fatal(msg string) {
    fmt.Fprintln(os.Stderr, "Error:", msg)
    os.Exit(1)
}

func must(err error) {
    if err != nil {
        fatal(err.Error())
    }
}

func ensureRepo() error {
    if _, err := os.Stat(repoDir); err != nil {
        return errors.New("not a tinyvcs repo (run `tinyvcs init` first)")
    }
    return nil
}

func initRepo() error {
    paths := []string{repoDir, objectsDir, refsHeadsDir}
    for _, p := range paths {
        if err := os.MkdirAll(p, 0o755); err != nil {
            return err
        }
    }
    // HEAD -> master
    if _, err := os.Stat(headFile); errors.Is(err, os.ErrNotExist) {
        if err := os.WriteFile(headFile, []byte("ref: refs/heads/master\n"), 0o644); err != nil {
            return err
        }
    }
    // Empty index
    if _, err := os.Stat(indexFile); errors.Is(err, os.ErrNotExist) {
        if err := saveIndex(Index{}); err != nil {
            return err
        }
    }
    // Create empty master ref if not exists
    masterRef := filepath.Join(refsHeadsDir, "master")
    if _, err := os.Stat(masterRef); errors.Is(err, os.ErrNotExist) {
        if err := os.WriteFile(masterRef, []byte(""), 0o644); err != nil {
            return err
        }
    }
    fmt.Println("Initialized empty tinyvcs repository in", repoDir)
    return nil
}

func parseCommitMessage(args []string) string {
    for i := 0; i < len(args); i++ {
        if args[i] == "-m" && i+1 < len(args) {
            return args[i+1]
        }
    }
    return ""
}

// ---------- object store ----------

func hashAndPath(typ string, data []byte) (string, string) {
    content := []byte(typ + "\n")
    content = append(content, data...)
    sum := sha1.Sum(content)
    hash := hex.EncodeToString(sum[:])
    return hash, filepath.Join(objectsDir, hash)
}

func writeObject(typ string, data []byte) (string, error) {
    hash, path := hashAndPath(typ, data)
    if _, err := os.Stat(path); errors.Is(err, os.ErrNotExist) {
        payload := append([]byte(typ+"\n"), data...)
        if err := os.WriteFile(path, payload, 0o644); err != nil {
            return "", err
        }
    }
    return hash, nil
}

func readObject(hash string) (string, []byte, error) {
    path := filepath.Join(objectsDir, hash)
    f, err := os.Open(path)
    if err != nil {
        return "", nil, err
    }
    defer f.Close()
    r := bufio.NewReader(f)
    typ, err := r.ReadString('\n')
    if err != nil {
        return "", nil, err
    }
    typ = strings.TrimSpace(typ)
    data, err := io.ReadAll(r)
    return typ, data, err
}

func writeBlob(path string) (string, error) {
    b, err := os.ReadFile(path)
    if err != nil {
        return "", err
    }
    return writeObject("blob", b)
}

func writeTree(entries map[string]string) (string, error) {
    // entries: path -> blobHash
    buf, err := json.Marshal(entries)
    if err != nil {
        return "", err
    }
    return writeObject("tree", buf)
}

func readTree(hash string) (map[string]string, error) {
    typ, data, err := readObject(hash)
    if err != nil {
        return nil, err
    }
    if typ != "tree" {
        return nil, errors.New("object is not a tree: " + hash)
    }
    var m map[string]string
    if err := json.Unmarshal(data, &m); err != nil {
        return nil, err
    }
    return m, nil
}

func writeCommit(c Commit) (string, error) {
    buf, err := json.Marshal(c)
    if err != nil {
        return "", err
    }
    return writeObject("commit", buf)
}

func readCommit(hash string) (*Commit, error) {
    typ, data, err := readObject(hash)
    if err != nil {
        return nil, err
    }
    if typ != "commit" {
        return nil, errors.New("object is not a commit: " + hash)
    }
    var c Commit
    if err := json.Unmarshal(data, &c); err != nil {
        return nil, err
    }
    return &c, nil
}

func readBlob(hash string) ([]byte, error) {
    typ, data, err := readObject(hash)
    if err != nil {
        return nil, err
    }
    if typ != "blob" {
        return nil, errors.New("object is not a blob: " + hash)
    }
    return data, nil
}

// ---------- index ----------

func loadIndex() (Index, error) {
    b, err := os.ReadFile(indexFile)
    if err != nil {
        return nil, err
    }
    var idx Index
    if len(b) == 0 {
        return Index{}, nil
    }
    if err := json.Unmarshal(b, &idx); err != nil {
        return nil, err
    }
    return idx, nil
}

func saveIndex(idx Index) error {
    b, err := json.MarshalIndent(idx, "", "  ")
    if err != nil {
        return err
    }
    return os.WriteFile(indexFile, b, 0o644)
}

// ---------- refs & HEAD ----------

func readHEADRef() (string, error) {
    b, err := os.ReadFile(headFile)
    if err != nil {
        return "", err
    }
    line := strings.TrimSpace(string(b))
    if !strings.HasPrefix(line, "ref: ") {
        return "", errors.New("HEAD is detached or invalid")
    }
    return strings.TrimPrefix(line, "ref: "), nil
}

func readRef(refPath string) (string, error) {
    b, err := os.ReadFile(filepath.Join(repoDir, refPath))
    if err != nil {
        return "", err
    }
    return strings.TrimSpace(string(b)), nil
}

func writeRef(refPath, hash string) error {
    return os.WriteFile(filepath.Join(repoDir, refPath), []byte(hash+"\n"), 0o644)
}

3 数据结构和对象模型的区别

Tree对象的表示和构建算法:

Git: 使用递归树状结构。每个目录对应一个独立的tree对象，包含子tree（目录）和blob（文件）的条目。

构建tree时，Git递归遍历目录层次，从叶子节点向上构建tree对象，确保每个子目录的tree哈希被包含在上层tree中。

这允许高效的子树复用和增量更新。哈希计算基于排序后的条目列表（mode + name + hash），确保确定性。

本地git工具: Tree简化成一个扁平的map<string, string>（路径 -> blob哈希），序列化为单个JSON对象。构建时，直接从index收集所有文件路径，排序后序列化成一个tree对象。没有递归子tree，所有路径（如"dir/sub/file"）都扁平存储。

这在算法上简化了遍历（无需递归构建），但在大型仓库中可能导致tree对象过大，且无法高效复用子目录（每次commit都需完整重写tree，即使只改动子目录）。区别在于Git的算法支持O(1)子树引用，而tinyvcs是O(n)线性存储（n为文件数）。

Commit对象的结构和历史遍历:

Git: Commit包含tree哈希、多个parent（支持合并commit，有多个父节点）、author、committer、message等。

历史遍历使用DAG（有向无环图）算法，支持从任意commit回溯多条路径（e.g., via BFS/DFS遍历parents）。这允许复杂操作如merge-base计算（找到共同祖先）。

tinyvcs: Commit只支持单个parent（线性历史），无多个parents。因此，历史是严格的单链表（linked list），遍历算法简化成while循环跟随parent直到空。

缺少合并支持，无法处理分支合并的算法（如三路合并或递归合并策略）。此外，timestamp是Unix时间戳，但无committer区分。

Blob和对象哈希计算:

Git: Blob哈希是SHA-1("blob " + size + \0 + content)。对象存储使用deflate压缩，支持loose objects和packfiles（打包优化，使用delta压缩算法减少存储）。

示例本地git: 哈希是SHA-1(typ + “\n” + data)，无size字段，无压缩。算法更简单，但缺少delta压缩（每个对象独立存储），在重复文件多时存储效率低。

无packfiles算法，无法优化历史仓库大小。

4 小结

进一步扩展的方向

三方合并（merge）

读取共同祖先（lowest common ancestor），对文本执行 diff3。

Go 可自己实现 LCS/三方合并，或引入库（例如 sergi/go-diff）做行级合并与冲突标记。

目录树分层

将 tree 做成真正的分层结构，entry 包含 mode/name/oid/type，更贴近 Git。

状态检测（status）

比对工作区 vs index、index vs HEAD tree，给出“未跟踪/已修改/已暂存”的三分视图。

远端与协作

简单 HTTP 远端：

push：把缺失对象与 refs 上传到服务端（set-if-unmodified 以防并发覆盖）。

pull/fetch：下载对象并更新本地 refs（不自动合并）。

做到这里，你就具备最简版“多人协作”的雏形。

安全与一致性

对象写入时使用临时文件 + 原子 rename；refs 更新使用锁文件（.lock）。

校验对象哈希一致性，防止损坏。

性能

打包（packfile）、delta 压缩、并行 I/O、内存映射。

可用性

ignore 规则、.attributes、hooks、GPG 签名、Conventional Commits 校验等。

将这些理念落地到团队协作的实施建议

先选一个分支模型（建议：GitHub Flow 为默认；发布驱动型再考虑 Git Flow）。

配置：受保护分支、强制 PR、强制 CI、简称统一命名与 Conventional Commits。

文化：小批量提交、小 PR、自动化测试优先、Feature Flag 控灰度、禁 force-push 到共享分支。

可视化：配套看板（Issue/PR 状态）、发布看板（release 与 hotfix）。

复盘：每个版本做一次“变更审计”（Changelog 自动化 + 失败案例复盘）。

可以继续添加功能：merge/rebase、真正的分层 tree、远端同步。