Git Stash 内部

Modesty Zhang

5.00/5 (2投票s)

2024年3月9日

CPOL

9分钟阅读

6377

通过 `git stash` 的实现，包括 push、apply、pop、drop、list 和 clear，全部使用 isomorphic-git，深入剖析 Git 的对象模型。

在评估用于 CDE（云开发环境）的 Git 集成解决方案时，我对其技术方面印象深刻 isomorphic-git。代码库组织良好，文档同步，并且测试套件丰富。该项目拥有强大的功能集并提供出色的性能。直到发现 stash 功能存在差距，它似乎完全符合项目需求。

Git stash 的功能请求已被标记为 '需要帮助' 了多年，显然弥补这一差距将使更多人受益。需要深入研究 Git 对象模型和 isomorphic-git 的复杂细节，才能为该项目添加 stash 功能。

现在 PR 已准备就绪，本文将与社区分享学习和发现以及实现技术，希望能帮助那些正在寻找类似解决方案或仅仅对通用对象模型和数据结构感兴趣的人。

Stash 与 Branch

Git 对象模型采用 Merkle 树来确保数据完整性、实现高效的存储和检索，并促进数据验证和同步。这种由哈希组成的递归树结构代表了任意大小的分层数据集的快照——即我们项目工作目录的版本历史记录。

在 Git 中，branch 和 stash 都充当指向提交的“refs”（引用）。它们都可以通过 Git 命令进行操作，用于导航提交历史。然而，它们的共性是有限的。

从概念上讲，分支是对提交树末端的引用，它们是项目永久历史记录中固有的组成部分。相比之下，stash 存在于一个单独的命名空间（refs/stash）中。当您创建 stash 时，Git 会生成一个提交对象来封装已暂存和工作目录的修改，但此提交既不集成到提交历史中，也不与特定分支关联。此外，refs/stash 条目是本地的，不包含在 git push 操作中。

Stash 是一个专门的 ref，它将进行中的工作 (WIP) 状态保存为一次提交。这允许恢复到该状态，而不会改变分支历史。本质上，它是一个悬空提交，有两个父提交：创建 stash 时 HEAD 处的提交和当时索引的状态。如果通过 stash push（默认）包含未暂存的更改，则会添加第三个父提交，以表示创建 stash 时工作目录树的快照。

Stash 可以被视为一个临时分支，它不打算合并到主分支。当保存尚未准备好提交或推送的更改，或者在不丢失工作的情况下切换分支时，它非常有用。与分支不同，stash 没有名称，并且存储在堆栈状结构中，其中最新的 stash 位于顶部。Stash 有自己的访问方式，包括 stash list、stash show 和 stash apply 命令。

虽然分支和 stash 都实现为 ref，但它们的预期用途和对存储库的影响是不同的。实现 git stash 不会受益于 branch 的功能。相反，需要直接操作低级 Git 对象来生成父提交、树和 reflogs。此任务涉及与松散对象的交互，但不是 packfiles，packfiles 针对具有高效存储和索引的对象传输进行了优化。

在开始自己实现之前，让我们检查一下常规 git 客户端为 git stash 创建的内容。我们可以从命令行窥探 refs/stash 中的内容。

$ cat .git/refs/stash

0f47ba5d10ed30779c078d31b3fc47331e4bb98b <-- current stash commit SHA

从提交 SHA，我们可以找到 stash 提交对象。

$ git cat-file -t 0f47ba5d10ed30779c078d31b3fc47331e4bb98b

commit <-- type of the object

提交对象有两个父提交。

$ git cat-file -p 0f47ba5d10ed30779c078d31b3fc47331e4bb98b

tree a0d51b4516951595dc4fd6ecb9beb50da495e210

parent b72fb56d1f53d4120ee6fd206ea1e77ee4071c5f

parent 41d7e412a828f5c6838f6d064881803316afeea3

author modesty <pdf2json@github.com> 1707931505 -0800

committer modesty <pdf2json@github.com> 1707931505 -0800

它指向一个树，并有两个父提交，分别代表索引和工作目录的更改。我们的任务是在 isomorphic-git 中为 `git stash` 创建一个相同结构的提交对象，这是其他 stash 操作的核心，包括 apply、drop、pop、list 和 clear 等。

