Module Graph の世界

どのように依存グラフを作るのか?

有向非巡回グラフ (DAG)


エントリーポイントからのすべてのモジュールの依存を知るには、閉路がない有向グラフ(つまり一方通行で自身に戻らない)である DAG を利用する。


そして半順序関係とみなす DAG で必ず成り立つトポロジカルソートを使い、 依存関係を構成する。

トポロジカルソート


𝑂(|𝑉|+|𝐸|)


すべてのノード v1, v2 に対して、到達可能経路がある場合に必ず v1 を v2 の前に持ってくるアルゴリズムであり、 この DAG の半順序を拡張し、全順序を得る。


主な実現方法として、深さ優先探索(DFS)と幅優先探索(BFS)のどちらかがあり、どちらも計算量は同じとなる。


webpack での実装例

execute
const vertices = new Map(); // key: name, value: deps
const visited = new Set();
const res = [];

vertices.set('v', ['a']); //      v -> a
vertices.set('a', ['b', 'c']); // a -> b, a -> c
vertices.set('b', ['d']); //      b -> d
vertices.set('c', ['b', 'd']); // c -> d, c -> d
vertices.set('d', []); //         d

for (const [name] of vertices) {
  dfs(name);
}
console.log(res.reverse()); // [ 'v', 'a', 'c', 'b', 'd' ]

function dfs(name, stack = new Set()) {
  if (visited.has(name)) return;
  visited.add(name);
  stack.add(name);
  const edges = vertices.get(name);

  for (const edge of edges) {
    // 再帰スタックにすでに頂点が入っている場合、閉路グラフである
    if (stack.has(edge)) return;
    dfs(edge, stack);
  }
  stack.delete(name);
  res.push(name);
}

ランタイムではどのように処理されるのか？

ランタイムでは、エントリーポイントから再帰的に走査しモジュールを随時実行していく。


また実行は、Node.js のモジュールシステム同様に IIFE を使いスコープを確保し、
引数等で Object/Array の形で必要なすべてのモジュールを渡しエントリーポイントから実行する。
webpack5 から引数ではなく、内部で直接各モジュールを宣言するように変わったが、仕組みは同じ。


詳しくは、module bundler の作り方(準備編)を参照。

execute
// 例なのでESMの対応はないが仕組みは一緒
((modules) => {
  const usedModules = {};

  function require(moduleId) {
    if (usedModules[moduleId]) {
      return usedModules[moduleId].exports;
    }

    // ModuleId(0, 1, ...)を入れ、最低限必要なexportsを定義し初期化
    const module = (usedModules[moduleId] = { exports: {} });

    // 自身の関数であるrequireを渡すことにより、各モジュール内でこの関数を実行し再帰走査する
    // つまり、各モジュール内のmodule/requireはここで上書きされる
    modules[moduleId](module, module.exports, require);

    return module.exports;
  }

  return require(0); // entry pointである0(index.js)から開始
})({
  0 /* index.js */: function (module, exports, require) {
    const say = require(1); // ビルド時にファイル名からmoduleIdへ書き換えられる
    say('hello world');
  },
  1 /* foo.js */: function (module, exports, require) {
    module.exports = function say(txt) {
      console.log(txt, 'from foo.js!');
    };
  },
});

Scope Hoisting


Scope Hoistingとは静的解析をする ECMAScript Modules のときに有効化できる同列階層のモジュールを統合するアルゴリズム。
これにより、無駄な再帰処理をなくし実行速度の向上とバンドルサイズを減らすことが可能となる。

無効時

var __webpack_modules__ = [
  /* 0 */
  (__unused_webpack_module, __webpack_exports__, __webpack_require__) => {
    __webpack_require__.r(__webpack_exports__);
    /* harmony import */ var _foo__WEBPACK_IMPORTED_MODULE_0__ = __webpack_require__(1);

    (0, _foo__WEBPACK_IMPORTED_MODULE_0__.default)('hello world');
  },
  /* 1 */
  (__unused_webpack_module, __webpack_exports__, __webpack_require__) => {
    __webpack_require__.r(__webpack_exports__);
    /* harmony export */ __webpack_require__.d(__webpack_exports__, {
      /* harmony export */ default: () => /* export default binding */ __WEBPACK_DEFAULT_EXPORT__,
      /* harmony export */
    });
    /* harmony default export */ function __WEBPACK_DEFAULT_EXPORT__(txt) {
      console.log(txt, 'from foo.js!');
    }
  },
];

有効時

var __webpack_modules__ = [
  /* 0 */
  (__unused_webpack_module, __webpack_exports__, __webpack_require__) => {
    // ESM COMPAT FLAG
    __webpack_require__.r(__webpack_exports__); // CONCATENATED MODULE: ./src/foo.js

    /* harmony default export */ function foo(txt) {
      console.log(txt, 'from foo.js!');
    } // CONCATENATED MODULE: ./src/index.js

    foo('hello world');
  },
];

まとめ



  • モジュールの依存関係はグラフ理論を使い表現できる
  • ランタイムでは、再帰処理の走査が走るので深さはパフォーマンスに影響がでる可能性がある
    • そのための Scope Hoisting などのアルゴリズムがあるが、これらは静的解析が必要なため基本的には ESM を使うべき

参考資料


The End