Bug 163663 – RangeError with deep self recursion (Proper tail call)

• Status: RESOLVED
• Resolution: WORKSFORME
• Component: JavaScriptCore

[Gabe Johnson]

A RangeError is thrown during a deep self recursion. As stack frames are supposed to be reused if a function is called in tail position, this is unexpected.

```
function decToZero(n) {
  return n>0 ? decToZero(n-1) : n;
}

decToZero(42280) // yields "RangeError: Maximum call stack size exceeded."
```

The depth of recursion necessary to blow the stack is not consistent but I've always observed it when n >= 100000.

Hardware:
MacBook Pro (Retina, 15-inch, Mid 2015)
2.5 GHz Intel Core i7
16 GB 1600 MHz DDR3

Webkit: Version 10.0 (11602.1.50.0.10, r207529)

[Gabe Johnson]

Note: I tested this in the developer console.

[Filip Pizlo]

(In reply to comment #0)
> A RangeError is thrown during a deep self recursion. As stack frames are
> supposed to be reused if a function is called in tail position, this is
> unexpected.
> 
> ```
> function decToZero(n) {
>   return n>0 ? decToZero(n-1) : n;
> }
> 
> decToZero(42280) // yields "RangeError: Maximum call stack size exceeded."
> ```
> 
> The depth of recursion necessary to blow the stack is not consistent but
> I've always observed it when n >= 100000.
> 
> Hardware:
> MacBook Pro (Retina, 15-inch, Mid 2015)
> 2.5 GHz Intel Core i7
> 16 GB 1600 MHz DDR3
> 
> Webkit: Version 10.0 (11602.1.50.0.10, r207529)

Does it work if you write your code this way:

function decToZero(n) {
  if (n>0)
    return decToZero(n-1);
  return n;
}

The bug appears to be that we don't handle ternaries correctly for our evaluation of whether a call is in tail position. It took me a while, but by my reading of http://www.ecma-international.org/ecma-262/6.0/ECMA-262.pdf, on page 265 it appears to say that if the cases of the ternary are tail candidates.

[Geoffrey Garen]

> Does it work if you write your code this way:
> 
> function decToZero(n) {
>   if (n>0)
>     return decToZero(n-1);
>   return n;
> }

decToZero#DYBUcA:[0x104588310->0x1045a37c0, NoneFunctionCall, 43]: 43 m_instructions; 344 bytes; 2 parameter(s); 16 callee register(s); 6 variable(s); scope at loc3
[   0] enter             
[   1] get_scope         loc3
[   3] mov               loc4, loc3
[   6] jngreater         arg1, Int32: 0(const0), 35(->41)
[  10] resolve_scope     loc10, loc3, decToZero(@id0), <GlobalVar>, 1, 0x1045dc0a0
[  17] get_from_scope    loc6, loc10, decToZero(@id0), 2049<ThrowIfNotFound|GlobalVar|NotInitialization>, 60435336    predicting None
[  25] sub               loc9, arg1, Int32: 1(const1)    results: Result:<Int32> LHS ObservedType:<> RHS ObservedType:<> LHS ResultType:<0x3e> RHS ResultType:<0x3>
[  30] call              loc6, loc6, 2, 16 (this at loc10) status(Could Take Slow Path)    Original; predicting None
[  39] ret               loc6
[  41] ret               arg1

Identifiers:
  id0 = decToZero

Constants:
   k0 = Int32: 0: in source as integer
   k1 = Int32: 1: in source as integer

--> RangeError: Maximum call stack size exceeded.

[Filip Pizlo]

(In reply to comment #3)
> > Does it work if you write your code this way:
> > 
> > function decToZero(n) {
> >   if (n>0)
> >     return decToZero(n-1);
> >   return n;
> > }
> 
> decToZero#DYBUcA:[0x104588310->0x1045a37c0, NoneFunctionCall, 43]: 43
> m_instructions; 344 bytes; 2 parameter(s); 16 callee register(s); 6
> variable(s); scope at loc3
> [   0] enter             
> [   1] get_scope         loc3
> [   3] mov               loc4, loc3
> [   6] jngreater         arg1, Int32: 0(const0), 35(->41)
> [  10] resolve_scope     loc10, loc3, decToZero(@id0), <GlobalVar>, 1,
> 0x1045dc0a0
> [  17] get_from_scope    loc6, loc10, decToZero(@id0),
> 2049<ThrowIfNotFound|GlobalVar|NotInitialization>, 60435336    predicting
> None
> [  25] sub               loc9, arg1, Int32: 1(const1)    results:
> Result:<Int32> LHS ObservedType:<> RHS ObservedType:<> LHS ResultType:<0x3e>
> RHS ResultType:<0x3>
> [  30] call              loc6, loc6, 2, 16 (this at loc10) status(Could Take
> Slow Path)    Original; predicting None
> [  39] ret               loc6
> [  41] ret               arg1
> 
> Identifiers:
>   id0 = decToZero
> 
> Constants:
>    k0 = Int32: 0: in source as integer
>    k1 = Int32: 1: in source as integer
> 
> --> RangeError: Maximum call stack size exceeded.

I bet you forgot "use strict" at the top of the file, or inside decToZero.

[Filip Pizlo]

Ha!  And the supplied test case doesn't get RangeError if I just put "use strict" in it.

Gabe: please check that your code is in strict mode, or else according to the spec, you're not supposed to get tail calls.

[Geoffrey Garen]

lulz

[Gabe Johnson]

That's the problem. I'm so used to using babel which inserts "use strict". I haven't had to do it in over a year. Sorry to waste your time.

One a side note, tail calls and ternaries work fine.