sharin

Appearance

バンドラ(依存解決) ​

実装: frontend/bundler/ / 実行: pnpm test(frontend/)

アプリは何百ものモジュールに分かれ、importで依存し合う。ブラウザにそれを個別に読ませるのは非効率だ。バンドラは入口から importを辿って依存グラフを作り、依存が先に来るよう並べ替えて1つにまとめる。import が輪を作っていれば循環依存として検出する。依存グラフの探索・トポロジカル順序・循環検出・使われないexportを落とすtree-shakingを実装する。

この章で作るもの ​

コードをモジュールに分けるのは良い設計だ。1 つの関心事を 1 つのファイルに閉じ込め、必要なものだけを import する。だがこの「良い設計」は、そのままではブラウザに優しくない。何百ものファイルを個別に取りに行くのは遅く、依存の順序(どのファイルを先に読むべきか)も自明ではない。バンドラは、この開発時の理想と実行時の効率の間を埋める。

やることは 3 段階だ。まず、入口(entry)のモジュールから import を辿り、到達できるモジュールをすべて集めて依存グラフを作る。次に、そのグラフを並べ替える。あるモジュールが別のモジュールを import しているなら、import される側が先に定義されていなければならない。これはグラフのトポロジカル順序だ。並べる過程で、import が輪を作っている(A が B を、B が A を import する)循環依存も検出できる。最後に、依存グラフを見れば「どの export が実際に使われているか」が分かるので、どこからも import されない export を削る。これが tree-shaking だ。この章では、この依存解決の中核を実装する。

entry ─import{add}─▶ math (add, sub, mul)
  │                        ▲
  └─import{log}─▶ util ─import{sub}┘

到達: entry, math, util (orphan は含まれない)
順序: math → util → entry (依存が先)
tree-shake: math の mul は誰も使わない → 落とす
バンドラの依存解決。entry から import を辿ってグラフを作り、依存が先に来るよう並べ替え、使われない export を落とす

順に見ていく。

  1. 依存グラフを辿る: entry から import を辿り、到達できるモジュールだけを集める。使われないモジュールは含めない
  2. トポロジカル順序: 依存を先に、使う側を後に並べる。深さ優先探索(DFS)の帰りがけ順がそれになる。循環なら検出
  3. tree-shaking: 実際に import される export だけ残し、使われない export を落とす

① 依存グラフ: 到達できるものだけ集める ​

まず entry から import を辿って、バンドルに含めるべきモジュールを集める。グラフの到達可能性の探索だ:

ts
// モジュールバンドラの中核（依存解決）を最小構成でフルスクラッチする。
//
// ブラウザは何百ものファイルを個別に読むのが苦手だ。バンドラは、入口(entry)の
// モジュールから import を辿って依存グラフを作り、依存が先に来るように並べ替えて
// 1 つにまとめる。ついでに、どこからも使われない export を落として無駄を削る
// (tree-shaking)。import が輪を作っていれば(循環依存)、それも検出する。
//
// 肝は3つ:
//   1. 依存グラフ: entry から import を辿り、到達できるモジュールだけを集める
//   2. トポロジカル順序: 依存を先に、それを使う側を後に並べる（循環なら検出）
//   3. tree-shaking: 実際に import される export だけ残し、使われない export を落とす

// #region graph{ts}

// Import は「from から names を取り込む」を表す（import { names } from "from"）。
export interface Import {
  from: string;
  names: string[];
}

// Module は 1 つのモジュール。何を import し、何を export するか。
export interface Module {
  id: string;
  imports: Import[];
  exports: string[];
}

// Registry は id からモジュールを引く表（ファイル解決の結果に相当）。
export type Registry = Record<string, Module>;

// collectReachable は entry から import を辿って到達できるモジュール ID を集める。
// どこからも import されないモジュールは、ここに入らない＝バンドルに含まれない。
export function collectReachable(entry: string, registry: Registry): Set<string> {
  const reachable = new Set<string>();
  const stack = [entry];
  while (stack.length > 0) {
    const id = stack.pop() as string;
    if (reachable.has(id)) continue;
    reachable.add(id);
    const mod = registry[id];
    if (!mod) throw new Error(`bundler: module not found: ${id}`);
    for (const imp of mod.imports) stack.push(imp.from);
  }
  return reachable;
}

// #endregion graph{ts}

// #region topo{ts}

// CycleError は import が輪を作っているとき。path に循環の経路を持つ。
export class CycleError extends Error {
  constructor(public path: string[]) {
    super(`bundler: circular dependency: ${path.join(" -> ")}`);
    this.name = "CycleError";
  }
}

