Promiseで依存関係の並行ロードを実装する #JavaScript

TL;DR

コールバックで実装すると一緒に並列処理もできて楽です。ただし依存関係が循環していないかは別途調べる必要があります。

問題の定義

依存先を先に読み込むことです。
すなわち複数の機能を読み込む際に依存先が読み込まれていることを保証する順番で読み込むことです。

順序を決定して読み込む

順序決定

依存関係は各機能を頂点とし、依存関係を辺(依存元→依存先)とするDAG(有向非巡回グラフ)として表すことができます。これは依存関係が循環してはならないことと同値です。
DAGにはトポロジカルソート(ノードを1列に並べる方法)の解が存在することが保証されるため、依存関係グラフにトポロジカルソートを適用することで読み込み順を生成することができます。
トポロジカルソートの段階で依存関係が循環しているかを判定できます。

例として次のような依存関係を考えます。

タスク	依存先
A	-
B	A
C	A
D	B, C

まず、タスクを次のようなオブジェクトで表すとします。なお name フィールドは固有名、run は Promise のファクトリです。

{
  name: 'task-D',
  requires: ['task-B', 'task-C'],
  run: () => new Promise((resolve, reject) => {
    setTimeout(() => {
      console.log('D');
      resolve();
    }, 1000);
  })
}

依存関係を解決する処理は次のようになります。トポロジカルソートにはDFS(深さ優先探索)を利用しています。

// DAGとしてトポロジカルソートする
const tsorted = (() => {
  // 名前, 子要素(依存先), 訪問済みラベルを持つノードを作成
  const nodes = tasks.map(task => ({
    name: task.name,
    children: task.requires,
    visited: false
  }));
  // childrenの要素をノードの名前からオブジェクトに変更
  nodes.forEach((node => {
    node.children = node.children.map((name) => nodes.find(n => n.name == name));
  }));
  const result = [];

  // DFSで探索
  const visit = (node) => {
    if(!node.visited) {
      node.visited = true;
      node.children.forEach(node => {
        visit(node);
      });

      result.push(node.name);
    }
  }

  nodes.forEach(node => {
    visit(node);
  });

  return result;
})();

ソートの結果はタスクA, タスクB, タスクC, タスクD の順になります。

実行

単純に順番に実行することができます。

// 順に実行
let p = Promise.resolve();
tsorted.forEach(name => {
  const task = tasks.find(t => t.name == name);
  p = p.then(task.run);
});

これを改良して、並行して実行するようにすることもできます(ループで次の Promise が現在の Promise に依存しないならまとめてしまう)こともできますが、すべての依存グラフに対してうまく動作するわけではありません。例えば非連結なグラフなどの半順序集合を考えた際に極大元が複数存在する場合、うまく並行処理ができません。
並列処理を行える環境では並列処理数を管理しながら並列実行できるので便利だと思いますが、JSではあまり恩恵がないと考えられます。

コールバックによる実装(並行処理)

JSには Promise やイベントループが存在するので、これを利用します。

すべて走査する方法

大規模でなければ十分な実装だと思われます。この場合タスクが終了しているかどうかを知る方法が必要になります。また、完了の更新タイミングと Promise.then のコールバックが呼ばれるタイミングは保証されないので、多重ロードを避けるため実行中かどうかを知る方法も必要になります。

const list = tasks.map(task => {
  const obj = Object.create(task);
  obj.compleated = false;
  obj.pending = false;
  return obj;
});
// requiresに対応するインデックスの配列を作成
list.forEach(task => {
  task.children = task.requires.map((name) => list.findIndex(t => t.name === name));
});

// 実行できるタクスをすべて実行する関数
const execute = () => {
  list.forEach((task) => {
    if(!task.compleated && !task.pending) {
      // タスクが未完了
      if(task.children.every(index => list[index].compleated)) {
        // 前提タスクがすべて終了している
        task.pending = true;
        task.run().then(() => {
          task.compleated = true;
          task.pending = false;
          execute();
        });
      }
    }
  });
}
execute();

Promise.then にコールバックとして登録することでタスクが終了した際にすべて走査して実行します。

EventTargetを使う方法

EventTarget と CustomEvent (サンプルでは CustomEvent が使用できない環境のため Event を直接利用しています) を利用することで前提タスクの完了にコールバックを登録する方法です。完了済み・実行中の情報を保持する必要がありませんが、複数のタスクに依存する場合それらがすべて読まれたかを判断する必要があります。言語レベルでのイベントループが存在するため、効率の良い方法だと思います( ~~せっかく Promise 使ってるのにイベントを使うんですか?~~ )。

const list = tasks.map(task => {
  const obj = Object.create(task);
  obj.eventTarget = new EventTarget();
  obj.count = 0;
  return obj;
});

// イベント登録
list.forEach((task) => {
  task.requires.forEach((name) => {
    const targetTask = list.find(t => t.name === name);
    const listener = () => {
      task.count += 1;
      if(task.count >= task.requires.length) {
        // ロードされるべき数に達している
        targetTask.eventTarget.removeEventListener('load', listener);
        task.run().then(() => {
          task.eventTarget.dispatchEvent(new Event('load'));
        });
      }
    }
    targetTask.eventTarget.addEventListener('load', listener);
  });
});

// 依存先がないタスクを実行
list.forEach((task) => {
  if(task.requires.length === 0) {
    task.run().then(() => {
      task.eventTarget.dispatchEvent(new Event('load'));
    });
  }
});

`Promise` の合成を利用する方法

Promise の実行タイミングを制御できれば Promise.all で合成することで順次実行の例のようにいい感じに実装できるんじゃないかなと思います。具体的な実装は思いついていませんが、 Promise ファクトリを合成するライブラリを書けばできそうだなと思いました( Promise.all を任意のタイミングで呼ぶ関数を作ってしまうと多重ロードが発生してしまうため )。思いついたら追記します。

Promiseで依存関係の並行ロードを実装する