ReviewOS

zig-utils/zig-js

Interpreter: complete proper tail calls across tree-walked expressions

#1099
Closed glennmichael123 opened this 9 days ago ·
9 days ago

Parent: #491 Related: #465

Problem

The forced tree walker and required bytecode disagree on 13 positive test262 expression cases, all in the proper-tail-call family:

  • logical && / || and nullish ?? right operands
  • conditional branches
  • the final comma operand
  • ordinary identifier/member calls, including an identifier resolved through with
  • tagged-template calls

Current-main evidence (136178ae):

# test/language/expressions: 13 diverge, 11025 agree

Every mismatch is fail_runtime->pass: the tree walker reaches its native stack guard while required bytecode completes.

The tree walker already owns a frame-reusing tail-call trampoline, but tree_tail_allowed is enabled only when a strict function's source contains the bytes eval, and prepareTreeTailCall recognizes only a non-direct call through an identifier literally named eval. Ordinary tail calls and the other HasCallInTailPosition expression forms therefore never enter it.

Executed oracle

A minimized strict conditional-tail recursion at depth 100 returns 41 exactly once in Node, JavaScriptCore, forced tree, and required VM. At depth 100,000:

  • JavaScriptCore: 41:1
  • required VM: 41:1
  • forced tree: RangeError, terminal call count 0
  • Node: RangeError because Node does not implement the optional proper-tail-call feature; it is useful here only for the bounded semantic/order control

Scope

  • Extend the existing tree-walker trampoline across the exact strict-mode tail-position expression grammar used by the compiler: call, final sequence operand, logical right operand, conditional branches, nullish right operand, and tagged templates.
  • Preserve call-reference semantics: computed/member/super/with receivers, evaluation order, direct-eval handling, spread arguments, optional short circuit, and call-site diagnostics.
  • Do not reuse a frame while a try/finally or constructor obligation must remain live.
  • Add deterministic forced-tree versus required-bytecode tests, including receiver/order and GC-rooting coverage.

Acceptance

  • The 13 current expression divergences become 0 without reducing the denominator.
  • Minimized deep strict recursion completes with bounded native stack in forced-tree and required-bytecode modes.
  • Sloppy recursion still grows the logical/native stack and throws rather than being silently optimized.
  • Receiver, argument, tagged-template, with, abrupt completion, and moving-GC observations agree across tiers.
  • Focused normal and unsuppressed TSan tests pass; affected test262 subtrees have zero failures.

No source-name recognition, test-specific depth exception, or forced-tree fallback to bytecode.

9 days ago

Completed in 8c672e9 (rebased onto current origin/main and pushed directly to main).

The 13 original required-VM expression divergences are eliminated by extending the real tree-walker tail-expression trampoline across calls, sequence/logical/nullish/conditional/optional/tagged-template forms, preserving receivers, evaluation order, direct-eval handling, method fallback, and try/finally boundaries. Nested strict concise arrows now use canonical compiler tail lowering. Pending tree tail-call inputs are also traced and relocated across the GC handoff.

Final evidence from the exact rebased tree:

  • full test/language/expressions required-VM witness: 0 diverge, 11038 agree
  • affected statement TCO: 0 fail, 16 pass; 0 diverge, 16 agree
  • affected expression TCO: 0 fail, 16 pass
  • Proxy revocable: 0 fail, 18 pass; 0 diverge, 18 agree
  • focused Debug gate: 4/4 passed
  • focused unsuppressed TSan gate: 4/4 passed, no race report
  • focused frontend regression: 1 case passed
  • compiler lowering regression: 2/2 linked tests passed

This meets the acceptance checklist without source-specific shortcuts or a bytecode fallback. Closing the tranche issue.

9 days ago

Closed by 8c672e9 after the full expression witness and focused normal/TSan/GC gates passed.

Sign in to comment on this issue.