// topoOrder は依存を先に、それを使う側を後に並べた順序を返す。
// DFS の帰りがけ順が「依存が先」になる。訪問中(gray)のノードに戻れば循環。
export function topoOrder(entry: string, registry: Registry): string[] {
  const order: string[] = [];
  const state = new Map<string, "gray" | "black">(); // gray=訪問中, black=完了
  const path: string[] = [];

  function visit(id: string): void {
    const s = state.get(id);
    if (s === "black") return;
    if (s === "gray") {
      // 訪問中に戻った＝循環。今の経路から循環部分を切り出す。
      const start = path.indexOf(id);
      throw new CycleError([...path.slice(start), id]);
    }
    state.set(id, "gray");
    path.push(id);
    const mod = registry[id];
    if (!mod) throw new Error(`bundler: module not found: ${id}`);
    for (const imp of mod.imports) visit(imp.from); // 依存を先に訪ねる
    path.pop();
    state.set(id, "black");
    order.push(id); // 依存を訪ね終えてから自分を積む＝依存が先に並ぶ
  }

  visit(entry);
  return order;
}

// hasCycle は循環の有無だけを返す（あれば経路、なければ null）。
export function hasCycle(entry: string, registry: Registry): string[] | null {
  try {
    topoOrder(entry, registry);
    return null;
  } catch (e) {
    if (e instanceof CycleError) return e.path;
    throw e;
  }
}

// #endregion topo{ts}

// #region treeshake{ts}

// treeShake は各モジュールについて「実際に使われる export だけ」を返す。
// 到達可能なモジュールが import する名前だけを used とし、他は落とす。
// entry 自身はアプリの入口なので、その export はすべて残す。
export function treeShake(entry: string, registry: Registry): Map<string, string[]> {
  const reachable = collectReachable(entry, registry);

  // 誰かに import される名前を集める（モジュールID → 使われる export の集合）。
  const used = new Map<string, Set<string>>();
  for (const id of reachable) {
    const src = registry[id];
    if (!src) continue; // reachable なので実際には存在する
    for (const imp of src.imports) {
      if (!reachable.has(imp.from)) continue;
      const set = used.get(imp.from) ?? new Set<string>();
      for (const n of imp.names) set.add(n);
      used.set(imp.from, set);
    }
  }

  // 各モジュールの export を、used に含まれるものだけに絞る（entry は全部残す）。
  const kept = new Map<string, string[]>();
  for (const id of reachable) {
    const mod = registry[id];
    if (!mod) continue;
    if (id === entry) {
      kept.set(id, [...mod.exports]);
      continue;
    }
    const u = used.get(id) ?? new Set<string>();
    kept.set(id, mod.exports.filter((e) => u.has(e)));
  }
  return kept;
}

// #endregion treeshake{ts}

collectReachable は entry から出発し、各モジュールの import 先を辿って、到達できるモジュール ID をすべて集める。ここで大事なのは、どこからも import されないモジュールは集合に入らないことだ。プロジェクトに 500 ファイルあっても、entry から辿れるのが 200 なら、バンドルに含まれるのはその 200 だけ。使われないコードは最初から運ばない。テストで、entry から辿れる math・util は集まり、どこからも import されない orphan は含まれないことを固定した。これがバンドルの土台になるグラフだ。

② トポロジカル順序: 依存を先に並べる ​

集めたモジュールを、1 つのファイルに連結する順序を決める。ルールは単純で、あるモジュールが import するモジュールは、そのモジュールより先に来なければならない。使う前に定義されている必要があるからだ。これはグラフのトポロジカル順序で、深さ優先探索(DFS。行ける限り奥へ潜り、行き止まりで戻る辿り方)の帰りがけ順で得られる:

ts
// モジュールバンドラの中核（依存解決）を最小構成でフルスクラッチする。
//
// ブラウザは何百ものファイルを個別に読むのが苦手だ。バンドラは、入口(entry)の
// モジュールから import を辿って依存グラフを作り、依存が先に来るように並べ替えて
// 1 つにまとめる。ついでに、どこからも使われない export を落として無駄を削る
// (tree-shaking)。import が輪を作っていれば(循環依存)、それも検出する。
//
// 肝は3つ:
//   1. 依存グラフ: entry から import を辿り、到達できるモジュールだけを集める
//   2. トポロジカル順序: 依存を先に、それを使う側を後に並べる（循環なら検出）
//   3. tree-shaking: 実際に import される export だけ残し、使われない export を落とす

// #region graph{ts}

