Why does nesting a bunch of blocks causes a stack overflow in JavaScript

Question

The code {} is perfectly legal in JavaScript as it represents a Block.

However, I noticed that nesting a lot of blocks ({{...}}) inside another raises in Chrome*:

Uncaught RangeError: Maximum call stack size exceeded

Why is a stack overflow happening here?

---

Here is a codepen illustrating the issue (jsfiddle crashes).

When asking in the JSRoom Zirak found out that the magic number is 3913 blocks on chrome and 2555 on Firefox.

What is being pushed to the stack? Why?

---

(*) I've checked and it also happens in IE and Firefox

Update: I've checked and unreliably IE is able to avoid the stack overflow exception. It has thrown it two times but not the third. If any of the readers have IE and are willing to test older versions of it too (like IE8 and 9) and let me know what happens I'd really appreciate that.

Answer 1

First of all, ghord is completely correct. It is caused by the parser's recursive nature, so give him upvote love. But proof needs to be had, and OP wanted me to post this as a separate answer.

Firefox

So, where to find out about how it was done? Ask some guys who're in the engine making. So I went over to the #jsapi channel on irc://irc.mozilla.org and asked them:

< bhackett> zirak: well, with a recursive descent parser all the productions will roughly correspond to a frame on the C stack

< bhackett> zirak: the parser is at js/src/frontent/Parser.cpp

< Waldo> zirak: Parser<ParseHandler>::statement(bool canHaveDirectives) and Parser<ParseHandler>::statements() pretty much

< bhackett> zirak: in this case, the recursion will be Parser::blockStatement ->Parser::statements -> Parser::statement -> Parser::blockStatement

Which is pretty much the answer. Going to the mozilla-central repository and digging in, we have our suspects:

• Parser<ParseHandler>::blockStatement
• Parser<ParseHandler>::statements

So, what we have is this:

• statements which calls blockStatement, which parses the block, to find another block, calling
  • statements which calls blockStatement, which parses the block, to find another block, calling
    • statements which calls blockStatement, which parses the block, to find another block, calling
      • ...

Until the stack collapses, I'm guessing here.

So we have the source for Firefox.

Chrome/Chromium/anything else based on v8

Learning my lesson from Firefox, I went to the v8 project and looked for a file named parser. Sure enough, it was there!

The next thing was looking for when a block is parsed, so I naively searched for statements, arriving on the promising ParseStatement.

And it's our lucky day, a giant switch! And the first case is what we care about, a call to ParseBlock, another promising name!

Indeed, inside ParseBlock, we find a call to ParseStatement. So, to be clear, we have two functions:

• Parser::ParseBlock
• Parser::Parser::ParseStatement

And they're calling each other like we saw in Firefox:

• ParseStatement which calls ParseBlock, which parses the block, to find another block, calling
  • ParseStatement which calls ParseBlock, which parses the block, to find another block, calling
    • ParseStatement which calls ParseBlock, which parses the block, to find another block, calling
      • ...

Until kaboom goes the stack.

Safari

(Sorry for calling it closed-source in the last edit!) Safari's js engine is JavaScriptCore, which resides in the WebKit project. Finding the functions was pretty much the same as finding them for Chrome, so let's skip to the interesting part:

• Parser<LexerType>::parseSourceElements
• Parser<LexerType>::parseStatement
• Parser<LexerType>::parseBlockStatement

We have an extra function in the middle, but the principle is the same:

• parseSourceElements which calls parseStatement which calls parseBlockStatement, which parses the block, to find another block, calling
  • parseSourceElements which calls parseStatement which calls parseBlockStatement, which parses the block, to find another block, calling
    • parseSourceElements which calls parseStatement which calls parseBlockStatement, which parses the block, to find another block, calling
      • ...

BOOM

IE (and all other closed-source, like Opera)

...will remain a mystery, unless they feel the sudden urge to open their source or if an enterprising employee shared the internals with us. The two great engines above do it in the same fashion, so we can assume the other browsers do it similarly.

If a browser doesn't collapse, that's an interesting question, but one that this answer can't hope to cough answer.

Answer 2

Default implementation of Recursive descend parser while simple and elegant, parses every language grammar rule with one method. These methods call other methods recursively, so when you have too much nested rules, it exceeds the stack size. Chrome and Firefox both use such implementation of interpreter.

You will notice that a lot of ' + ', while having nothing to do with scope, will cause the same exception:

+ + + + + + + + + ... // same error