Tsonnet #47 - The devil in the details #3

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 replaced the proactive cycle-checking AST walk with on-demand detection during translation: On-demand caught simple cycles during translation, but lazy types in arrays, function defaults, and object fields could still hide cycles until interpretation. I needed to manifest every type fully during type checking. Hardening: recursive function calls The on-demand pattern from post #46 caught variable cycles via TranslatingVar and field cycles via TranslatingObjField . But recursive function calls were a blind spot - when a function body references another function that hasn't finished translating, the cycle goes undetected. I added a TranslatingFunction key: diff --git a/lib/type.ml b/lib/type.ml index 551454f..341134c 100644 --- a/lib/type.ml +++ b/lib/type.ml @@ -5,6 +5,7 @@ open Syntax_sugar type translation_key = | TranslatingVar of string | TranslatingObjField of Env.env_id * string + | TranslatingFunction of string module TranslationKeys = Set.Make(struct type t = translation_key @@ -16,6 +17,7 @@ let translating_bindings = ref TranslationKeys.empty let string_of_translation_key = function | TranslatingVar varname -> varname | TranslatingObjField (obj_id, field) -> Env.uniq_field_ident obj_id field + | TranslatingFunction name -> name And wrapped the function body translation in with_translating : @@ -563,7 +589,9 @@ and translate_named_function_call venv (pos, name, args) = venv' resolved_params in - let* (, body_type) = translate body_venv body_expr in + let* (, body_type) = + with_translating (TranslatingFunction name) pos (fun () -> translate body_venv body_expr) + in This catches local f() = f() - the body translation fires TranslatingFunction f before starting, and if f() in the body triggers the same key, with_translating raises the cycle error. The same logic applies to closure calls - local f = function() f() now triggers TranslatingFunction f around the closure body. While I was at it, I fixed collect_free_idents to exclude bound names from function and closure bodies. A function's own name and its parameter names shouldn't count as free variables in the body: @@ -149,10 +154,31 @@ let rec collect_free_idents = function | Positional e -> collect_free_idents e | Named (, e) -> collect_free_idents e ) call.args - | Closure (, closure) -> collect_free_idents closure.body + | Closure (, closure) -> + let param_names = List.map fst closure.params in + collect_param_defaults closure.params + @ exclude_bound_idents param_names (collect_free_idents closure.body) + | FunctionDef (, def) -> + let bound_names = def.name :: List.map fst def.params in + collect_param_defaults def.params + @ exclude_bound_idents bound_names (collect_free_idents def.body) The new samples cover the full matrix of recursive call scenarios: - invalid_recursive_function_call.jsonnet -local f() = f(); f() - invalid_recursive_closure_call.jsonnet -local f = function() f(); f() - invalid_mutual_recursive_function_call.jsonnet -local f() = g(); local g() = f(); f() - invalid_mutual_recursive_closure_call.jsonnet -local f = function() g(); local g = function() f(); f() - valid_closure_param_shadowing_unused_outer.jsonnet - local shadowing doesn't trigger false positives - valid_function_body_uses_outer_local.jsonnet - function body referencing an outer local is fine Deep translation: manifesting every type The on-demand approach - wrapping each lazy translation in with_translating - works well for bindings hit during translation. But array elements, object fields, and function default parameters are stored as Lazy expr nodes in the type. Translation never visits them until they're actually accessed. If two lazy nodes reference each other through an intermediary, the cycle passes the type checker silently and blows up at interpretation time. Consider: { a: self } With the on-demand pattern alone, the object field a is stored as Lazy (ObjectFieldAccess ...) . Translation of the object doesn't resolve self.a - that only happens when the field is accessed. So { a: self } used to type-check successfully and fail at manifestation. I needed a post-processing step that recursively resolves every Lazy , LazyIn , and LazyDefault wrapper in the type tree, catching cycles along the way. The core: deep_translate_type and deep_translate_type pos venv = function | Lazy expr -> let* (venv', ty) = translate venv expr in deep_translate_type (expr_pos pos expr) venv' ty | LazyIn (lazy_venv, expr) -> let* (venv', ty) = translate lazy_venv expr in deep_translate_type (expr_pos pos expr) venv' ty | LazyDefault (name, outer_venv, params, expr) -> with_translating (TranslatingDefaultParam name) pos (fun () -> with_shadowed_translating_vars [name] (fun () -> let default_env = add_default_params_to_env outer_venv name params in let* (venv', ty) = translate default_env expr in deep_translate_type (expr_pos pos expr) venv' ty ) ) | Tarray tys -> let* tys' = List.fold_left (fun acc ty -> let* tys = acc in let* ty' = deep_translate_type pos venv ty in ok (tys @ [ty']) ) (ok []) tys in ok (Tarray tys') | TruntimeObject (obj_id, obj_venv, fields) -> let* fields' = List.fold_left (fun acc field -> let* fields = acc in match field with | TobjectField (name, ty) -> let* ty' = with_translating (TranslatingObjField (obj_id, name)) pos (fun () -> deep_translate_type pos obj_venv ty ) in ok (fields @ [TobjectField (name, ty')]) | TobjectExpr ty -> let* ty' = deep_translate_type pos obj_venv ty in ok (fields @ [TobjectExpr ty']) ) (ok []) fields in ok (TruntimeObject (obj_id, obj_venv, fields')) | TobjectPtr (obj_id, _, _) -> Error.error_at pos (Error.Msg.type_cyclic_reference (Env.uniq_field_ident obj_id "self")) | ty -> ok ty The three lazy wrappers each need different handling: - Lazy - translate in the current environment (the default for most lazy bindings) - LazyIn - translate in the environment captured at array construction time (array elements should resolve against the scope where the array was defined, not where it's accessed) - LazyDefault - translate in an environment where sibling parameters are also lazy and the current parameter is shadowed out (sof(x = y, y = 1) resolvesy in the default forx ) For Tarray , I went from a single element type to an element-level list. This lets deep_translate_type resolve each element independently: - | Tarray of tsonnet_type + | Tarray of tsonnet_type list And translate_array now wraps each element in LazyIn with the current environment: - ok (venv, Tarray (List.map (fun elem -> Lazy elem) elems)) + ok (venv, Tarray (List.map (fun elem -> LazyIn (venv, elem)) elems)) Object fields in deep translation translate_object needed two changes. First, it now builds a field list alongside the object environment, so deep_translate_type knows which fields to visit: - let* obj_venv = List.fold_left + let* (obj_venv, fields) = List.fold_left (fun result entry -> - let* obj_venv = result in + let* (obj_venv, fields) = result in match entry with | ObjectExpr expr -> - let* (obj_venv', _) = translate obj_venv expr in ok obj_venv' + let* (obj_venv', _) = translate obj_venv expr in ok (obj_venv', fields) | ObjectField (attr, expr) -> - ok (Env.add_obj_field attr (Lazy expr) obj_id obj_venv) + ok ( + Env.add_obj_field attr (Lazy expr) obj_id obj_venv, + fields @ [TobjectField (attr, Lazy expr)] + ) ... Second, TobjectPtr now carries an optional captured environment for resolving self and $ during deep translation. When deep_translate_type encounters a TobjectPtr , it raises a cycle error - manifesting self or $ in the root type means the top-level expression references the object itself, which can't be manifested. - | TobjectPtr of Env.env_id * t_object_scope + | TobjectPtr of Env.env_id * t_object_scope * tsonnet_type Env.Map.t option The interpreter gives up runtime detection Since every lazy type is now resolved during type checking, the interpreter no longer needs its own cycle detection. The entire evaluating_bindings infrastructure - about 150 lines across interpret_ident , interpret_object_field_access , interpret_runtime_object_fields , and interpret_seq - came out: -let evaluating_bindings = ref ObjectFields.empty - -let with_fresh_evaluating_bindings fn = - let saved_evaluating_bindings = !evaluating_bindings in - evaluating_bindings := ObjectFields.empty; - let result = fn () in - evaluating_bindings := saved_evaluating_bindings; - result I removed the ObjectFields.mem checks from every interpreter path. The type checker now guarantees that by the time the interpreter sees a type, all cycles have been detected. The interpreter can focus on evaluation. The entry point The top-level check function now runs deep_translate_type after translation: - let* _ = translate Env.empty expr in + let* (venv, ty) = translate Env.empty expr in + let* _ = deep_translate_type dummy_pos venv ty in This single extra line is the architectural change. Translation produces the type; deep_translate_type walks the result and blows up on any leftover lazy reference that would cycle. Cleanup: translate_ident The old translate_ident had a manual TranslationKeys.mem check before Env.find_var . Since with_translating inside the Lazy branch already handles that check, the early guard was redundant: -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 - | LazyDefault _ as ty -> ... - | Lazy expr -> with_translating key pos (fun () -> - let* (venv', ty) = translate venv expr in - let* ty' = deep_translate_type pos venv' ty in - ok (venv', ty') - ) - | _ -> ok (venv, ty) - ) - ~err:(Error.error_at pos) +and translate_ident venv pos varname = + Env.find_var varname venv + ~succ:(fun venv ty -> + match ty