// Import は「from から names を取り込む」を表す（import { names } from "from"）。
export interface Import {
  from: string;
  names: string[];
}

// Module は 1 つのモジュール。何を import し、何を export するか。
export interface Module {
  id: string;
  imports: Import[];
  exports: string[];
}

// Registry は id からモジュールを引く表（ファイル解決の結果に相当）。
export type Registry = Record<string, Module>;

// collectReachable は entry から import を辿って到達できるモジュール ID を集める。
// どこからも import されないモジュールは、ここに入らない＝バンドルに含まれない。
export function collectReachable(entry: string, registry: Registry): Set<string> {
  const reachable = new Set<string>();
  const stack = [entry];
  while (stack.length > 0) {
    const id = stack.pop() as string;
    if (reachable.has(id)) continue;
    reachable.add(id);
    const mod = registry[id];
    if (!mod) throw new Error(`bundler: module not found: ${id}`);
    for (const imp of mod.imports) stack.push(imp.from);
  }
  return reachable;
}

// #endregion graph{ts}

// #region topo{ts}

// CycleError は import が輪を作っているとき。path に循環の経路を持つ。
export class CycleError extends Error {
  constructor(public path: string[]) {
    super(`bundler: circular dependency: ${path.join(" -> ")}`);
    this.name = "CycleError";
  }
}

// topoOrder は依存を先に、それを使う側を後に並べた順序を返す。
// DFS の帰りがけ順が「依存が先」になる。訪問中(gray)のノードに戻れば循環。
export function topoOrder(entry: string, registry: Registry): string[] {
  const order: string[] = [];
  const state = new Map<string, "gray" | "black">(); // gray=訪問中, black=完了
  const path: string[] = [];

  function visit(id: string): void {
    const s = state.get(id);
    if (s === "black") return;
    if (s === "gray") {
      // 訪問中に戻った＝循環。今の経路から循環部分を切り出す。
      const start = path.indexOf(id);
      throw new CycleError([...path.slice(start), id]);
    }
    state.set(id, "gray");
    path.push(id);
    const mod = registry[id];
    if (!mod) throw new Error(`bundler: module not found: ${id}`);
    for (const imp of mod.imports) visit(imp.from); // 依存を先に訪ねる
    path.pop();
    state.set(id, "black");
    order.push(id); // 依存を訪ね終えてから自分を積む＝依存が先に並ぶ
  }

  visit(entry);
  return order;
}

// hasCycle は循環の有無だけを返す（あれば経路、なければ null）。
export function hasCycle(entry: string, registry: Registry): string[] | null {
  try {
    topoOrder(entry, registry);
    return null;
  } catch (e) {
    if (e instanceof CycleError) return e.path;
    throw e;
  }
}

// #endregion topo{ts}

// #region treeshake{ts}

// treeShake は各モジュールについて「実際に使われる export だけ」を返す。
// 到達可能なモジュールが import する名前だけを used とし、他は落とす。
// entry 自身はアプリの入口なので、その export はすべて残す。
export function treeShake(entry: string, registry: Registry): Map<string, string[]> {
  const reachable = collectReachable(entry, registry);

  // 誰かに import される名前を集める（モジュールID → 使われる export の集合）。
  const used = new Map<string, Set<string>>();
  for (const id of reachable) {
    const src = registry[id];
    if (!src) continue; // reachable なので実際には存在する
    for (const imp of src.imports) {
      if (!reachable.has(imp.from)) continue;
      const set = used.get(imp.from) ?? new Set<string>();
      for (const n of imp.names) set.add(n);
      used.set(imp.from, set);
    }
  }

  // 各モジュールの export を、used に含まれるものだけに絞る（entry は全部残す）。
  const kept = new Map<string, string[]>();
  for (const id of reachable) {
    const mod = registry[id];
    if (!mod) continue;
    if (id === entry) {
      kept.set(id, [...mod.exports]);
      continue;
    }
    const u = used.get(id) ?? new Set<string>();
    kept.set(id, mod.exports.filter((e) => u.has(e)));
  }
  return kept;
}

// #endregion treeshake{ts}

visit は、あるモジュールの import 先を全部訪ね終えてから、自分を order に積む。だから依存が先に、それを使う側が後に並ぶ。同時に循環も検出する。ノードに 3 色(未訪問・訪問中 gray・完了 black)を付け、訪問中の gray なノードに戻ってきたら、それは import が輪を作っている証拠だ。今辿ってきた経路から循環部分を切り出して CycleError で返す。テストで、依存の math が使う側の util・entry より前に並ぶこと、a→b→c→a の循環が経路つきで検出されることを固定した。循環依存は、初期化順序が定まらず実行時エラーの温床になるので、バンドル時に見つけて警告できるのは大きい。

