百聞は一実装に如かず。仮想DOM・diff・useStateを100行ちょっとで自作する

前回、Virtual DOMの正体・Reconciliationの計算量・keyの意味を、理屈でみっちり掘り下げました。でも理屈だけだと、どうしても「へー」で終わりがちです。

今回は実際に手を動かします。仮想DOM・diff・patch・useStateを、全部で150行くらいのミニReactとして自作します。写経しながら読むと、前回の理屈が体に馴染むはずです。

• Step 1：仮想DOMを作る関数 h()
• Step 2：仮想DOM→本物のDOMに変換する createDom()
• Step 3：差分を見つけて反映する patch()
• Step 4：子要素のリストを比較する patchChildren()（keyの効果を実際に事故らせて確認します）
• Step 5：useState のミニ実装

最後に、これらを組み合わせて前々回のTODOアプリを動かします。

---

Step 1：仮想DOMを作る関数 h()

前回話した「ただのオブジェクト」を作りやすくする関数を書きます。ReactでいうReact.createElementのミニ版です。

function h(type, props, ...children) {
  return {
    type,                      // "div" とか "li" とかのタグ名
    props: props || {},        // 属性やイベントハンドラ
    children: children.flat()  // 子要素（ネスト対応でflat）
  };
}

使ってみます。

const vnode = h("ul", { id: "todo-list" },
  h("li", {}, "牛乳を買う"),
  h("li", {}, "Qiita書く")
);

前回「JSXの正体はReact.createElementの入れ子呼び出し」という話をしましたが、まさにこれです。

<ul id="todo-list">
  <li>牛乳を買う</li>
</ul>

というJSXは、ビルド時に

h("ul", { id: "todo-list" }, h("li", {}, "牛乳を買う"))

に変換されているだけでした。

---

Step 2：仮想DOM → 本物のDOM（初回描画）

設計図があっても、本物のDOMにしないと画面には出ません。

function createDom(vnode) {
  // テキスト（文字列・数値）はテキストノードに
  if (typeof vnode === "string" || typeof vnode === "number") {
    return document.createTextNode(vnode);
  }

  const dom = document.createElement(vnode.type);
  setProps(dom, vnode.props);

  vnode.children.forEach(child => {
    dom.appendChild(createDom(child));
  });

  return dom;
}

function setProps(dom, props) {
  for (const [key, value] of Object.entries(props)) {
    if (key === "key") continue; // keyはReact内部だけの目印。DOMには書き込まない
    if (key.startsWith("on")) {
      dom.addEventListener(key.slice(2).toLowerCase(), value);
    } else if (key === "value") {
      dom.value = value;
    } else {
      dom.setAttribute(key, value);
    }
  }
}

ポイントは再帰です。子要素も仮想DOMなので、createDomを子に対しても呼べば、ツリー全体が一気に本物のDOMになります。

document.getElementById("root").appendChild(createDom(vnode));
// → 画面にリストが出る

このcreateDomは「設計図から本物のDOMを新築する工事担当」です。出番は2つあります。初回描画（今ここ）と、この後作るpatchが「これはリフォーム不可能、新築で置き換え」と判断したときの部品として、です。

（setPropsの冒頭にkeyを除外する1行を足しています。keyはReactが要素を見分けるための内部的な目印で、本物のDOMの属性として書き込むものではないからです。）

---

Step 3：差分を見つけて反映する patch() —— 判定は4パターンだけ

やりたいことはシンプルです。

古い設計図（oldVNode）と新しい設計図（newVNode）を比較して、
「違うところだけ」本物のDOMを直す

前回、「型が違えば別物として作り直す」というReactの割り切りの話をしました。それをコードにすると、判定はこの4パターンに集約されます。