Git 对象：回顾

现在我们了解了 stash 的独特性质，对 Git 对象类型的简洁回顾将阐明它们的内部表示。Stash 利用了四种基本 Git 对象类型中的三种：commit、tree 和 blob（在此讨论中我们将省略 tag）。

回想一下 commit 和 tree 之间的关系：tree 可以被概念化为目录快照，它包含了子目录（由 tree 对象表示）以及指向任意数量文件内容的 blob 的引用。Blob 对象包含压缩的文件内容，它们的 SHA-1 哈希作为其父 tree 中的引用。这种“子不识父”的模型使得对象共享非常高效，如果一个文件存在于多个分支（这是常见情况），则只引用其 SHA，而不是文件本身。

要检查 stash 的内部结构，我们可以检查其关联的 tree 对象。

$ git cat-file -p a0d51b4516951595dc4fd6ecb9beb50da495e210 <-- the tree SHA above

100644 blob 1bff7bfa72823e7cd90a6e9304156571e53b0988 .eslintrc.json
100644 blob 3a15fc6e4f3d3b359f9f2900fd6e1d61824fe5c2 .gitignore
040000 tree ddfdb61937565b864aaa210a187890a7dfefdf0d .husky
100644 blob bcea5db4c05c21cbd19ea6a5fae4cb6c71e8dc19 README.md
100644 blob cb00c3f18ee24b4e75abdf9883fd6f284f048ec2 build.properties
100644 blob 0594052072a108a4446678e35e035bb0955ffb23 package-lock.json
100644 blob 3ef98a63860e011e1b573ab36302542d68bc320a package.json
040000 tree 8c4401ac77ef562385f401d90feeca7a9d6ed304 packages
100644 blob 35259cddd2bb0c6f17e40edbaa03f4feba19d142 pom.xml
040000 tree 806243fa28d66c2904f8d4eb0623a0718383f63a scripts
100644 blob 3ac4170137102fd0d14e9e2e345a794f28b21b4f tsconfig.base.json
100644 blob 2e7ef9708ca1cd337a8a57ab101b986a7a2ed8a2 webpack.base.js

（链接指向 geeksforgeeks 的 Merkle 树介绍）Merkle 树模型固有的优雅体现在其高效简洁地表示文件系统目录内容。每个 tree 条目都封装了文件系统权限、文件名以及它所包含的任何文件或子目录的 SHA-1 哈希。

下面是一个简化的图表，说明了这些 Git 对象类型之间的关系。

Commit Object
│
├─ Tree Object 1 ─ Blob Object (File content)
│  │
│  ├─ Tree Object 2 ─ Blob Object (File content)
│  │
│  └─ Blob Object (File content)
│
└─ Parent Commit Object (Previous commit)
   │
   └─ Tree Object ─ Blob Object (File content)

至关重要的是，Git 对象模型不显式存储“diff”或“log”。在执行 git show、git log 或 git status 等命令时，输出是通过分析和比较 tree 及其组成对象动态生成的。这一基本原理对于 git stash 的实现至关重要：通过根据 Git 对象模型构建对象和建立关系，我们可以无缝地引入新的 stash 功能。

创建 Stash

在 isomorphic-git 中实现 git stash 需要直接利用低级 API。诸如 writeCommit（不同于更高级别的 commit）、writeTree、TREE、WORKDIR、STAGE 以及至关重要的 walk 等函数都可以促进这一过程。

以下是生成 stash 的一般步骤，它默认封装了来自索引（暂存）和工作目录（未暂存）的已跟踪更改。

获取当前分支的 HEAD：此提交作为 stash 提交的第一个父提交，代表了创建 stash 时的存储库状态。

// prepare the stash commit: first parent is the current branch HEAD
const headCommit = await GitRefManager.resolve({fs, gitdir, ref: 'HEAD'})

构建表示索引更改的 tree：如果存在已暂存的更改，则生成一个以索引 tree 为根的提交对象。此提交是 stash 提交的第二个父提交。

const indexTree = await writeTreeChanges
                  (fs, dir, gitdir, [ TREE({ref: 'HEAD'}),'stage'])
