beagrep，0.23秒grep两个G的代码

1 简介

多年前还在上大学的时候，读到LDD（Linux Device Driver）第一版的前言，作者说这本书是他花了很多小时，仔细grep内核源代码才写出来的。所以后来我也试着坚持用grep这样的工具阅读源代码。很长一段时间内grep都是足够用了的，即使像Linux内核这样的几百兆的代码，grep起来也不会太慢。

直到有一天grep了一下Android的代码，花了我半个小时，终于觉得太慢了，受不了了。

后来发现Linux下开源的桌面索引、搜索软件beagle，灵机一动，先用beagle粗略地搜一遍可能匹配的文件，然后再单在这些文件内grep，不就可以大大节省时间吗？

非常热血地向你推荐beagrep（beagle + grep），在两个G的Android代码中grep readlink函数，只需要0.23秒！

更加热血的是，beagrep在Windows下也能用（更新：在MacOS下也可以）！

（本文的英文版在这里，可能会比中文版更新）。

2 安装

2.1 Linux下安装

2.1.1 用.deb包安装

我在github上提供了4个.deb包，分别是给ubuntu 10.04, 11.10, 12.04和 debian testing (wheezy)的，如果你的Linux发行版恰好是这几个中的一个，那你可以在这里直接选一个.deb包下载安装，以ubuntu 12.04 (precise)为例：

dpkg -i beagrep_0.4.0-1_amd64-ubuntu-precise.deb # 会出错，因为一些依赖的.deb包没装上
apt-get -f install # 装上依赖的.deb包，修正上面的错误

更新（2014-05-03） 目前编译出来的.deb包在ubuntu 12.04上测试发现运行会抛异常，建议用下面自己编译安装的方法。

2.1.2 编译安装

如果你需要自己编译，以ubuntu precise为例：

git clone https://github.com/baohaojun/beagrep.git -b for-ubuntu-precise
# you can also run "git branch -a" to see other versions of ubuntu supported

# Install build dependencies. You can open debian/control and check
# the build dependencies and install all of them. The following
# command will try to install them automatically, but if it fails then
# you need figure out which packages to install manually. Good luck!
# Or you can contact me for help.
apt-get install $(cat debian/control | perl -ne 'print if m/Build-Depends/..m/Standards-Version/'|grep -v -e Build-Depends:\\\|Standards-Version|perl -npe 's/,/ /g')

# do the build
(set -e; autoreconf -i; ./configure; make -j4; sudo make install; echo OK)

2.1.3 自己编译deb包

这一节见英文版

2.2 Windows下安装

2.2.1 安装依赖软件

需要安装cygwin和mono的Windows版。Cygwin建议完全安装，Mono建议安装到默认目录下。

2.2.2 下载代码

git clone git://github.com/baohaojun/beagrep.git -b for-windows

2.2.3 编译安装

cd beagrep
bash build-win.sh

3 使用

3.1 快速smoke test

cd /tmp; mkdir $$; cd $$; echo main > 1.txt; mkbeagrepidx; beagrep -e 'main' --grep '--color=auto'; true; cd ..; rm $$ -rf

如果beagrep安装配置没有问题的话，在上面的命令输出的最后，你可以看到类似于 /.cache/11468/1.txt:1:main 。

3.2 创建索引

到想阅读的源代码目录下，以android为例

cd ~/src/android
mkbeagrepidx

这一步第一次花费的时间较长，在Linux下android代码索引大概需要半个小时（跟以前单独用一次grep的时间差不多）。我建议可以用crontab定时在半夜做这个工作。

但是如果以前已经生成过index，则再做一次花的时间应该可以大为缩短（几分钟），因为那些没有更新过的文件（按照文件时间戳和index数据库里记录的时间戳对比）不需要重新生成 index。

另外，已经生成过index的情形下，如果你只想重新index某个子目录，则可在该子目录下调用 mkbeagrepidx ，程序会问你是否想更新上级已有的index库，如果选是，则取决于该子目录的大小，可能更新index的时间只需要几秒钟。

3.3 man page for mkbeagrepidx

mkbeagrepidx is a simple wrapper over beagrep-build-index. You can configure it for which directories to ignore using --deny-directory-pattern option. By default,

The $PWD/out is ignored, because it contains android build output
The */.git is ignored, because of well known reason
The */.repo is ignored, for the same reason.

The syntax is comma separated shell glob patterns, and you can check how it is converted into regular expression by examing the beginning of mkbeagrepidx output.

You can customize it using several ways, in the order of increasing priority:

Not customize it, then
```
"$PWD/out,*/.repo,*/.git"
```
will be used.
Overide it in ~/.mkbeagrepidx.rc, setting the BEAGREP_IGNORE_DIR_PATTERNS environment variable:
```
export BEAGREP_IGNORE_DIR_PATTERNS="$PWD/out,*/.repo,*/.git"
```
Overide it in the .mkbeagrepidx.rc in the current working directory, same as the above.

Overide it on the command line:

mkbeagrepidx --deny-directory-pattern "$PWD/out,*/.repo,*/.git,*/.svn"

3.4 用beagrep搜索

在想阅读的代码目录下：

cd ~/src/android
beagrep -e "readlink"

3.4.1 man page for beagrep

Here's a list of all arguments that beagrep takes:

beagrep -e REGEXP_MATCH [-p REGEXP_PATH] [-a ADDITIONAL_WORDS] [-v REGEXP_REVERSE_PATH] [-i] [-f] [-l] [--grep GREP_OPTIONS] [-a]

-e REGEXP_MATCH

