Почему вложенность кучи блоков вызывает переполнение стека в JavaScript

Ответ 1

Прежде всего, ghord полностью верен. Это вызвано рекурсивной природой парсера, поэтому дайте ему возвысить любовь. Но нужно иметь доказательства, а ОП хотел, чтобы я опубликовал это как отдельный ответ.

Firefox

Итак, где узнать, как это было сделано? Спросите некоторых парней, которые находятся в двигателе. Поэтому я перешел к каналу #jsapi на irc://irc.mozilla.org и спросил их:

< 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

Это в значительной степени ответ. Перейдя в центральный хранилище mozilla и выкапывая, у нас есть наши подозреваемые:

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

Итак, что у нас есть:

• statements, который вызывает blockStatement, который анализирует блок, чтобы найти другой блок, вызывая
  • statements, который вызывает blockStatement, который анализирует блок, чтобы найти другой блок, вызывая
    • statements, который вызывает blockStatement, который анализирует блок, чтобы найти другой блок, вызывая
      • ...

Пока пакет не упадет, я предполагаю здесь.

Итак, у нас есть источник для Firefox.

Chrome/Chromium/все остальное на основе v8

Изучив мой урок из Firefox, я пошел в проект v8 и искал файл с именем parser. Конечно, он был там!

Следующее, что нужно было искать, когда блок анализируется, поэтому я наивно искал statements, прибыв на перспективный ParseStatement.

И это наш счастливый день, гигантский switch! И первый случай - это то, о чем мы заботимся, призыв к ParseBlock, еще одно многообещающее имя!

Действительно, внутри ParseBlock, мы находим вызов до ParseStatement. Итак, чтобы быть ясным, мы имеем две функции:

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

И они звонят друг другу, как мы видели в Firefox:

• ParseStatement, который вызывает ParseBlock, который анализирует блок, чтобы найти другой блок, вызывающий
  • ParseStatement, который вызывает ParseBlock, который анализирует блок, чтобы найти другой блок, вызывающий
    • ParseStatement, который вызывает ParseBlock, который анализирует блок, чтобы найти другой блок, вызывающий
      • ...

До тех пор, пока kaboom не перейдет в стек.

Safari

(Извините за то, что он вызвал закрытый файл в последнем редакторе!) Safari js engine JavaScriptCore, который находится в проекте WebKit. Поиск функций был почти таким же, как поиск их для Chrome, поэтому позвольте перейти к интересной части:

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

У нас есть дополнительная функция в середине, но принцип тот же:

• parseSourceElements, который вызывает ParseStatement, который вызывает parseBlockStatement, который анализирует блок, чтобы найти другой блок, вызывающий
  • parseSourceElements, который вызывает ParseStatement, который вызывает parseBlockStatement, который анализирует блок, чтобы найти другой блок, вызывающий
    • parseSourceElements, который вызывает ParseStatement, который вызывает parseBlockStatement, который анализирует блок, чтобы найти другой блок, вызывающий
      • ...

БУМ

IE (и все остальные закрытые исходники, такие как Opera)

... останется загадкой, если только они не почувствуют внезапное желание открыть свой источник или если предприимчивый сотрудник поделился с нами внутренностями. Два больших движка выше делают это одинаково, поэтому мы можем предположить, что другие браузеры делают это аналогично.

Если браузер не разрушается, это интересный вопрос, но тот, на который этот ответ не может надеяться ответить кашлем.

Ответ 2

Стандартная реализация Рекурсивный синтаксический анализатор нисходящего потока в то время как простой и элегантный, анализирует каждое правило грамматики языка одним способом. Эти методы рекурсивно вызывают другие методы, поэтому, когда у вас слишком много вложенных правил, оно превышает размер стека. Chrome и Firefox используют такую ​​реализацию интерпретатора.

Вы заметите, что много "+", не имея ничего общего с областью видимости, вызовет одно и то же исключение:

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