viviONグループでは、DLsiteやcomipoなど、二次元コンテンツを世の中に届けるためのサービスを運営しています。
ともに働く仲間を募集していますので、興味のある方はこちらまで。

はじめに

kyのソースコードを読んでいるときに、以下の非同期再帰関数でスタックオーバーフローが発生しない理由を言語化できなかったので調べてみました。

// https://github.com/sindresorhus/ky/blob/v1.4.0/source/core/Ky.ts#L330
new globalThis.ReadableStream({
  async start(controller) {
    const reader = response.body!.getReader();
    if (onDownloadProgress) {
      onDownloadProgress({percent: 0, transferredBytes: 0, totalBytes}, new Uint8Array());
    }
    async function read() {
      const {done, value} = await reader.read();
      if (done) {
        controller.close();
        return;
      }
      if (onDownloadProgress) {
        transferredBytes += value.byteLength;
        const percent = totalBytes === 0 ? 0 : transferredBytes / totalBytes;
        onDownloadProgress({percent, transferredBytes, totalBytes}, value);
      }
      controller.enqueue(value);
      await read();
    }
    await read();
  }
})

read関数は再帰関数のため、サイズの大きいレスポンスを読み込もうとした際に、関数呼び出しが多くなりすぎてスタックオーバーフローが発生しそうですが、実際にはそうなりません。

この記事ではイベントループや各タスクキューの仕組みを知ることで、なぜread関数でスタックオーバーフローが発生しないかを解説します。
なお、今回紹介するのはブラウザ環境のイベントループのため、node環境のイベントループとは異なります。

コールスタックとイベントループ

イベントループの流れを理解するために知っておく必要のある仕組みを簡単に紹介します。
具体的な説明は長くなるため、参考のリンク先を参照してください。

タスク
- プログラムの初期実行、イベントコールバックなどの標準的なメカニズムによってスケジュールされるJavaScriptのコード
- 次の要素を持つ構造体として表現される
  - ステップ
    - タスクによって行われる作業を指定する一連の手順
  - ソース
    - 関連するタスクをグループ化し、シリアライズするために使用されるタスクソースの一つ
  - ドキュメント
    - タスクに関連付けられたドキュメント。またはウィンドウのイベントループにないタスクの場合はnull
  - スクリプト評価の環境設定オブジェクトのSet
    - タスクの実行中にスクリプト評価を追跡するために使用される環境設定オブジェクトのSet
タスクキュー
- タスクを追加する順序付きSet（データ構造はSetでありQueueではない）
- setTimeout、イベントハンドラ、I/O操作などのコールバックが追加される
- イベントループには1つ以上のタスクキューが存在する
  - setTimeout、イベントハンドラなどによって発生するタスクはタスクソースと呼ばれ、個別のキューに送られる
マイクロタスクキュー
- Promise（then, catch, finally）、MutationObserver、queueMicrotaskなどのコールバックが追加される
コールスタック
- プログラムの実行中に関数の呼び出し履歴を追跡するためのデータ構造（LIFO）
- 関数が呼び出されるたびにその関数の実行コンテキストをスタックにプッシュし、関数の実行が完了するとそのコンテキストをスタックからポップすることで動作する

イベントループの流れ

ブラウザ環境のイベントループの流れは以下のステップを繰り返します。

スクリプトを評価し、コールスタックが空になるまで、関数呼び出しを処理します
- コールスタックには同期的な関数呼び出しが積まれます。関数が実行されると、その実行コンテキストがスタックから取り除かれます
タスクキューから最も古いタスクを1つ取り出し処理します
コールスタックが空になると、マイクロタスクキューのタスクをすべて処理します
レンダリング
- レンダリング回数はディスプレイのリフレッシュレートに依存するため、各ループで必ずレンダリングが実行されるわけではありません
マイクロタスクキューが空になると、2に戻る

非同期再帰関数でasync/awaitを使用した時のイベントループの流れ

次の関数を実行した際のイベントループの流れを考えます。
※説明に不要な関数実行のステップは省略します

async function asyncConsume(arr: number[]) {
  if(arr.length > 0) {
    console.log(arr.pop());
    await asyncConsume(arr);
  } else {
    console.log('done');
  }
}
asyncConsume(Array(10000))

asyncConsumeがコールスタックに追加される
await asyncConsume(arr)が呼び出され、asyncConsumeがコールスタックに追加される