function patch(parent, dom, oldVNode, newVNode) {
  // ① 新しい方に無い → 削除
  if (newVNode === undefined) {
    parent.removeChild(dom);
    return;
  }

  // ② 古い方に無い → 追加
  if (oldVNode === undefined) {
    parent.appendChild(createDom(newVNode));
    return;
  }

  // ③ 別物になった → 置き換え（前回の「型が違えば作り直す」ルール）
  if (changed(oldVNode, newVNode)) {
    parent.replaceChild(createDom(newVNode), dom);
    return;
  }

  // ④ 同じtypeの要素 → 中身だけ更新
  if (typeof newVNode !== "string" && typeof newVNode !== "number") {
    updateProps(dom, oldVNode.props, newVNode.props);
    patchChildren(dom, oldVNode.children, newVNode.children);
  }
}

function changed(a, b) {
  return (
    typeof a !== typeof b ||                            // 型が違う（要素⇔テキスト）
    ((typeof a === "string" || typeof a === "number")
      && a !== b) ||                                    // テキストの中身が違う
    a.type !== b.type                                    // タグ名が違う（div⇔span等）
  );
}

changedが文字列同士にまでa.type !== b.typeを素通りさせているのは手抜きに見えるかもしれませんが、文字列に.typeは存在しない（アクセスするとundefinedが返るだけ）ので、undefined !== undefinedはfalseになり、ちゃんと正しく動きます。JSの緩さに助けられているポイントです。

propsの差分更新も書いておきます。

function updateProps(dom, oldProps, newProps) {
  for (const key of new Set([...Object.keys(oldProps), ...Object.keys(newProps)])) {
    if (key === "key") continue;
    const oldVal = oldProps[key];
    const newVal = newProps[key];
    if (oldVal === newVal) continue; // 同じなら何もしない ← これが差分更新の本体

    if (key.startsWith("on")) {
      const event = key.slice(2).toLowerCase();
      if (oldVal) dom.removeEventListener(event, oldVal);
      if (newVal) dom.addEventListener(event, newVal);
    } else if (key === "value") {
      if (dom.value !== newVal) dom.value = newVal;
    } else if (newVal === undefined) {
      dom.removeAttribute(key);
    } else {
      dom.setAttribute(key, newVal);
    }
  }
}

---

Step 4：子要素のリストを比較する patchChildren() —— keyの正体をここで自分の手で事故らせる

子要素の比較、いちばん素朴な実装はこうです。

function patchChildren(dom, oldChildren, newChildren) {
  const max = Math.max(oldChildren.length, newChildren.length);
  for (let i = 0; i < max; i++) {
    patch(dom, dom.childNodes[i], oldChildren[i], newChildren[i]);
  }
}

**「上から順に、同じ位置（index）同士で比較する」**だけです。実はこれ、key={i}を指定したときのReactの挙動と実質同じです。

ここで大事な感覚がひとつあります。patch内のchanged判定は「一致する相手を探す」ためのものではありません。同じ位置同士を機械的にペアにしたあとで、「このDOMを使い回すか、壊して作り直すか」を判定するためだけに使われます。位置がそのまま身元になる、という割り切りです。

実際に事故らせてみる

TODOが3件あるとします。

古: [牛乳を買う, Qiita書く, 筋トレ]

先頭の「牛乳を買う」を削除しました。

新: [Qiita書く, 筋トレ]

index同士で比較すると、こうなります。

i=0: 「牛乳を買う」vs「Qiita書く」→ テキストが違う → changed=true → 書き換え
i=1: 「Qiita書く」 vs「筋トレ」  → テキストが違う → changed=true → 書き換え
i=2: 「筋トレ」   vs undefined  → 削除

実際にやったのは「先頭を1個消した」だけなのに、DOM操作は「2箇所書き換え＋1個削除」の3回発生しました。しかもこれがinputを含む行だったらもっと悲惨です。DOMの書き換えは<li>のテキスト部分だけで、inputに入力中の値はその場（そのindexの位置）に残ります。結果、「消したはずの行の入力内容が、次の行に化けて残る」という、前回予告したバグの完成です。

