
BraKet 用 Tries 在 343 纳秒内解析 bash 命令能力
来源标题:Using Tries to resolve bash command effects in 343 nanoseconds
BraKet 利用 Tries 数据结构在 343 纳秒内完成 shell 命令能力分类,仅占约 3MB 内存。该工具旨在解决编码智能体频繁请求权限的问题,通过识别命令的实际能力(如文件读取、修改、执行)来替代逐条审批。其思路是用户更关心命令能力而非具体命令本身,例如不同 find 命令可分别归类为只读、修改或执行。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
TL;DR BraKet 利用约 3MB 内存,以超快速度对 shell 命令的能力进行分类。技术细节请跳至后面章节。
如果你在过去几年用过编码 agent,那么那段时间里你做过的最徒劳无功的事,很可能就是处理没完没了的权限请求。这就像做欺诈检测分析师:100 笔交易里有 1 笔可疑,1000 笔里有 1 笔确定是欺诈,但你并不知道是哪一笔,于是被迫全部监控。
沙箱可以帮助把外部损害降到最低,但它们静态地判定能力,无法替代沙箱内部的权限流程。
众所周知,用 shell 实现同一个结果有很多种方式,而 LLM 尤其擅长此道。编码 agent 的用户在大多数情况下关心的是命令的能力是什么,而不是实际执行了哪些命令。例如,
find src -type f -name '.ts' => filesystem:read find build -type f -name '.tmp' -delete | sort | wc -l => filesystem:mutate find src -type f -name '*.ts' -exec wc -l {} + | sort -nr => filesystem:read, execution:use
名义上这些都是 find 命令,但第一条在语义上属于 ls 这一类,第二条在语义上属于和 rm -f 同一类,第三条则属于和任意脚本执行同一类。
如果你把数千个 shell 命令、数万个子命令和数万个选项都算上,再考虑管道和重定向,最终会得到数百万种看似合理的组合,以及实际上无界的可能组合。
另一方面,如果你纯粹从命令能对你的系统做什么这个角度来思考,
而在全局层面,你有一个 unknown,只要命令的任何一部分是 unknown,整个命令就判定为 unknown。
在这种分类方式下,任何给定命令返回的要么是 unknown,要么是最多 10 种能力。
classify(X) 的输出总共可以用 31 位编码(10x3 + 1)
显然,要实现这一切,你首先需要两样东西:
我最初接触这个问题时,最初的想法是使用现成的解析器,比如 treesitter 和 mvdan/sh,两者都不错(顺便说一句,mvdan/sh 比 treesitter 略胜一筹),但它们引入了单独的依赖,各自有需要计入的资源消耗,最重要的是,先把东西解析一遍、再在完整的语法树上套用某些东西,这种感觉很别扭,而你本可以在解析阶段就完成这件事。如果你不需要完整的语法树,跑完整解析器就是浪费。
于是我开始寻找一个 typescript 解析器(因为 Dirac 目前是用 typescript 构建的,迁移到 rust 的事还悬而未决),然后找到了 Unbash。最终 agent 把整个东西重写了,但那是一个起点。
这个任务本身没什么有趣的,主要就是一个循环,反复调用一个能力还算不错的模型,对 906 个 shell 命令、它们的 7,288 个子命令以及总共约 90,000 个选项/标志进行分类。这个阶段基本上就是把上面的分类应用到单个命令 + 子命令 + 选项的层面,反复进行。
和许多学过 CS 的人一样,我对 trie 有偏爱。这个语料天然适合:命令路径和选项拼写共享大量前缀。你可以把它们存进两棵压缩 trie,由扁平数组支撑。一棵解析命令和子命令,另一棵解析选项拼写。命令专属的绑定表连接两者,让共享的选项拼写在特定命令的上下文中获得含义。
git ls-files --stage
在命令一侧,查找过程依次是 g → it → \0 → l → s- → files。\0 是命令路径各组件之间的内部隔符。共享前缀占用相同的节点,而非分支序列(如 it 和 files)则被装入单个压缩标签中。
git ls-files 的终端解析到命令记录 3377。该记录标识了打包的选项绑定数组中的一个范围:从索引 30329 开始的 40 条绑定。
在选项一侧,--stage 通过共享选项 trie 解析到拼写 ID 13352。这个 ID 标识的是拼写,它并不决定该选项对当前命令是否有效。
这项检查发生在两次查找交汇的地方。分类器在命令的绑定范围内二分查找拼写 ID 13352,并在绑定 30352 处找到它。这条记录同时提供了该选项的参数语法和它的能力判定。
这里,语法值 0 表示该选项不接受参数。判定 ID 3 索引共享的判定调色板,返回掩码 3:filesystem read。该命令的默认判定也是 filesystem read,因此 --stage 保持了这个分类。
因此,共享选项 trie 只存一次拼写,而各条单独的绑定赋予它命令专属的行为。一个全局能找到的拼写,仍然需要一条适用的绑定,才能被接受为选项。
你可以把所有我们关心的 Unix 命令效果打包进一个 1.2 MB 二进制文件中的两棵压缩 trie。
在一台 Apple M3 MacBook Air 上,单命令基准测试每次分类耗时 343 纳秒,预热后的进程占用常驻内存约 3 MB。
无论运行规模或单个命令的大小如何,内存使用都保持在 3MB 左右。更多细节见 BraKet。
GitHub README 中有安装配置细节和示例。
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。