③ tree-shaking: 使われない export を落とす ​

最後に無駄を削る。依存グラフには「どのモジュールが、どのモジュールから、どの名前を import しているか」の情報がある。これを逆に見れば、各モジュールの export のうち、実際に誰かに import されているものが分かる。どこからも import されない export は、あっても使われない死んだコードだ。落とせる:

ts
// モジュールバンドラの中核（依存解決）を最小構成でフルスクラッチする。
//
// ブラウザは何百ものファイルを個別に読むのが苦手だ。バンドラは、入口(entry)の
// モジュールから import を辿って依存グラフを作り、依存が先に来るように並べ替えて
// 1 つにまとめる。ついでに、どこからも使われない export を落として無駄を削る
// (tree-shaking)。import が輪を作っていれば(循環依存)、それも検出する。
//
// 肝は3つ:
//   1. 依存グラフ: entry から import を辿り、到達できるモジュールだけを集める
//   2. トポロジカル順序: 依存を先に、それを使う側を後に並べる（循環なら検出）
//   3. tree-shaking: 実際に import される export だけ残し、使われない export を落とす

// #region graph{ts}

// Import は「from から names を取り込む」を表す（import { names } from "from"）。
export interface Import {
  from: string;
  names: string[];
}

// Module は 1 つのモジュール。何を import し、何を export するか。
export interface Module {
  id: string;
  imports: Import[];
  exports: string[];
}

// Registry は id からモジュールを引く表（ファイル解決の結果に相当）。
export type Registry = Record<string, Module>;

// collectReachable は entry から import を辿って到達できるモジュール ID を集める。
// どこからも import されないモジュールは、ここに入らない＝バンドルに含まれない。
export function collectReachable(entry: string, registry: Registry): Set<string> {
  const reachable = new Set<string>();
  const stack = [entry];
  while (stack.length > 0) {
    const id = stack.pop() as string;
    if (reachable.has(id)) continue;
    reachable.add(id);
    const mod = registry[id];
    if (!mod) throw new Error(`bundler: module not found: ${id}`);
    for (const imp of mod.imports) stack.push(imp.from);
  }
  return reachable;
}

// #endregion graph{ts}

// #region topo{ts}

// CycleError は import が輪を作っているとき。path に循環の経路を持つ。
export class CycleError extends Error {
  constructor(public path: string[]) {
    super(`bundler: circular dependency: ${path.join(" -> ")}`);
    this.name = "CycleError";
  }
}

// topoOrder は依存を先に、それを使う側を後に並べた順序を返す。
// DFS の帰りがけ順が「依存が先」になる。訪問中(gray)のノードに戻れば循環。
export function topoOrder(entry: string, registry: Registry): string[] {
  const order: string[] = [];
  const state = new Map<string, "gray" | "black">(); // gray=訪問中, black=完了
  const path: string[] = [];

  function visit(id: string): void {
    const s = state.get(id);
    if (s === "black") return;
    if (s === "gray") {
      // 訪問中に戻った＝循環。今の経路から循環部分を切り出す。
      const start = path.indexOf(id);
      throw new CycleError([...path.slice(start), id]);
    }
    state.set(id, "gray");
    path.push(id);
    const mod = registry[id];
    if (!mod) throw new Error(`bundler: module not found: ${id}`);
    for (const imp of mod.imports) visit(imp.from); // 依存を先に訪ねる
    path.pop();
    state.set(id, "black");
    order.push(id); // 依存を訪ね終えてから自分を積む＝依存が先に並ぶ
  }

  visit(entry);
  return order;
}

// hasCycle は循環の有無だけを返す（あれば経路、なければ null）。
export function hasCycle(entry: string, registry: Registry): string[] | null {
  try {
    topoOrder(entry, registry);
    return null;
  } catch (e) {
    if (e instanceof CycleError) return e.path;
    throw e;
  }
}

// #endregion topo{ts}

// #region treeshake{ts}