keyがあると何が変わるか

各要素に、位置ではなく身元を示すID＝keyを持たせます。

function patchChildren(dom, oldChildren, newChildren) {
  // keyを持つ古い子を「key → {vnode, dom}」のマップにしておく
  // keyが無い要素は、indexを仮のkeyとして扱う（＝これまで通りの位置ベース）
  const keyed = new Map();
  oldChildren.forEach((child, i) => {
    const k = child?.props?.key ?? i;
    keyed.set(k, { vnode: child, dom: dom.childNodes[i] });
  });

  newChildren.forEach((newChild, i) => {
    const key = newChild?.props?.key ?? i;

    if (keyed.has(key)) {
      // 同じkey（またはindex）の要素が前回もいた → 「同一人物」として再利用
      const { vnode: oldChild, dom: oldDom } = keyed.get(key);
      keyed.delete(key);

      if (oldDom !== dom.childNodes[i]) {
        dom.insertBefore(oldDom, dom.childNodes[i] ?? null);
      }
      patch(dom, oldDom, oldChild, newChild);
    } else {
      // 前回いなかった → 新規作成
      dom.insertBefore(createDom(newChild), dom.childNodes[i] ?? null);
    }
  });

  // マップに残った＝新しい方にいない → 削除
  keyed.forEach(({ dom: oldDom }) => dom.removeChild(oldDom));
}

（child?.props?.key ?? iで、keyが無い要素にはindexを仮のkeyとして与えています。こうしておかないと、keyを持たない要素同士—例えば後で出てくるTODOアプリのinputやbutton—が毎回「新規作成」扱いになり、古いDOMノードが消されないまま増え続けるバグになります。実際に手を動かしてみて見つけた落とし穴です。）

さっきの例をkey付きでやり直すと、

古: [key:a 牛乳, key:b Qiita, key:c 筋トレ]
新: [key:b Qiita, key:c 筋トレ]

→ key:b は前回もいた → 同一人物として再利用
→ key:c は前回もいた → 同一人物として再利用
→ key:a は新しい方にいない → 削除

inputの中身は、DOMノードごと正しい「牛乳を買う」の生まれ変わりとして扱われるので、入力内容が正しい行にくっついたまま残ります。 前回の伏線、ここで回収です。

keyとは「この要素はどの要素の生まれ変わりか」をReactに教える身元証明書。 key={i}（index）を使うと「位置＝身元」になってしまい、要素を消したり並べ替えたりした瞬間に身元が入れ替わって事故る。

正直に告白します：これでもまだ完璧じゃない

insertBeforeとremoveChildの呼び出しを実際にログしながら、さっきの例をもう一度動かしてみます。

古: [key:a 牛乳, key:b Qiita, key:c 筋トレ]
新: [key:b Qiita, key:c 筋トレ]

実際のログ:
insertBefore(b, a)
insertBefore(c, a)
removeChild(a)

3回の操作が発生しています。 本当は削除1回で済むはずなのに、Qiitaと筋トレのDOMノードまで「移動」扱いになってしまっています。理由は単純で、このコードは「今回、位置iに来るべき要素」と「現在その位置に物理的にあるDOMノード」を比較しているだけで、「動かさなくてもいずれ正しい順番になる」ということまでは考えていないからです。

でも安心してください。幸い、「正しさ」の方は直ったままです。insertBeforeは既存のDOMノードを移動するだけで、壊して作り直しているわけではないので、input要素の中身・フォーカス・カーソル位置といった状態は移動されても保持されます。「正しさ」と「操作回数の最小化」は別問題で、keyが直したのは前者でした。

