jq实现原理——字节码

jq所用的DSL是一门dataflow language，程序中编写的几乎所有结构都是filter，函数(比如def foo(f) f;)接受filter为参数，产生filter。jq程序描述了如何把各个filter组合起来产生更复杂的filter，在执行时把输入数据(若干JSON)变换得到输出(若干JSON)。

jq独特的地方在于它的控制结构是由if和backtracking实现的。由于变量赋值后不可修改，因此迭代无法通过跳转和可变状态实现。

jq把程序编译成字节码后解释执行。字节码是栈式的(参看后缀表达式计算器、Forth)，处理的值是JSON，执行时当前结果和临时变量等都存放在data stack上，并提供了很多指令用于处理data stack。下面用表示data stack，左边是栈顶：

持续更新中

  • DUP：
  • DUP2：
  • POP：
  • LOADV(lvl,idx)：
  • STOREV(lvl,idx)：，另外
  • JUMP(pc)：跳转
  • JUMP_F(pc)：，若为false或null则跳转

jq支持函数调用，还支持嵌套函数，下面是两个例子： 

1
2
3
4
5
6
7
8
def range($x): range(0;$x);

def scan(re):
  match(re; "g")
  |  if (.captures|length > 0)
      then [ .captures | .[] | .string ]
      else .string
      end ;

Call stack中维护活动记录(见execute.c的struct frame)，存储的信息包括：函数第一条字节码地址bc、下一个环境env(下文会说明)、返回地址retaddr、返回caller后恢复的栈地址retdata、闭包和局部变量entries(下文会说明)。 Data stack和call stack共用一块存储空间。解释器的核心是struct jq_state，两个偏移量stk_top和curr_frame分别指向data stack和call stack的栈顶。栈中的每个元素带有指向后继的指针，call stack中元素的后继是离它最近的下一个call stack元素，data stack中元素的后继是离它最近的下一个data stack元素，因此call stack和data stack是不相交的两条链。栈元素虽然没有标签区分call stack元素还是data stack元素，但可以从表示栈顶的stk_top或curr_frame出发，沿着后继指针下溯找出所有特定栈的元素。

jq提供了很多控制结构，这里列出一些重要的：if-else、[]、foreach、reduce、try-catch、|(串联)、,(gen_both)。http://stedolan.github.io/jq/manual/比较旧，可以查阅https://github.com/stedolan/jq/blob/master/docs/content/3.manual/manual.yml。

if-else

if-else的翻译方案参看gen_cond： 

1
2
3
4
5
6
DUP           # <cond>会对栈顶元素进行处理，得到true/false，而then/else部分需要用到栈顶原值，因此DUP
<cond>
JUMP_F .L0    # 栈顶为false或null则跳转
<then>
.L0:
<else>

[]

[]翻译成一条字节码：EACH，例如： 

1
2
3
4
% jq --debug-dump-disasm '.[]'
0000 TOP
0001 EACH
0002 RET

其中--debug-dump-disasm选项用于打印字节码。

你一定好奇这条EACH指令怎么能发挥这么大魔力的，比如： 

1
2
3
4
% jq  '.[]' <<< '[1,2,3]'
1
2
3

翻译方案完全不像循环或递归！我也觉得这实在是太神奇了……继续看下去吧。

先引入一个概念：choice point stack，这个不是jq的术语，但我觉得和Prolog的Warren Abstract Machine里的choice point概念有相似处，因此捏造了这个名称。在jq里它和call/data stack共用存储空间，struct jq_state里用fork_top指向choice point stack的栈顶，它也以后继指针形成一条链，三个栈的链互不重叠。 Choice point stack的元素是choice point，类似于线程，choice point stack管理各个choice point，但同一时刻只有一个choice point在执行，从栈中弹出后(退出)也无法再恢复。Choice point的类型是struct forkpoint，包含如下字段：

  • stack_ptr saved_data_stack：choice point执行时使用的stk_top(data stack栈顶指针)
  • stack_ptr saved_curr_frame：choice point执行时使用的curr_frame(call stack栈顶指针)
  • int path_len, subexp_nest：TODO
  • uint16_t* return_address：choice point执行时使用的program counter值

