正则如何驱动索引查询？深入剖析tgrep的QueryPlan分解与Bloom过滤技巧

正则如何驱动索引查询深入剖析tgrep的QueryPlan分解与Bloom过滤技巧【免费下载链接】tgrepTrigram-indexed grep with a client/server architecture for fast regex search in large codebases locally项目地址: https://gitcode.com/gh_mirrors/tg/tgreptgrep 是一款基于三字符组trigram索引的正则搜索工具采用客户端/服务器架构专为大型代码库的极速检索设计。本文将带你读懂它的核心引擎一条正则表达式如何被分解成 QueryPlan 查询计划又如何借助Bloom 过滤技巧在索引中精准筛选候选文件——这正是 tgrep 在 chromium 级别仓库上快 ripgrep 数十倍的关键。一、先搞懂tgrep 的三字符组索引是什么 传统 grep 每次搜索都要打开每个文件逐行匹配。tgrep 换了一个思路提前把整个仓库嚼碎建好索引。建索引时tgrep 把每个文件的内容切成所有重叠的 3 字节窗口即 trigram例如hello会产生hel、ell、llo三个单元。每个 trigram 被打包成一个 24 位的整数a16 | b8 | c最多约 1670 万个不同值零哈希冲突。实现见 trigram.rs。索引以三个二进制文件落盘格式定义在 ondisk.rs文件作用lookup.bin按 trigram 排序的目录页二分查找直达帖子列表index.bin拼接的帖子列表每条记录仅6 字节file_id(4) loc_mask(1) next_mask(1)files.binfile_id 到文件路径的映射表 每条帖子记录只有 6 字节这是后文 Bloom 过滤技巧能塞进索引的前提。二、QueryPlan 分解把正则翻译成与/或查询树 用户输入foo.*bar后tgrep 不会直接丢给正则引擎暴力扫库而是先由 query.rs 中的build_query_plan解析正则的 HIR正则语法树提取出其中必然出现的字面片段生成一棵QueryPlan查询计划树。计划树只有三种节点逻辑非常清晰节点含义对应操作And([...])列出的每个 trigram都必须存在于文件中各帖子列表求交集Or([...])任一分支命中即可对应|或选言各分支结果求并集MatchAll提取不到任何可用 trigram放弃收窄全量扫描兜底几个关键分解规则见decompose_hirquery.rs字面量mutex_lock直接拆出mut、utex、tex… 全部 trigram组成And节点拼接相邻字面片段共享同一个And池中间的可索引子结构递归提取选言foo|bar拆成两个子计划再用Or包裹可选量词foo?min0可能整体消失只能降级为MatchAll过短模式不足 3 字节的ab无法产出 trigram同样MatchAll。分解完成后还有一步simplify化简query.rs按哈希排序、去重。细节很有讲究——如果同一个 trigram 在不同上下文出现且下一个字节不一致会主动清空 next_mask 约束宁可少过滤也不误杀真命中。 这个设计保证了正确性底线计划只可能多留候选文件绝不漏掉真命中最后仍由真正的正则引擎逐一验证。三、Bloom 过滤技巧next_mask 如何消灭假阳性 ✨只有 trigram 交集还不够。搜索mutex_lock时一个文件里分别出现mutex和clock交集检查也可能误判——这就是假阳性。tgrep 的答案是给每条帖子记录再压两个 1 字节掩码1️⃣next_mask—— 8 位 Bloom 过滤器对 trigram 后紧跟的那个字节用乘法哈希byte * 0x9E 5 7散列到 8 位中的一位trigram.rs。查询时TrigramQuery自带从 HIR 字面量算出的expected_next期望字节只要next_mask bloom_hash(expected_next) ! 0就通过。代价每条帖子多 1 字节收益把trigram 出现但后接字节不对的假候选在索引层就拦下安全性Bloom 过滤器只会产生漏报为通过的假阳性、不会产生假阴性——真命中的字节必然被建索引时点亮绝不会误杀。2️⃣loc_mask—— 位置掩码记录 trigram 出现偏移offset % 8的位图配合左旋 1 位与相邻 trigram 掩码做 AND可判断两个 trigram 是否相邻出现check_adjacencytrigram.rs进一步压缩散落各处的假阳性。四、执行流程从 QueryPlan 到候选文件集合 ⚡计划建好后execute_plan_with_masksquery.rs在索引上执行按帖子列表长度排序从最小的列表开始——集合越小交集收敛越快对每对列表做有序双指针求交逐条叠加next_maskBloom 检查中途候选集为空立即短路退出Or分支递归执行后用平衡归并求并集union_many_sorted还会自适应切换两两归并避免列表膨胀。对于 ripgrep 风格-P的 PCRE 模式含环视等regex-syntax不认识的语法tgrep 还有relax_for_indexing模式松弛机制query.rs安全地删掉零宽环视、把原子组(?…)放宽为(?:…)只放宽、不收紧匹配语言让(?!//)ExchangePrincipal这类模式照样能靠ExchangePrincipal的 trigram 走索引而不是退回全库扫描。整条链路在 CLI 侧的接入点见 search.rs构建多模式计划 → 执行掩码感知的计划求交 → 只对候选文件跑真正的正则匹配。五、效果如何索引收窄 Bloom 过滤 并行验证的组合在大仓库上收益显著。根据 BENCHMARKS.md 的 2026-08-24 基准索引预建、每次新进程客户端计时仓库文件数Linux 加速比最佳平台chromium/chromium504,3513.81xmacOS 15.8xmozilla/gecko-dev387,8417.36xmacOS 51.9xtorvalds/linux95,8319.38xWindows 34.8x而这一切的源头就是本文拆解的两件事QueryPlan 的正则分解负责找对文件Bloom 掩码负责排除假朋友。理解了它们你就掌握了 tgrep 快在哪里。小结新手快速上手路径 安装后运行tgrep serve .启动服务端自动建索引另开终端tgrep -- fn main .发起正则搜索模式含字面片段≥3 字节→ 走 QueryPlan 索引收窄模式如.*、过短串 → 自动降级全扫描结果同样正确。想继续深挖从 tgrep-core/src/query.rs 的decompose_hir和 tgrep-core/src/trigram.rs 的extract_merged_masks读起配合 fuzz/fuzz_targets/fuzz_query.rs 等模糊测试看边界用例是最佳路径。【免费下载链接】tgrepTrigram-indexed grep with a client/server architecture for fast regex search in large codebases locally项目地址: https://gitcode.com/gh_mirrors/tg/tgrep创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考