// treeShake は各モジュールについて「実際に使われる export だけ」を返す。
// 到達可能なモジュールが import する名前だけを used とし、他は落とす。
// entry 自身はアプリの入口なので、その export はすべて残す。
export function treeShake(entry: string, registry: Registry): Map<string, string[]> {
  const reachable = collectReachable(entry, registry);

  // 誰かに import される名前を集める（モジュールID → 使われる export の集合）。
  const used = new Map<string, Set<string>>();
  for (const id of reachable) {
    const src = registry[id];
    if (!src) continue; // reachable なので実際には存在する
    for (const imp of src.imports) {
      if (!reachable.has(imp.from)) continue;
      const set = used.get(imp.from) ?? new Set<string>();
      for (const n of imp.names) set.add(n);
      used.set(imp.from, set);
    }
  }

  // 各モジュールの export を、used に含まれるものだけに絞る（entry は全部残す）。
  const kept = new Map<string, string[]>();
  for (const id of reachable) {
    const mod = registry[id];
    if (!mod) continue;
    if (id === entry) {
      kept.set(id, [...mod.exports]);
      continue;
    }
    const u = used.get(id) ?? new Set<string>();
    kept.set(id, mod.exports.filter((e) => u.has(e)));
  }
  return kept;
}

// #endregion treeshake{ts}

treeShake は、到達可能な全モジュールの import を走査して「使われる名前」を集め、各モジュールの export をそれだけに絞る。math が add(entry から)と sub(util から)を使われ、mul は誰も使わないなら、mul は落ちる。entry 自身はアプリの入口で、その export はアプリのコードそのものなので全部残す。テストで、誰も使わない mul が落ち、使われる add・sub が残ること、どの名前も import されないモジュールは export が空になることを固定した。tree-shaking が効くには、モジュールが静的に解析できる(import/export が実行時に変わらない)ことと、副作用がないことが前提になる。だから ES Modules の静的な import 構文が重要で、これが動的だと何が使われるか静的には分からず、削れない。

動かす ​

下のデモは、モジュールの依存グラフを与えて、到達できるモジュール・連結の順序・使われない export の削除を段階的に見る。孤立モジュールが除かれ、依存が先に並び、死んだ export が落ちる様子を確かめてほしい。

デモバンドラ(依存解決)依存解決
正常な依存グラフ循環依存
モジュール(到達できないものは灰色)
entry
import [add] from math [log] from util
math
export addsubmul
util
import [sub] from math
export log
orphan
export x
到達不能 → 除外
連結順(依存が先):math → util → entry

entry から import を辿って到達できるモジュールだけを集める(孤立した orphan は除外)。依存を先に、 使う側を後に並べる(トポロジカル順序)。どこからも import されない export は死んだコードとして落とす (tree-shaking。math の mul が消える)。import が輪を作れば循環依存として検出する。すべて静的な import/export が読めることが前提で、これが ES Modules の静的構文が重要な理由だ。

設計の観点 ​

  • 静的解析が前提: tree-shaking も依存グラフも、import/export が静的に読めることに依存する。動的 import や実行時に決まる依存は解析できず、削れない。ES Modules の静的構文がこれを可能にした
  • 副作用の扱い: import しただけで副作用(グローバル登録など)があるモジュールは、export が未使用でも消せない。バンドラは sideEffects の指定で副作用の有無を知る
  • 循環依存は警告する: 循環は初期化順序を不定にする。バンドルは通せても実行時にundefinedを掴む危険があるので、検出して警告するのが親切
  • コード分割: すべてを 1 つに固めず、動的 import の境界でチャンクに分ける。初期ロードを軽くする。この章の静的グラフの先にある発展
  • 開発と本番の違い: 開発時は速い再ビルド(esbuild/Vite の no-bundle)、本番は最適化重視(tree-shaking, minify)。同じ依存解決でも目的で手法が変わる

対照と実例 ​

段階やること効果
依存解決import を辿ってグラフ化使うモジュールだけ集める
順序付けトポロジカルソート依存を先に連結
循環検出DFS の gray 検出初期化順序の罠を警告
tree-shaking未使用 export の除去バンドルを小さく

裏どり:

  • webpack: 依存グラフからバンドルを組む定番。ローダーとプラグインで変換を挟む
  • Rollup: tree-shaking を前面に出した先駆。ライブラリ配布向けの小さなバンドル
  • esbuild / Vite: 高速な依存解決とバンドル。Vite は開発時に no-bundle(ブラウザの ES Modules を活用)
  • ES Modules (RFC/仕様): 静的な import/export。tree-shaking が可能になった土台

簡略化したこと ​

  • パースなし: 実物はソースを AST に解析して import/export を抽出する。ここは宣言済みの依存グラフを受け取る
  • 副作用の考慮なし: 副作用のある import は本来 tree-shake できない。ここは純粋前提
  • コード生成なし: 順序と生存 export を出すまで。実際の連結・変換・minify・ソースマップは扱わない
  • 動的 import なし: import() によるコード分割やチャンク生成は扱わない

参考資料 ​