This is the minimum required arguments. For e.g., beagrep -e readlink

The REGEXP_MATCH serves 2 purposes:

First, it is computed into whole words for querying beagle. For e.g., l] [--grep GREP_OPTIONS] above should be matched with the following REGEXP: l\] \[--grep GREP_OPTIONS\], but it should be converted into 4 words: l grep GREP OPTIONS for beagle.
Second, it is used as the regexp for grep to work on.

-a ADDITIONAL_WORDS

means to add more words into the beagle query. This is useful by increasing the work beagle need to do, but reduce the possible workset grep need to work on.

-p REGEXP_PATH

means to limit the search result to those files whose pathname matches REGEXP_PATH.

-v REGEXP_REVERSE_PATH

means to exclude those matched files whose pathname matches REGEXP_REVERSE_PATH.

-i

means to do case insignificant grep.

-f

means to do the match in filenames only. For example,

beagrep
        -e readlink -f

will only show results like readlink.h and readlink.c.

This is very useful for finding files. Note that when -f is used, the beagle querying words will be computed differently: only the basename will be used, and filename: is prepended onto each words.

-l

means to list the beagle matched list of files directly, without running grep to match on them.

–grep GREP_OPTIONS

means to pass additional arguments to the grep invocation. For e.g., the -l argument can be passed to beagrep directly, or it can be passed using --grep, they mean different things:

beagrep -e "hello world" -l will show a file containing "hello wonderful world", but beagrep -e "hello world" --grep -l will not show that file as a match.

4 原理

beagrep是一个非常实用主义的软件，它之所以有用，是基于以下几条观察：

4.1 grep pattern ，通常是很简单的

或者说，可以分解为几个很简单的子pattern：整字（whole words）。

比如在android代码库里grep这样一个看起来很复杂的pattern：

"JsonToValue(\"\\\\\"hello world\\\\\"\","

实际上，它包含了几个简单的子pattern，也就是那三个完整的英文单词： JsonToValue hello world 。要匹配这个复杂的pattern，一个必要而非充分条件是需要能匹配所有的这三个子pattern。但这三个子pattern已经不需要正则表达式这么强大的工具去匹配了，我们把它交给beagle，一个桌面搜索引擎工具。它可以飞快查出在android代码里，哪些文件能匹配所有这三个子pattern（也即包含所有这三个英文单词）。

事实上，只有一个文件满足这个要求：

$beagrep-files 'JsonToValue hello world '
Beagrep index found at /home/bhj/.cache/for-code-reading//home/bhj/src/gingerbread-tegra/.beagrep
/home/bhj/src/gingerbread-tegra/external/chromium/base/json/json_reader_unittest.cc
/dev/null

所以，可以想象在这个文件集上grep之前那个复杂的pattern能有多快得到结果。

beagrep -e "JsonToValue(\"\\\\\"hello world\\\\\"\","
pat is: 'JsonToValue("\\"hello world\\"",'.
beagrep query argument `JsonToValue hello world '
Beagrep index found at /home/bhj/.cache/for-code-reading//home/bhj/src/gingerbread-tegra/.beagrep
/home/bhj/src/gingerbread-tegra/external/chromium/base/json/json_reader_unittest.cc:168:  root.reset(JSONReader().JsonToValue("\"hello world\"", false, false));
Unmatched ( in regex; marked by <-- HERE in m/JsonToValue( <-- HERE ""hello world"",/ at /home/bhj/system-config/bin/beagrep line 98.

总之，完整的英文单词是beagle处理起来最得心应手的，而巧得很的是，我们几乎从来都只用完整的英文单词，而不是半个单词去grep代码。

4.1.1 题外话，用emacs自动创建pattern

从上面可以看出，在文本中出现的match的字符串是：

JsonToValue("\"hello world\"",

因为正则表达式的元字符、shell的转义字符、引号的关系，我传给beagrep的pattern是复杂得多的：

"JsonToValue(\"\\\\\"hello world\\\\\"\","

如果这些反斜杠要自已用手指头数着挨个数进去的话，就悲剧了。所以当然不是这样的。当你在Emacs里选定一段文本，按下C-u M-x grep之后，Emacs会自动帮你计算出需要如何添加反斜杠，以把这个“纯”字符串变成一个可以跟它匹配的正则表达式（其实也是字符串，只是加了一些奇怪字符，有特殊意义的字符串）。（但是其实现有点bug，我的 .emacs 里有对 grep-default-command 和 grep-shell-quote-argument 的修正）。

4.2 grep 关键字，通常是有趣的

beagrep之所以能大大加快grep的速度，是因为它能大大缩小grep需要处理的文件集。

注意，是大大地缩小，而不是小小的缩小一点点。这有一个要求，就是你给beagrep（也就是最终的beagle）的英文单词，必须是有趣的。至少要有一个以上是有趣的。有趣的越多，加速的越大，像上面那个例子，只有三个有趣的英文单词，就把文件集缩小到只剩一个。

试想一下，如果你想grep is 这个最常见的英文单词在android里出现的位置，几乎所有的文件都包含了这个单词，不管是文档还是代码（代码的注释里极可能出现 is ）。所以即便用beagle，得到的文件集和整个android代码是相当的，没有加速的空间。因为 is 实在是太不有趣了，所以你通常不会单独去grep它。

所以：

不要单独grep include，因为它不有趣，几乎所有C/C++源文件、头文件都会包含这个单词。
不要单独grep import，因为它也不有趣，几乎所有java文件都会包含它。

等等等等。

包昊军的博客