skip to content
OnionTalk

git中的二分查找– git bisect

二分查找是一种大家都熟悉的算法。这种算法由于套路非常的清晰,在程序开发中被广泛使用。很常见的一个例子就是使用二分查找去进行程序的debug,逐步缩小代码区间最终确定问题。循着这个思路,在多人合作的场景下,如果某次你pull代码之后发现某些代码不能工作了,你也可以通过二分查找的方式找出出问题的commit。而git bisect就是git内置的二分查找命令。

从二分查找说起

二分查找是一种很简单的算法,适用的对象是 已经排序的数组 。一个最简单的二分查找的实现如下。

/**
 * @param {Array} sortedList 排好序的list
 * @param {number} target 需要检索的值
 * @return {number} 检索到的值的index,未检索到返回-1
 */

function binarySearch(sortedList, target) {
  let left = 0;
  let right = sortedList.length - 1;
  let middle = parseInt((right + left) / 2);
  while (sortedList[middle] !== target && left !== right) {
    if (sortedList[middle] > target) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }

    middle = parseInt((right + left) / 2);
  }
  return sortedList[middle] === target ? middle : -1;
}

一个简单的递归实现如下

/**
 * @param {Array} sortedList 排好序的list
 * @param {number} target 需要检索的值
 * @return {number} 检索到的值的index,未检索到返回-1
 */

function binarySearch(sortedList, target, left = 0, right = sortedList.length - 1) {
  const middle = parseInt((right + left) / 2);
  if (sortedList[middle] === target || left === right) {
    return sortedList[middle] === target ? middle : -1;
  }
  if (sortedList[middle] > target) {
    return binarySearch(sortedList, target, left, middle - 1);
  } else {
    return binarySearch(sortedList, target, middle + 1, right);
  }
}

这里是 usfca 做的一个二分查找的动画演示 https://www.cs.usfca.edu/~galles/visualization/Search.html

git 中的二分查找

让我们进行一下思路的迁移,先看一看一条 git branch 上的 commit 记录。

其实很容易发现我们的 git commit 历史其实在某种意义上很像一个 已经排序的数组 ,所以当我们想找出某个有问题的 commit 时,二分查找很自然的成为了我们首选的搜索算法。

git bisect

git bisect 就是 git 内置的二分查找工具,具体用法如下。

git bisect start # 开始二分查找
git bisect bad [?index] # 标记错误区间右边界 index 可以是commit hash / tag等。如果不传index那么默认会标注HEAD为bad
git bisect good [index] # 标记错误区间左边界
# 最后错误区间为(good, bad]

当确定区间之后,bisect 会提示你区间内有多少个 commit,并且最多几次查找可以查找完。同时你会被 checkout 到区间中心的那个 commit 上。

如果当前的 commit 仍是坏的 commit, 你可以继续使用 git bisect bad 进行标注,git bisect 会应用二分法帮你缩小区间并且 checkout 到区间中心的 commit 上,这个过程会一直持续直到二分查找结束。而你最后停下来的 commit 就是那个有问题的 commit。

可视化这个过程大致如下

使用 git bisect run 来自动标注

git bisect 提供了 git bisect run 这条命令可以在某些情况下帮助我们进行自动化标注。

假设在某个 commit 中我们的测试挂掉了,我们想找出这个 commit。我们使用 git bisect 的思路是在每次查找完后运行测试,根据测试结果去标注 good/bad。

yarn test
git bisect good # or bad 取决于test结果

以上两条命令可以合并成一条命令

git bisect run yarn test

git bisect run 后面接受的是一条 shell 命令,如果这条命令以 exit(-1) 终止, git bisect 会自动把当前 commit 标记成 bad,否则标记成 good。

一些有用的 tips

  • 在每一次步进的时候,你可以通过 git bisect visualize 来预览当前的 commit 区间。
  • 你可以通过 git bisect log 来查看自己的每一次 good/bad 标注。
  • 如果你记录了 git bisect log, 你可以通过 git bisect replay [log-file] 来重放你的 git bisect 操作。

参考资料

Get good with git: bisect

https://git-scm.com/docs/git-bisect