if (indexTree) {
  // this indexTree will be the tree of the next commit object
  // create a commit from the index tree, which has one parent, 
  // the current branch HEAD
  const stashCommitOne = await stashMgr.writeStashCommit({
    message: `stash-Index: WIP on ${branch} - ${new Date().toISOString()}`,
    tree: indexTree, // stashCommitTree
    parent: stashCommitParents,
  })
  stashCommitParents.push(stashCommitOne)
  stashCommitTree = indexTree
}

构建表示工作目录更改的 tree：如果已跟踪文件的未暂存修改存在，则生成一个以工作目录树为根的提交对象。此提交构成了 stash 提交的第三个父提交。

const workingTree = await writeTreeChanges(fs, dir, gitdir, [workDirCompareBase,'workdir'])

if (workingTree) {
  // create a commit from the working directory tree, 
  // which has one parent, either the one we just had, or the headCommit
  const workingHeadCommit = await stashMgr.writeStashCommit({
    message: `stash-WorkDir: WIP on ${branch} - ${new Date().toISOString()}`,
    tree: workingTree,
    parent: [stashCommitParents[stashCommitParents.length - 1]],
  })

  stashCommitParents.push(workingHeadCommit)
  stashCommitTree = workingTree
}

创建 stash 提交：准备好所有父提交后，组装最终的 stash 提交。

// create another commit from the tree, 
// which has three parents: HEAD and the commit we just made:
const stashCommit = await stashMgr.writeStashCommit({
  message: message.trim() || `stash: WIP on ${branch} - ${new Date().toISOString()}`,
  tree: stashCommitTree,
  parent: stashCommitParents,
})

在 .git/refs/stash 中记录 stash：将新创建的 stash 保存在 Git 对象存储中。
```
// next, write this commit into .git/refs/stash:
await stashMgr.writeStashRef(stashCommit)
```

添加 reflog 条目：在 reflog 中记录 stash 创建提交，以进行历史跟踪。

// write the stash commit to the logs
await stashMgr.writeStashReflogEntry({
  stashCommit,
  message: `WIP on ${branch}: ${headCommit.substring(0, 7)} ${headMsg}`,
})

将工作目录恢复到干净状态：将工作目录恢复到 stash 之前的状态。

// finally, go back to a clean working directory

await checkout({fs, dir, gitdir, ref: branch, track: false,
  force: true, // force checkout to discard changes
})

应用 Stash

虽然 stash 在内部表示为一个提交，但仅仅检出关联的提交树并不能完全复制预期的 stash 行为。特别是，标准的检出会将工作目录留在分离 HEAD 状态，并且不会恢复对索引（暂存区）的修改。需要一种定制的方法来全面应用 stash。

核心策略很简单：我们分析 stash 提交及其父提交树，并根据需要将检测到的更改应用于工作目录和索引。这是程序分解：

从 stash ref 检索父提交：访问存储在.git/refs/stash中的 stash 提交关联的父提交。

// get the stash commit object
const stashCommit = await stashMgr.readStashCommit()
const { parent: stashParents = null } = stashCommit.commit ? stashCommit.commit : {}
if (!stashParents || !Array.isArray(stashParents)) {
  return // no stash found
}

遍历父提交并应用差异：对于每个父提交，将其 tree 表示与前一个父提交进行比较。将任何已识别的更改应用于工作目录或暂存区。

// compare the stash commit tree with its parent commit
for (let i = 0; i < stashParents.length - 1; i++) {
  const applyingCommit = await _readCommit({fs, cache: {}, gitdir, oid: stashParents[i + 1]})
  const wasStaged = applyingCommit.commit.message.startsWith('stash-Index')
  await applyTreeChanges(fs, dir, gitdir, stashParents[i + 1], stashParents[i], wasStaged)
}

就是这样！

我们可以跳过其他常见的 git stash 操作，例如 pop（它实际上是 apply + drop）、drop（从.git/refs/stash中删除引用，以及 reflogs 中的顶部条目）、list（读取并格式化 reflogs）以及 clear（删除.git/refs/stash和 reflogs），这些操作没有什么特别有趣的。