じゃあ後者も直せばいいのでは、と思って「前回の位置を覚えておいて、動かさなくていい要素を先に見分ける」版を書いてみたんですが——単純な工夫だと、削除だけのケースは直っても、並べ替えが絡むケースで正しさ自体が壊れることが、実際に手を動かして検証したら分かりました。 「ちょっとインデックスを覚えておけばいいのでは」が、思ったより甘くなかったわけです。「壊さずに操作回数だけ最小化する」には、ちゃんと理論的に裏付けられた解法が必要で、それが次に話すLISです。

この問題を理論的に正しく解く方法：LIS

「操作回数を、正しさを壊さずに最小化する」には、「動かさなくていい要素の集合」を先に特定してから、それ以外だけを動かすという発想が必要です。ここで使われるのが**最長増加部分列（LIS: Longest Increasing Subsequence）**という、既存の枯れたアルゴリズムです。

大づかみに言うと、

新しい並びの各要素が「元は何番目にいたか」を並べる
  ↓
その並びの中から「順序を保ったまま増え続ける最長の部分列」を見つける
  ↓
その部分列に該当する要素だけは、他との相対順序が既に正しいので「動かさなくていい」
  ↓
残りの要素だけを動かせば、理論上最小回数で並べ替えが完了する

これでピンとこなければgit diffを思い浮かべてください。あれも「2つのファイルを比較して最小の変更点だけ見つける」処理で、中身はMyers (1986) “An O(ND) Difference Algorithm and Its Variations”という、今回の木の編集距離とは別系統の、列（シーケンス）のdiffを扱う古典アルゴリズムです。keyed diffが解いているのは本質的に「子要素という列をどう最小手数で書き換えるか」なので、木の編集距離より、むしろこちらの列diffの親戚にあたります。

実際、Vue 3のkeyed diffはLISを使って移動回数を最小化しています。 じゃあReactは？というと、少し意外なことに、Reactの実際の実装（lastPlacedIndexという変数で「最後に確定した位置」を追跡する、独自の一回走査の工夫）は、単純な追加・削除のようなよくあるケースはうまく処理できるものの、LISほど網羅的に「あらゆる並べ替えパターンで最小回数」を保証するものではないようです。さっき私が試して壊れた素朴な工夫と同様、「ちゃんとした理論的裏付け（LIS）なしに、ちょっとした工夫だけで済まそうとする」のがいかに難しいかを、Reactの実装自体も物語っています。

---

Step 5：useStateのミニ実装

最後に、「stateが変わったら自動でdiff & patchが走る」仕組みを作ります。

let states = [];         // 全stateの保管場所
let cursor = 0;          // 「今何個目のuseStateか」のカーソル
let oldVTree = null;
let rootDom = null;
let AppComponent = null;

function useState(initialValue) {
  const i = cursor;      // この呼び出しの「席番号」を確保
  cursor++;

  if (states[i] === undefined) {
    states[i] = initialValue; // 初回だけ初期値をセット
  }

  const setState = (newValue) => {
    states[i] = newValue;
    rerender();           // stateが変わったら再描画をキック
  };

  return [states[i], setState];
}

function rerender() {
  cursor = 0;                          // カーソルをリセット
  const newVTree = AppComponent();     // 関数を呼ぶ＝新しい設計図を丸ごと作る
  patch(rootDom, rootDom.firstChild, oldVTree, newVTree);
  oldVTree = newVTree;
}

function mount(component, container) {
  AppComponent = component;
  rootDom = container;
  cursor = 0;
  oldVTree = component();
  container.appendChild(createDom(oldVTree));
}

気づきポイント：Hooksの「順番縛り」の正体

図の下半分のように、こう書くと事故ります。

if (condition) {
  const [a, setA] = useState(0); // 呼ばれたり呼ばれなかったり
}
const [b, setB] = useState("");

conditionがtrueの回はa→index0, b→index1。falseの回はaの呼び出しがまるごとスキップされるので、bがindex0を受け取ってしまいます。bなのにaの値が返ってくる、という事故です。

