Internals: the stack - troyp/jq GitHub Wiki

The jq interpreter stack

The jq interpreter's stack is about what one would expect: a stack. It contains three kinds of things:

• jv values (the C API's representation of values with JSON representations)
• jq function call activation frames (frames)
• "fork points"

Stack allocations are "stack blocks", which chain back through a "next" pointer pushed on the stack before the new stack block. Popping the stack returns the previous stack block's address (via this next pointer), but does not actually pop the given stack block if it isn't at the top of the stack.

Pointers to anything in the stack are always written as negative integer values relative to the top of the stack. This is important: it allows jq to use realloc() to grow the stack without having to traverse the stack to fix-up pointers.

Stack addresses are expressed as relative to the end of the jq stack as allocated (from the C heap).

jv values are fixed-sized.

Frames are fixed-sized for any given function. The size of a frame can always be determined from context. Local variables in frames store jv values.

Fork points are fixed-sized.

Fork points mark places where the stack was "forked", as if a new stack had been allocated, as if forks were rather simple co-routines.

The jq interpreter state structure records the current frame and fork point "addresses" (i.e., stack indices, not absolute memory pointers).

Cleanup of the stack is simple (see stack_restore()): find the current frame, free all jv values in the frame and past it, pop the frame, repeat until we reach a fork point. Complete cleanup consists of repeatedly applying stack_restore() until nothing remains on the stack.

Look ma', no leaks!

Fork points are used in the backtracking machinery: on backtrack we stack_restore() to the nearest fork point and resume the interpreter there (with a flag set to indicate that we've backtracked; some opcodes act differently on backtrack). Backtracking basically runs the bytecode backwards, sort of, popping off stack blocks as it goes until it finds an instruction that has special backtracking handling, which might resume forwards execution. Fork points are the key to implementing, for example, the comma operator.