然而，请注意我们在创建索引或工作目录 tree 时调用了 writeTreeChanges？另外还有上面的 applyTreeChanges？这些是 stash 的精髓，也是我花最多时间的地方，让我们仔细看看。

Tree Walker

我们 stash 实现的核心是我们定制的 tree 比较机制。这使我们能够生成表示索引（暂存更改）和工作目录更改的 tree，这对于封装 stash 状态至关重要。Isomorphic-git 的 walk API 为此功能提供了基础。

1. Tree 条目过滤

我们战略性地使用 WalkerIterate 回调来过滤掉无关的 tree 条目，确保生成的 tree 反映预期的 stash 内容。isStage 变量有助于区分索引和工作目录 tree 处理，而 changedEntries 变量则捕获检测到的差异。

// if parent is skipped, skip the children
// API ref: type WalkerIterate = (walk: WalkerIterateCallback, children: 
//          IterableIterator<Array<WalkerEntry>>) => Promise<Array<any>>;: // API 
// API ref: type WalkerIterateCallback = 
//          (entries: Array<WalkerEntry>) => Promise<Array<any>>;

const iterate = async (walk, children) => {
  const filtered = []
  for (const child of children) {
    const [head, stage] = child
    if (isStage) {
      if (stage) {
        // for deleted file in work dir, it also needs to be added on stage
        if (await fs.exists(`${dir}/${stage.toString()}`)) {
          filtered.push(child)
        } else {
          changedEntries.push([null, stage]) // record the change (deletion) 
                                             // while stop the iteration
        }
      }
     } else {
      if (head) {
        // for deleted file in workdir, "stage" (workdir in our case) will be undefined
        if (!stage) {
          changedEntries.push([head, null]) // record the change (deletion) 
                                            // while stop the iteration
        } else {
          filtered.push(child)              // workdir, tracked only
        }
      }
    }
  }

  return filtered.length ? Promise.all(filtered.map(walk)) : []
}

2. 使用 Tree Mapping 分析更改

WalkerMap 回调在文件和子目录级别精确定位更改。与 WalkerIterate 一样，head 和 stage 变量代表正在比较的 tree。它利用 changedEntries 结构来跟踪修改。此回调返回一个 TreeEntry 类型的对象，这是 tree 构建的关键构建块。

// transform WalkerEntry objects into the desired format
// API ref: type WalkerMap = 
//          (filename: string, entries: Array<(WalkerEntry|null)>) => Promise<any>;

const map = async (filepath, [head, stage]) => {
  if (filepath === '.' ||
    (await GitIgnoreManager.isIgnored({ fs, dir, gitdir, filepath }))
  ) {
    return
  }

  if (stage) {
    if ( !head ||
      ((await head.oid()) !== (await stage.oid()) &&
      (await stage.oid()) !== undefined)
    ) {
      changedEntries.push([head, stage])
    }

    return {
      mode: await stage.mode(),
      path: filepath,
      oid: await stage.oid(),
      type: await stage.type(),
    }
  }
}

3. 组合 Tree 结构

WalkerReduce 回调促进 tree 的分层组合。它组装 TreeEntry 实例及其子项，最终确定最终的 tree 结构。

// combine mapped entries with their parent results
// API ref: type WalkerReduce = (parent: any, children: Array<any>) => Promise<any>;
  const reduce = async (parent, children) => {
    children = children.filter(Boolean) // Remove undefined entries
    if (!parent) {
      return children.length > 0 ? children : undefined
    } else {
      parent.children = children
      return parent
    }
  }

4. 验证和展平

附加的递归过程会验证每个 TreeEntry 是否具有有效的 oid。此步骤处理 tree 类型对象的子项条目，使用 _writeTree 函数将其写入。Blob 条目通过 checkAndWriteBlob 函数进行验证。此阶段准备好条目，以便与 writeTree API 无缝集成。