Choice point的生命期从被创建出来开始算起，执行BACKTRACK或顶层的RET(顶层的RET用于返回输出)时结束。BACKTRACE的作用是从choice point stack上弹出栈顶替代当前的choice point。jq没有常规语言中的循环，用choice point机制模拟出循环的形式。

题外话：struct forkpoint里的这些字段可以看作保存的执行环境。不谈continuation，常规编程语言中用到环境保存的最熟悉的概念是异常处理，catch根据异常类型创建用于处理异常的活动记录，try则会unwind栈，上溯找到匹配的最近的异常处理活跃记录。

EACH执行时会区分首次执行(case EACH:。非backtracking模式执行时)和非首次执行(case ON_BACKTRACK(EACH)。Backtracking模式执行时)。 首次执行要求栈顶值为待迭代的容器，它会在data stack上压入迭代位置值-1，然后fall through到非首次执行的代码。 非首次执行时，从data stack上弹出迭代位置值和容器，获取容器中位置值+1处的元素，压入data stack。之后在choice point stack上创建一个choice point，其program counter是当前指令(EACH)。

字节码解释器(execute.c)中EACH的解释方案是让它第次被某个choice point执行时把容器的第个元素压入栈顶。下面看一个具体例子，--debug-trace可以产生指令trace： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
% ./jq --debug-trace '.[]' <<< [0,1,2]
0000 TOP
0001 EACH       [0,1,2] (1)
0002 RET        0
0
0002 RET                <backtracking>
0001 EACH               <backtracking>
0002 RET        1
1
0002 RET                <backtracking>
0001 EACH               <backtracking>
0002 RET        2
2
0002 RET                <backtracking>

EACH首次执行时创建了一个choice point(其中记录了当前已经处理过的位置0)，之后执行0002 RET(顶层RET)，jq_next返回到main.c process函数(驱动)的while (jv_is_valid(result = jq_next(jq))) {，在stdout打印0后jq_next再次被执行！jq_next非首次执行时会立刻进入backtracking模式(execute.c中的int backtracking = !jq->initial_execution;)，而choice point在经过ON_BACKTRACK(RET)中转后回到了EACH创建的记录！因此EACH被再次执行，几乎重复之前的步骤：压入新choice point和产生新一轮迭代的值。

,

参见compile.c中定义的gen_both。

看一个例子： 

1
2
3
4
5
% jq --debug-dump-disasm '.,.'
0000 TOP
0001 FORK 0005
0003 JUMP 0005
0005 RET

其中JUMP 0005是冗余的，在这里,就对应一条FORK。

FORK的名称应该源自Unix进程拷贝函数fork，作用是根据参数program counter创建choice point(其他参数如data/call stack等都继承当前choice point)，而当前choice point则继续执行下一条指令。 和前面EACH的情况类似，当前choice point产生输出退出后被驱动(main.c的process函数)再次执行，保存的choice point恢复并产生下一个输出。

现在可以理解empty了，jq -n '1,empty,3'会输出两个值：1和3。两个逗号会用FORK创建两个choice point，而empty会翻译成BACKTRACK，即从choice point stack上弹出choice point替代当前choice point。

foreach

参见compile.c中定义的gen_foreach。

foreach EXP as $var (INIT; UPDATE; EXTRACT)的翻译方案是： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
DUP
<init>
STOREV <var>

FORK .L1

DUPN
<source>
LOADVN <var>
<update>
DUP
STOREV <var>
<extract>
JUMP .L0

.L1:
BACKTRACK

.L0:

DUPN和LOADVN涉及issue #618，理解的时候可以分别看作DUP和LOADV。

垃圾收集

引用计数

TODO