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:
| Unit | Null _ | Number _ | String _ | Bool _ | EvaluatedObject _
| RuntimeObject _ | ObjectPtr _ | FunctionDef _ | FunctionCall _ | Closure _
(* TODO *)
| Local _ | IndexedExpr _ -> ok ()
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:
and check_function_def_for_cycles venv def seen =
check_param_defaults_for_cycles venv def.params seen
and check_closure_for_cycles venv closure seen =
check_param_defaults_for_cycles venv closure.params seen
and check_param_defaults_for_cycles venv params seen =
List.fold_left
(fun result (_, default_expr_opt) ->
let* () = result in
match default_expr_opt with
| Some default_expr -> check_expr_for_cycles venv default_expr seen
| None -> ok ()
)
(ok ())
params
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:
and check_function_call_for_cycles venv call seen =
let* () = check_expr_for_cycles venv call.callee seen in
List.fold_left
(fun result arg ->
let* () = result in
match arg with
| Positional expr -> check_expr_for_cycles venv expr seen
| Named (_, expr) -> check_expr_for_cycles venv expr seen
)
(ok ())
call.args
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:
and check_indexed_expr_for_cycles venv (pos, varname, index_expr) seen =
let* () = check_expr_for_cycles venv index_expr seen in
match Env.find_opt varname venv with
| Some (Lazy (Array (_, exprs))) ->
(match index_expr with
| Number (_, Int index) when index >= 0 && index < List.length exprs ->
check_expr_for_cycles venv (List.nth exprs index) (varname :: seen)
| _ -> ok ()
)
| Some (Lazy (String _)) -> ok ()
| Some (Lazy _) -> check_cyclic_refs venv varname seen pos
| _ -> ok ()
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.
- | TruntimeObject of Env.env_id * t_object_entry list
+ | TruntimeObject of Env.env_id * tsonnet_type Env.Map.t * t_object_entry list
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:
type translation_key =
| TranslatingVar of string
| TranslatingObjField of Env.env_id * string
module TranslationKeys = Set.Make(struct
type t = translation_key
let compare = Stdlib.compare
end)
let translating_bindings = ref TranslationKeys.empty
And a helper that wraps the common check/set/remove pattern:
let with_translating key pos fn =
if TranslationKeys.mem key !translating_bindings then
Error.error_at pos (Error.Msg.type_cyclic_reference (string_of_translation_key key))
else begin
translating_bindings := TranslationKeys.add key !translating_bindings;
let result = fn () in
translating_bindings := TranslationKeys.remove key !translating_bindings;
result
end
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:
and translate_ident venv pos varname =
let key = TranslatingVar varname in
if TranslationKeys.mem key !translating_bindings then
Error.error_at pos (Error.Msg.type_cyclic_reference varname)
else
Env.find_var varname venv
~succ:(fun venv ty ->
match ty with
| Lazy expr -> with_translating key pos (fun () -> translate venv expr)
| _ -> ok (venv, ty)
)
~err:(Error.error_at pos)
translate_indexed_expr — wraps lazy resolution in with_translating:
| Lazy expr ->
with_translating (TranslatingVar varname) pos (fun () -> translate venv expr)
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):
| String (_, field) | Ident (_, field) ->
...
(match rest with
| Number _ :: _ -> lookup_field ()
| _ -> with_translating (TranslatingObjField (obj_id, field)) pos lookup_field
)
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 cyclic -
invalid_closure_default_cycle.jsonnet— same for closures -
valid_unused_recursive_function_body.jsonnet—local f() = f(); 1 -
valid_unused_recursive_closure_body.jsonnet—local f = function() f(); 1 -
invalid_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.a -
invalid_object_var_field_cycle.jsonnet—local obj = { a: obj.a }; obj.a -
invalid_object_var_indirect_field_cycle.jsonnet—local obj = { a: obj.b, b: obj.a }; obj.a -
valid_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:
- WARNING: .../untouched_invalid_field.jsonnet:1:15 Cyclic reference found for 1->c
-
- 1: local result = {
- ^^^^^^^^^^^^^^^^
- 2: a: 1,
- 3: b: self.a,
- 4: c: self.d,
-
- ---
- WARNING: .../untouched_invalid_field.jsonnet:1:15 Cyclic reference found for 1->d
-
- 1: local result = {
- ^^^^^^^^^^^^^^^^
- 2: a: 1,
- 3: b: self.a,
- 4: c: self.d,
-
- ---
1
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.
Thanks for reading Bit Maybe Wise! On-demand translation meets on-demand newsletter delivery — subscribe and the condition for getting the next post is, conveniently, always true.
Photo by Aleksandr Popov on Unsplash
Top comments (0)