Typing a query language stack machine in C
- YT :: https://www.youtube.com/watch?v=eGvUK-3RmDs
- Original title :: Issue Tracker in C
A recreational programming session extending the query language of Tatr, Tsoding's command-line issue tracker in C, which he has worked on on and off for six months and wants to open source soon. The goal looks trivial - filter tasks by priority - but adding a second type to a boolean-only stack machine cascades into tagged unions, source location tracking through both the op codes and the stack items, runtime type checking with pointed error messages, and precedence climbing in the parser. Most of the value is in watching that cascade be managed deliberately rather than in the feature itself.
What Tatr is
Tasks live in a tasks/ folder at the project root, one folder per task, each named by a timestamp ID and holding a task.md. The format is markdown-adjacent, not markdown: a # title line, then properties (status open/closed, priority, comma-separated tags), then arbitrary free text the tracker ignores. Output uses the compiler-error format, so Emacs can parse it and jump to the task.
The existing query language supports conjunction, disjunction, tag matching, negation, and a tagged predicate - e.g. .release and not .scope, or not tagged to find untagged tasks. There is also a summary subcommand showing tag frequencies. Queries compile to byte code for a stack machine whose stack held only booleans; a debug flag dumps the op codes.
The design constraint that shapes everything
He wants priority < 100. He cannot use < as a token, because the language is typed at a shell prompt and < 100 is an input redirection - bash will fail with "no such file". So the operators end up as LT and GT (with =lt=/=gt= aliases considered; "more aliases is better"). The same reasoning kills bare parentheses later, which also need escaping in bash.
One new type, a lot of new machinery
Adding integers is not two op codes, it is: OP_INTEGER, OP_LT, OP_PRIORITY, a new stack element type, and - the real cost - type checking that never had to exist before. The stack element becomes a tagged union:
typedef struct { Stack_Item_Type type; String_View src; union { bool as_boolean; long as_integer; }; } Stack_Item;
Naming the union members as_boolean / as_integer makes item.as_boolean read like a cast at the use site. Constructor helpers stack_boolean() / stack_integer() exist mostly because da_append is a macro and a braced initializer's commas would be read as extra arguments.
He uses his standard trick of a static_assert on STACK_ITEM_TYPE_COUNT at every place that must be updated when a new type is added, so adding one breaks the build in exactly the right spots.
Location tracking at runtime
The interesting part. Error reporting already existed for parse errors: the compiler keeps original_src and the current src, and the cursor position is just their difference. Runtime type errors need the same thing, so both the op codes and the stack items carry the source slice they originated from.
The question of what location a computed value gets answers itself: OP_AND pops two items and pushes one, and the new item takes the location of the and operation. So the last item on the stack always carries the location of the top-level expression, which is exactly what is needed to report "expected boolean, got integer" for the whole query. Tsoding is visibly delighted that this falls out for free.
One bug found along the way: the reported cursor pointed at the end of the token, because src had already advanced - the parser's saved_src is the right thing to store.
The result: not priority reports "expected boolean but got integer" with a cursor under the offending token. His comment - "already better than the majority of SQL implementations". He makes a broader point here: diagnostics are part of a compiler's interface, not an afterthought. If the diagnostics are bad, the interface is bad. He is scathing about commercial databases that answer a huge expression with a bare "syntax error".
Compiler-assisted refactoring, and backtracking out of it
Midway he discovers that one compiler-assisted refactor (threading src through op construction) triggers a second (the boolean stack becoming a typed stack), and doing both at once is too much to hold in your head. So he reverts the first, finishes the second, then redoes the first. His advice: notice when you are tangling yourself up, and do not be afraid to reset and start over - the second attempt knows which refactor to do first.
The return-value refactor is the counterexample. Changing task_matches_query from bool to an enum (TMR_MATCHED, TMR_MISMATCHED, TMR_ERROR) does not break any call site, because C happily reads an enum as a boolean. "C is a stinky boomer language, it's so weakly typed" - the reason he had to find the call site by hand. He also grumbles about break exiting the nearest switch while continue exits the nearest loop; the resulting switch is accidentally ordered by escape scope (break < continue < return < unreachable() aborting the program).
An API design remark: expect_type grows into pop_type, which pops and type-checks in one step, because with binary operators you need to check two operands. He notes he did not know what the API would look like before the stream - he brute-forces the problem and lets the friction points suggest the shape.
Parsing integers, and a memory stamp paying off
Integer parsing uses strtol (chosen over strtoull so negatives work), which needs a NUL-terminated string, so the key is copied into the tmp arena (8 MB global byte array, save a checkpoint before, rewind after). Validity requires both that strtol consumed something and that *end_ptr = 0=, so 20abc is rejected rather than parsed as 20.
It failed on the first run, and the debugger showed why: a recently added feature - stolen from Jonathan Blow - that stamps freed tail memory in the tmp arena with 0xCC on rewind. The dangling pointer was immediately obvious. Chat supplies the reasons 0xCC is the traditional stamp: a visually distinct bit pattern in hex and binary, and int3 (breakpoint) on x86, so it grabs attention whether interpreted as data or executed as code. Windows uses 0xCD.
He added the stamping out of paranoia about temporary allocations and had never seen it fire before. It caught a real bug on stream, live.
Precedence climbing
Comparison binds tighter than and, so the chain becomes expression → or → and → LT/GT → primary, with LT and GT at the same precedence level parsed in one loop that breaks out when it sees an unrecognised key. not stays a primary. He notes =EQ=/=NEQ= belong in the same comparison cluster and will be added the same way.
Two things then worked first try: negating a comparison (not (priority lt 20)) as emergent behaviour of a properly structured grammar, and - less happily - a test caught a real bug where not was parsing an and expression instead of a primary. "Test your code, chat."
He deliberately refuses to add arithmetic ("34 + 35") to the query language: he only introduces things he has a use case for, otherwise it is machinery for no reason.
Q&A odds and ends
- On being asked whether he will move to Jai when it goes public: he finds the whole question perverse. Languages are cars. Even on a Jai project he is reading and patching C dependencies, so he is using two languages at once. That is just how programming works.
- On avoiding over-engineering: be lazy and sloppy. Over-engineering takes effort; not wanting to spend it is a reality check. He says this is genuine advice.
- On code scraping: if you don't want your code scraped, don't publish it. Same energy as "if you're being cyber-bullied, turn off the computer."
- On translating code between languages with LLMs: easy, and he never considered it programming anyway - it is mechanical enough to automate even without LLMs, though some patterns (his Nim file edit that needed a recorded macro applied N times) genuinely resist find-and-replace.
- The aside that lands hardest: "very powerful people and companies are pouring money every day to make you hate computers. They will fail. Computers are fun, they always were and always will be."
The work was committed to a repo on a laptop in the room, not GitHub - the code still needs cleanup before release.