Tsonnet #46 - The devil in the details #2
Adding missing cycle-check variants to the type checker, then replacing the entire proactive AST-walking approach with on-demand detection during translation.
Welcome to the Tsonnet series!
If you’re not following along, check out how it all started in the first post of the series.
In the previous post, we closed every scope-checking blind spot exposed by removing catch-all patterns — conditionals, field access chains, function definitions, function calls, and closures:
The type checker is next. Let’s go.
What was missing
The cycle checker in lib/type.ml had a check_expr_for_cycles function that walked the AST looking for cyclic references before translation. It covered the basics — Ident, BinOp, Array, ParsedObject, ObjectFieldAccess, If, and Seq — but we still had the type variants below a (* TODO *) comment from earlier to properly cover:
Terminal variants are fine — literals can’t reference anything. But FunctionDef, FunctionCall, Closure, and IndexedExpr absolutely can introduce cycles. Their default parameters, callee expressions, and index expressions all need checking. The catch-all removal in #44 made the gap explicit; now it’s time to fill it in.
Phase 1: Adding the missing handlers for cycle checking
Function definitions and closures
Function bodies are lazy — typed only when called. Checking the body at definition time would reject unused recursive functions too early. Default parameters, however, are typed eagerly during translate_function_def, so those need cycle checking:
Same logic for both FunctionDef and Closure — they share the lazy-body semantics.
Function calls
Every argument to a function call — both positional and named — can introduce a cycle, plus the callee itself:
Indexed expressions
Indexing a lazy variable (local a = a[0]) needs special care. If the variable being indexed is an array and the index is a constant integer, we can resolve directly. Otherwise, we check the general case:
Seq and locals
Seq was already handled, but only naively — it didn’t account for local bindings introducing new scopes. If local a = (local b = b; b) shadows an outer binding, the inner cycle should resolve against the local scope, not the outer one. The new check_seq_for_cycles collects consecutive Local bindings, builds an extended environment, computes reachable bindings, and only checks those that are actually used in the body.
I’m intentionally dropping the collect_locals and reachable_bindings details here — the pattern is similar to what translate_seq already does. The full diff has the gory details.
The ObjectVar rabbit hole
Handling ObjectVar references in field access chains forced a deeper change. When the interpreter looks up a variable during interpret_object_field_access and finds a RuntimeObject, it needs to record that the variable now points back into the current object — or risk losing cycle detection on self-referential object fields accessed through a variable.
The fix cascaded into TruntimeObject: it now carries its own environment (tsonnet_type Env.Map.t) instead of reconstructing it ad-hoc during field access. This is something I probably should have done from the start — lazy-evaluated objects need their environment to resolve self and $ correctly.
The interpreter side handles the same pattern: when interpret_ident evaluates a variable holding a RuntimeObject, it injects an ObjVarRef pointer into the object’s environment so field accesses through that variable can detect cycles.
Phase 2: Proactive → on-demand
By this point, check_expr_for_cycles had grown to cover a dozen expression variants, each with its own handler function. The approach was getting unwieldy — every new expression variant needed a new check function, and the AST-walking traversal duplicated what translate already did.
I had a classic spider-sense moment: why am I proactively walking the AST when translation already visits every expression? The answer: I don’t need to. Cycle detection can be on-demand — during translation, when we encounter a lazy binding that’s already being translated, that is the cycle.
TranslationKeys
I replaced the ad-hoc translating_fields : ObjectFields.set with a proper key set:
And a helper that wraps the common check/set/remove pattern:
What went away
The entire proactive cycle-check infrastructure — about 150 lines:
check_cyclic_refscheck_expr_for_cyclesiter_for_cyclescheck_object_for_cyclescheck_object_field_for_cyclescheck_object_field_chain_for_cyclescheck_conditional_for_cyclescheck_function_def_for_cyclescheck_function_call_for_cyclescheck_closure_for_cyclescheck_param_defaults_for_cyclescheck_seq_for_cyclescheck_indexed_expr_for_cycles
All gone. Translation itself is now the cycle detector.
What changed
Instead of walking the AST before translation, each translate_* variant registers its key when it starts processing a lazy binding:
translate_ident — was manually pushing/removing from translating_fields, now uses with_translating:
translate_indexed_expr — wraps lazy resolution in with_translating:
translate_object_field_access — field lookups register TranslatingObjField keys. The last field in the chain gets the cycle check; intermediate numeric lookups skip it (arrays/strings can’t cycle):
translate_object — the old check_cyclic_refs post-loop over entries is gone. The proactive warnings for unreachable cyclic fields are replaced by the on-demand detection that fires when the field is actually accessed. This also removed the separate pre-check of ObjectConditionalField keys — the attr translation handles it naturally.
translate_seq — the old proactive cycle check over reachable locals is replaced by removing shadowed bindings from translating_bindings before processing the body, so that local shadowing doesn’t falsely trigger cycle detection against outer bindings.
New behaviour note
The on-demand approach detects cycles at access time instead of at definition time. This means:
Fields that are never accessed never trigger cycle errors. A cyclic field in an untouched branch of an object is silently accepted. This is more correct — Jsonnet is lazy, and lazy evaluation means unused bindings shouldn’t error.
Error positions change. Errors now point to the use site, not the definition site. This is visible in the cram test diffs.
Testing
The new test samples cover the complete matrix of cycle scenarios for the newly-covered variants:
invalid_binding_cycle_index_expr.jsonnet—local i = i; local arr = [1]; arr[i]invalid_binding_cycle_indexed_local.jsonnet—local a = a[0]invalid_binding_cycle_nested_local.jsonnet—local a = (local b = b; b)valid_binding_local_shadowing.jsonnet—local a = (local a = 1; a)invalid_function_default_cycle.jsonnet—local f(x = a) = 1whereais cyclicinvalid_closure_default_cycle.jsonnet— same for closuresvalid_unused_recursive_function_body.jsonnet—local f() = f(); 1valid_unused_recursive_closure_body.jsonnet—local f = function() f(); 1invalid_function_call_callee_cycle.jsonnet—(local f = f; f)(1)invalid_function_call_positional_arg_cycle.jsonnet—f((local a = a; a))invalid_function_call_named_arg_cycle.jsonnet—f(x=(local a = a; a))invalid_object_var_access_self_cycle.jsonnet—local obj = obj; obj.ainvalid_object_var_field_cycle.jsonnet—local obj = { a: obj.a }; obj.ainvalid_object_var_indirect_field_cycle.jsonnet—local obj = { a: obj.b, b: obj.a }; obj.avalid_object_var_non_cyclic_field_access.jsonnet—local obj = { a: obj.b, b: 1 }; obj.a
The cram test diffs also show the removed warning lines — the error highlight fix eliminated trailing blank lines in error output. Example:
The untouched_invalid_field sample no longer emits warnings for cyclic fields that aren’t actually evaluated — the on-demand approach only fires when the field is accessed.
A note on the error-highlight fix
I snuck in a small change to lib/error.ml while I was at it. The error highlighter was drawing caret lines (^^^) for error lines even when the highlight function returned an empty string. Now it checks String.contains highlight '^' before adding the caret line to the output. This is why the cram test diffs all show trailing blank lines being removed — those were empty highlight lines. Pure cosmetic, but the cram test diffs are easier to read.
Conclusion
The type checker’s cycle detection went from 13 proactive AST-walking functions to zero. Translation itself is now the cycle detector — with_translating checks, registers, and cleans up. The on-demand approach is simpler: fewer lines of code, no separate traversal to keep in sync, and more correct lazy semantics.
There’s more to clean up in the type checker. The on-demand pattern exposed that TruntimeObject needed its own environment, which was long overdue. And the translation of function definitions still has some rough edges I’m not thrilled about. Future me gets to sort those out.
The entire diff can be seen here.