Stack Overflow とは？call stack が尽きるとき

stack overflow は、プログラムが call stack の固定サイズを超えたときに得るエラーで、ほぼ必ずネストした関数呼び出しが積み上がりすぎることが原因です。

call stack には厳格なサイズ上限があり、すべての関数呼び出しがその一部を使います。stack overflow はその上限を越えたことを意味します。プログラムが空きより 1 つ多い frame を push しようとしたのです。圧倒的に一般的な原因は適切な基底ケースのない再帰で、関数が永遠に自分自身を呼び続けます。

なぜ stack はオーバーフローするのか

各関数呼び出しは frame を push し、return だけがそれを pop します。呼び出しがネストし続けると（特に制御されない再帰）、frame は stack 上限を超えるまで蓄積します。その時点で runtime は stack overflow を発生させ、通常はプログラムを crash させます。

一般的な原因

基底ケースが欠けている、または到達不能な再帰。
決して終了しない関数間の相互再帰。
非常に大きな入力に対する、極めて深いが有限の再帰。
callback を介した関数呼び出しの偶発的な無限ループ。

修正方法

すべての再帰経路に、実際に到達される基底ケースがあることを確認してください。非常に深い再帰には、アルゴリズムを反復的に書き直すか、stack よりはるかに余裕のある heap 上の明示的なデータ構造を使ってください。

stack overflow と out of memory

stack overflow は小さく固定された call stack を使い果たし、通常は再帰が原因です。out-of-memory エラーははるかに大きな heap を使い果たし、通常はデータの確保しすぎが原因です。似て見えます（プログラムが死ぬ）が、原因と修正は異なります。

簡単な例

factorial(n) => n * factorial(n - 1) として書かれた階乗関数に if (n <= 1) の基底ケースがないと、永遠に再帰して結果を返さず、stack をオーバーフローさせます。

CI における stack overflow

テストでの stack overflow は決定的なバグです。毎回同じように失敗するため、retry は無意味です。Latchkey は決定的な crash を一時的なインフラの失敗とは別に扱い、後者だけを自動 retry するため、本物の再帰バグが覆い隠されません。

重要なポイント

stack overflow は call stack が固定サイズを超えたことを意味し、通常は暴走した再帰が原因です。
heap ではなく stack を使い果たす out-of-memory とは異なります。
決定的なバグなので retry は役に立ちません。再帰を修正してください。