async function processTreeEntries(fs, dir, gitdir, entries) {
  // make sure each tree entry has valid oid
  async function processTreeEntry(entry) {
    if (entry.type === 'tree') {
      if (!entry.oid) {
        // Process children entries if the current entry is a tree
        const children = await Promise.all(entry.children.map(processTreeEntry))
        // Write the tree with the processed children
        entry.oid = await _writeTree({
          fs,
          gitdir,
          tree: children,
        })
        entry.mode = 0o40000 // directory
      }
    } else if (entry.type === 'blob') {
      entry.oid = await checkAndWriteBlob(
        fs,
        gitdir,
        dir,
        entry.path,
        entry.oid
      )
      entry.mode = 0o100644 // file
    }

    // remove path from entry.path
    entry.path = entry.path.split('/').pop()
    return entry
  }

  return Promise.all(entries.map(processTreeEntry))
}

5. Tree 生成

使用我们定制回调配置的 walk 函数协调 tree 生成过程。最后一步是调用 writeTree 来物理创建将与 stash 提交关联的 tree 对象。

const entries = await _walk({
    fs,
    cache: {},
    dir,
    gitdir,
    trees,
    map,
    reduce,
    iterate,
  })

  if (changedEntries.length === 0 || entries.length === 0) {
    return null // no changes found to stash
  }

  const processedEntries = await processTreeEntries(fs, dir, gitdir, entries)

  const treeEntries = processedEntries.filter(Boolean).map(entry => ({
    mode: entry.mode,
    path: entry.path,
    oid: entry.oid,
    type: entry.type,
  }))

  return _writeTree({ fs, gitdir, tree: treeEntries })

这就是创建将与 stash 提交关联的 tree 对象的所有工作。

应用 stash 需要另一个 tree walk 操作。但是，这里不需要 iterate 和 reduce 回调。相反，map 回调直接处理应用更改。它封装了文件（blob）和目录（trees）的删除、添加和更新的逻辑。

export async function applyTreeChanges(
  fs,
  dir,
  gitdir,
  stashCommit,
  parentCommit,
  wasStaged
) {
  return _walk({
    fs,
    cache: {},
    dir,
    gitdir,
    trees: [TREE({ ref: parentCommit }), TREE({ ref: stashCommit })],
    map: async (filepath, [parent, stash]) => {
      if (
        filepath === '.' ||
        (await GitIgnoreManager.isIgnored({ fs, dir, gitdir, filepath }))
      ) {
        return
      }
      const type = stash ? await stash.type() : await parent.type()
      if (type !== 'tree' && type !== 'blob') {
        return
      }

      const currentFilepath = join(dir, filepath)

      // deleted tree or blob
      if (!stash && parent) {
        if (type === 'tree') {
          await fs.rmdir(currentFilepath)
        } else if (type === 'blob') {
          await fs.rm(currentFilepath)
        }
        return
      }

      const oid = await stash.oid()
      if (!parent || (await parent.oid()) !== oid) {
        // only apply changes if changed from the parent commit or 
        // doesn't exist in the parent commit
        if (type === 'tree') {
          await fs.mkdir(currentFilepath)
        } else {
          const { blob } = await readBlob({ fs, dir, gitdir, oid })
          await fs.write(currentFilepath, blob)
          // await fs.chmod(currentFilepath, await stash.mode())
        }
        if (wasStaged) {
          await add({ fs, dir, gitdir, filepath })
        }
      }
      return {
        path: filepath,
        oid: await stash.oid(),
        type: await stash.type(),
      } // return the applied tree entry
    },
  })
}

结论

Git 的 stash 功能为 Merkle 树提供了一个引人注目的用例，证明了其超越数据验证和同步的通用性，进入了差异跟踪和状态保存领域。Git 高效的数据组织、索引、查询和数据压缩技术——所有这些都通过 Merkle 树实现——都强调了该模型在规模化管理大型复杂数据集方面的强大功能。此外，多父提交的概念巧妙地实现了 stash 工作流，而不会破坏核心 Git 操作。

潜在的细化和增强途径包括：

冲突解决：为 stash apply 和 pop 集成冲突检测和解决机制。
简化实现：探索优化，例如为默认 stash 用例组合 tree walk。
专用 Stash 模式：支持“仅暂存”和“带未跟踪文件暂存”等高级场景，同时保留单独 tree walk 的灵活性。

对 Git stash 实现内部机制的探索非常有启发性。我预计将在初始 pull request 之后继续这些调查和改进。

历史

2024 年 3 月 9 日：初始版本