war on Any: recursive function calls see `Any` return type during body analysis

[timfennis]

Problem

When a named function is declared, the analyzer pre-registers a placeholder binding before analysing the body so that recursive calls can resolve the name (ndc_analyser/src/analyser.rs:295–316). The placeholder's return type is Any (or the annotated return type if one exists):

let placeholder = StaticType::Function {
    parameters: type_signature.types(),
    return_type: Box::new(
        return_type_slot.clone().unwrap_or(StaticType::Any),  // line 306
    ),
};

After body analysis, the slot is updated with the real inferred return type (update_binding_type at line 364). However, during body analysis, any expression that calls the function recursively has already been analyzed with the placeholder type — so the expr_types side table records Any for the return type of the recursive call.

Example

fn fib(n: Int) {
    if n <= 1 { n }
    else { fib(n-1) + fib(n-2) }
    // fib(n-1) is analyzed while placeholder has Any return → call type recorded as Any
}

The final function type IS updated correctly (callers outside the function body see the right type). But within the body, any variable bound to the result of a recursive call carries Any.

Impact

Severity: Low–Medium. Only affects recursive functions. Callers at the top level get the correct type. The problem manifests as inaccurate LSP hover types inside recursive bodies and, in edge cases, incorrect cascading Any when the recursive result is used in further computations.

Approaches

Simple fix (low effort)

For functions with an explicit return type annotation, the placeholder already uses the annotation instead of Any. Encouraging annotations eliminates the issue for all annotated functions at zero implementation cost.

Single-pass fixpoint (medium effort)

After updating the pre-registered slot with the real return type, run a second analysis pass over the function body. Since the return type can only grow through LUB, this converges in at most two passes for direct recursion.

Full fixpoint iteration (high effort)

For mutual recursion (fn a calls fn b calls fn a), two passes are insufficient. A full solution requires iterating until the type assignment is stable (classic Kildall-style dataflow). This is significant but well-understood.

Notes

• The placeholder already respects explicit return type annotations — if fn fib(n: Int) -> Int is written, the recursive call correctly records Int. So annotating recursive functions is the zero-cost workaround.
• The single-pass fixpoint approach covers the vast majority of real recursive code (self-recursion) at low cost.