Reactの公式ルール「フックはトップレベルでのみ呼ぶ。条件分岐やループの中で呼んではいけない」——あれは行儀作法ではなく、この「呼び出し順＝配列のインデックス」という仕組みが根本から壊れるからでした。自作すると一発で腑に落ちます。

---

完成：TODOアプリを動かす

全部品が揃いました。前々回のTODOアプリを、React無しで動かせます。

function App() {
  const [todos, setTodos] = useState([]);
  const [text, setText]   = useState("");

  return h("div", {},
    h("input", {
      value: text,
      onInput: (e) => setText(e.target.value)
    }),
    h("button", { onClick: () => {
      setTodos([...todos, { id: crypto.randomUUID(), text }]);
      setText("");
    }}, "追加"),
    h("ul", {},
      todos.map(todo =>
        h("li", { key: todo.id },   // ← ちゃんとIDをkeyに
          todo.text,
          h("button", { onClick: () =>
            setTodos(todos.filter(t => t.id !== todo.id))
          }, "削除")
        )
      )
    )
  );
}

mount(App, document.getElementById("root"));

動かして、DevToolsのElementsパネルを開いたままTODOを追加・削除してみてください。変わった要素だけがハイライトされる（＝そこしかDOMを触っていない）のが見えるはずです。これが差分更新です。

---

本物のReactとの違い（正直コーナー）

ミニReactで考え方は本物と同じですが、本物はさらに賢いです。ざっくり差分だけ挙げます。

• バッチ更新：ミニ版はsetStateのたびに即座に再描画しますが、本物は1つのイベント内の複数のsetStateをまとめて1回で描画します。これが次回の「setしたのに値が変わらない」の伏線です
• Fiberアーキテクチャ：React 16以降、diff作業を細かい単位に分割して中断・再開できる仕組みになっています。重い更新中でもユーザー入力を優先できます（詳しくは近いうちの回で扱います）
• コンポーネント単位の再レンダリング：ミニ版は毎回Appごと作り直しますが、本物はstateが変わったコンポーネントより下だけを再計算します
• 合成イベント：イベントリスナーを要素ごとに付けず、ルートで一括管理しています
• keyed diffの最適化：上で見た通り、Reactの実装はlastPlacedIndexという一回走査の工夫で一部のケースをカバーしていますが、Vue3のようなLISに基づく網羅的な最適化まではしていません

でも根っこは今日作ったものと同じ、「設計図を丸ごと作り直して、差分だけ本物に反映する」です。

---

まとめ

• 仮想DOMはただのJSオブジェクト。h()で作れる
• createDomが設計図を本物のDOMに新築し、patchが4パターンの判定で差分だけ書き換える
• 子要素の比較はkeyがあるかどうかで別人になる。keyは身元証明書
• ただし単純なkeyed diffは、正しさは直っても、操作回数の最小化まではしてくれない。そこにMyersのdiffやLISという列diffの理論が絡んでくる
• useStateは呼ばれた順番＝配列のインデックスで管理されている。だからHooksを条件分岐に入れてはいけない

理屈で聞くのと、自分の手でバグらせて直すのとでは、記憶への残り方が全然違います。

---

参考文献

• Myers, E. W. (1986). An O(ND) difference algorithm and its variations. Algorithmica, 1(2).
• Vue 3のkeyed diff実装（renderer.ts内のpatchKeyedChildren、LISベースの移動最小化）
• 前回の参考文献（Tai 1979、Zhang & Shasha 1989、Zhang・Statman・Shasha 1992、Demaine他 2007、Bringmann他 2018、Mao 2021、Bunke 1997、Pawlik & Augsten 2016、Bille 2005）も引き続き背景として繋がっています

---

次回

useStateの罠：「setしたのに値が変わらない」の正体

• setCount(count + 1) を3連発しても1しか増えない事件
• console.logすると古い値が出る事件（クロージャの話）
• 今回作ったミニReactに「バッチ更新」を実装して、仕組みから理解する

を書きます。