2の時点でawaitがPromiseの解決を待たずに次の呼び出しが行われるため、コールスタックが積み重なります。
そのため、再帰による関数呼び出しが多い場合、スタックオーバーフローが発生します。
コールスタックが積み重なる原因は通常の再帰関数と同じです。

JavaScript Visualizer 9000でasync/awaitが使用できないため通常の再帰関数になりますが、以下のリンクよりイベントループの流れを確認できます。

スタックオーバーフローが発生する再帰関数のイベントループ

スタックオーバーフローを防ぐには？

再帰関数でスタックオーバーフローを発生させないためにはトランポリン化がありますが、非同期再帰関数では別の方法を利用することが可能です。

再帰呼び出しがスタックオーバーフローを引き起こさないようにするためには、再帰関数の呼び出しごとに一度コールスタックをクリアする必要があります。

以下にasyncConsumeを修正したコードを示します。

+ function delay(ms: number) {
+   return new Promise((resolve) => setTimeout(resolve, ms));
+ }

async function asyncConsume(arr: number[]) {
  if(arr.length > 0) {
    console.log(arr.pop());
+   await delay(0);
    await asyncConsume(arr);
  } else {
    console.log('done');
  }
}

asyncConsume(Array(10000))

修正したコードのイベントループの流れを考えます。

asyncConsumeがコールスタックに追加される
await delay(0)が実行され、Promiseが解決されるまで現在のasyncConsumeは一時停止される
awaitの評価が完了した後に、後続の処理がマイクロタスクキューに追加され、コールスタックがクリアされる
後続処理でasyncConsumeが再度コールスタックに追加される

awaitによって分割された後続処理はマイクロタスクキューに追加されるため、コールスタックの関数実行 -> マイクロタスクの実行 -> コールスタックの関数実行を繰り返します。
これによりスタックオーバーフローが発生しなくなります。

async/awaitを用いてませんが、シミュレーションしたイベントループの流れはこちらになります。
スタックオーバーフローが発生しない再帰関数のイベントループ

awaitで待ち受けるPromiseの処理がタスクキュー、マイクロタスクキューのどちらに追加されているかで動作が変わります。

リンク先のシミュレーションではマイクロタスクを用いていますが、マイクロタスク内でマイクロタスクを追加すると、イベントループで永遠とマイクロタスクを処理してしまいます。
コールスタックがクリアされる点は変わりませんが、1回のイベントループを抜ける、抜けないの違いがある点に注意してください。

例えば下記のコードの実行結果は、asyncConsume内の処理でawait delay(0);を用いた場合と await Promise.resolve(undefined)を用いた場合では結果が異なります。

setTimeout(() => {
  console.log("first task");
});
asyncConsume([1, 2, 3]);
setTimeout(() => {
  console.log("second task");
});

await delay(0)の場合

3
first task
2
second task
1
done

await Promise.resolve(undefined)の場合

3
2
1
done
first task
second task

kyの実装でスタックオーバーフローが発生しない理由

冒頭で引用したkyの実装を見てみましょう。

async function read() {
    const {done, value} = await reader.read();
    if (done) {
    controller.close();
    return;
    }
    if (onDownloadProgress) {
    transferredBytes += value.byteLength;
    const percent = totalBytes === 0 ? 0 : transferredBytes / totalBytes;
    onDownloadProgress({percent, transferredBytes, totalBytes}, value);
    }
    controller.enqueue(value);
    await read();
}
await read();

await reader.read();のPromiseが解決されるまで実行が一時停止し、Promise解決後の処理がマイクロタスクキューに追加されます。
これにより、コールスタックの関数実行 -> マイクロタスクの実行 -> コールスタックの関数実行を繰り返すようになり、スタックオーバーフローが発生することなくレスポンスのbodyを読み取ることができます。
また、reader.read()の処理はタスクキューに追加されるため、1回のイベントループ内で永遠にマイクロタスクを処理してしまう問題も発生しません。

まとめ

今回は非同期再起処理でスタックオーバーフローが発生しない条件を紹介しました。
イベントループの仕組みを理解する必要があるため普段はwhileループを使用していますが、もし似たような実装を見かけたら、この記事の内容を思い出していただければ幸いです。

参考

一緒に二次元業界を盛り上げていきませんか？

株式会社viviONでは、フロントエンドエンジニアを募集しています。

また、フロントエンドエンジニアに限らず、バックエンド・SRE・スマホアプリなど様々なエンジニア職を募集していますので、ぜひ採用情報をご覧ください。