lit-htmlで使われている「仮想DOMじゃない」アルゴリズムについて解説する

追記:もう説明されている方がいました！

https://qiita.com/rikuba/items/92da6d99e2b0f831cc65


# はじめに

[lit-html](https://lit-html.polymer-jp.org/)とは、GoogleのPolymerプロジェクトの一部として作成されたライラブリです。

宣言的なUIプログラミングを行う為の効率的なアルゴリズムとしては、**仮想DOMがメジャー**かもしれませんが、

実は、それ以外にも方法があります。

それは、lit-htmlが実現しているものです。

# `lit-html`の簡単な説明

`lit-html`は、View部分を担うライブラリです。

- テンプレートの定義（`html`）
- コンテナへのレンダリング（`render()`）

の２つによりDOMの差分更新を行うシンプルなライブラリです。

```javascript
let value1 = "class";
let value2 = "some comment";
let value3 = "world";

// テンプレートの定義
const template = html`
  <div class="red ${value1}" color="blue">
    <!-- ${value2} -->
    hello ${value3}
  </div>
`;

// コンテナへのレンダリング
render(template, document.body);
```

カウンターアプリのような場合だと、

ボタンのクリックイベントのたびに、テンプレートに対して何度も`render()`が走ります。

毎回、**状態は異なりますが、テンプレートは変わらない**です。

こうした特性とES6から追加された「テンプレートリテラル」を生かして、

効率的な差分更新を行うことが可能になっています。

まずは、「テンプレートの定義」から説明していきます。

## テンプレートの定義 - `TemplateResult`の作成

lit-htmlは、まず`html`というタグを用いて、テンプレートを定義します。

```javascript
const template = html`
  <div class="red ${value1}" color="blue">
    <!-- ${value2} -->
    hello ${value3}
  </div>
`;
```

`html`は、[テンプレートリテラルの**タグ**と呼ばれるJavaScriptの機能](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/template_strings)です。

実はこれが肝で、今はまだ感覚的な説明になりますが、このテンプレートが表しているのは、

**変更される可能性があるのは、`value1`・`value2`・`value3`の３つだけ**

ということです。

`lit-html`ではこの３つの動的な部分（`Part`と呼ばれます）に対する**参照を保持すること**で、更新コストを最小限に抑えています。

詳しくは後で説明していきますが、まずはテンプレートリテラルについて軽い説明を行います。

テンプレートリテラルはただの文字列補間ではありません。

タグは`function`で、テンプレートリテラル内の

- 静的な部分 `strings`
- 動的な部分 `values`

を引数として受け取ります。

```javascript
const customTag = function(strings, ...values) {
  console.log(strings);
  console.log(values);
};

customTag`str1${value1}str2${value2}str3${value3}str4`;
```

結果：

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/169861/4780bd73-cf1f-5af2-14fb-bab7f970f725.png)

`html`タグはこれを利用して、`TemplateResult`クラスのインスタンスを作成しています。

`TemplateResult`クラスはいくつかのプロパティを持ちます。

1. `strings` ・・・ 静的な部分の文字列を含む配列が入ります
2. `values` ・・・ 埋め込み（${}）の部分の値の配列が入ります
3. `type` ・・・ 'html'または'svg'が入ります。`svg`はSVGを利用する場合の`svg`タグを利用した場合です
4. `processor` ・・・ ここには`TemplateProcesser`というインターフェースを持つオブジェクトが入ります。後述します。

最初に上げたテンプレートの場合は、下のような図になります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/169861/82f5a1e1-1871-3681-2839-88fc89721a36.png)

少し番号が見えにくいですが、stringsは４つあります。

動的な部分は３つです。

状態更新に対してリアクティブなテンプレートを作ろうとすると、毎回`html`タグによる解析が発生しますが、

**テンプレートリテラルによる解析はかなりコストが低い**為、問題になりません。

仮想DOMの場合、毎回仮想DOMツリーを探索しなければいけないため、比較してコストが高いです。

次の章でレンダリングについて記載していきますが、ここからはDOMツリーの探索が発生します。

ただ、**キャッシュの機構や`Part`という部分更新の仕組み**のおかげで、DOMツリーの探索は最初の１回だけになります。

では、説明していきたいと思います。

# レンダリング

レンダリングは、いくつかのフェーズを辿っていくことになります。

ただしフェーズのうちのいくつかは、最初の１回のみ実行され、２回目以降はキャッシュを利用する場合もあります。

そういった部分について、できるだけ細かく説明していきたいと思います。

## フェーズ１：`<template>`要素の中にDOM要素を作っていく

なぜ`<template>`要素の中にDOMを形成するかというと、

`<template>`要素の中は**ScriptやCSS、カスタムエレメントなどが評価されない**からです。

いきなり`render`関数に指定したコンテナ要素にDOM要素を追加していくのではなく、まずテンプレートを作っていきます。

ここで、動的な部分へマーカーを付けていく処理が発生します。

たとえば先ほども書いたような下記のテンプレートだと、

```javascript
html`<div class="red ${value1}" color="blue">
  <!-- ${value2} -->
  hello ${value3}
</div>`
```

このようにマーカーが付けられます。

```html
<template>
  <div style="display: flex" class$lit$="some {{lit-16848889075722862}}">
    <!--  {{lit-16848889075722862}}  -->
    hello
    <!--{{lit-16848889075722862}}-->
  </div>
</template>
```

動的な値が入る属性の**属性名**には、末尾に**`$lit$`**が付与されます。

**属性の値**には、**`{{lit-16848889075722862}}`**という文字が入っていることがわかります。

この「16848889075722862」はランダムに入る数字で、おそらく普通のコメントと差別化するためのものです。

要素の中の動的な部分には、**`<!--{{lit-16848889075722862}}-->`**というコメントが埋め込まれました。

これらはマーカーといって、後でこの`<template>`内のツリーを探索していくときに目印とするものになります。

このDOMツリーの生成は、先ほど作った`TemplateResult`の`strings`を組み合わせて、

`<template>`要素の`innerHTML`に設定しているだけです。

早速フェーズ２についても説明していきます。

## フェーズ２：`Template`クラスのインスタンス生成

先ほども言った通り、`<template>`要素内を探索していきます。

探索には、**TreeWalker API**が使用されます。

探索対象のノードは、`Element`と`Comment`と`Text`です。

探索開始ノードは、`<template>`要素の`content`、つまり子ノードからです。

先ほど書いたテンプレート要素を再度掲載します。

```html
<template>
  <div style="display: flex" class$lit$="some {{lit-16848889075722862}}">
    <!--  {{lit-16848889075722862}}  -->
    hello
    <!--{{lit-16848889075722862}}-->
  </div>
</template>
```

（※ 煩雑になるので、一旦空白しかないテキストノードは考えないことにします）

最初に当たるのは、`div`Elementですね。

```html
<div style="display: flex" class$lit$="some {{lit-16848889075722862}}"></div>
```

`Element`に当たった場合は、まずその要素の属性の一覧を取得します。

この場合は、

- style
- class$lit$

の２つが存在します。

ここで、**動的であることをマーク**したのは`class$lit$`の方なので、この部分について`TemplatePart`が作成されます。

中身はこんな感じです。

```javascript
{
  type: 'attribute',
  index: 0,
  name: "class",
  strings: ["some ", ""],
  sanitizer: undefined
}
```

**`index`**には、この動的な部分＝`TemplatePart`が現れるDOM要素の位置が記録されます。

**`name`**は、属性名です。

**`strings`**には、属性の値を`{{lit-16848889075722862}}`のマーカーで区切った（`split`）した配列が入ります。

`sanitizer`は、あとで値のサニタイズに使われますが、今はあまり気にしなくて大丈夫です。

この`TemplatePart`は、最終的に作られる`Template`クラスの`parts`プロパティに追加されます。

さて、次の要素を見ていきます。

```html
<template>
  <div style="display: flex" class$lit$="some {{lit-16848889075722862}}">
    <!--  {{lit-16848889075722862}}  -->
    hello
    <!--{{lit-16848889075722862}}-->
  </div>
</template>
```

次は、コメントノードです。

```html
<!--  {{lit-16848889075722862}}  -->
```

この`<!--`と`{`の間に挟まるスペースがあるため、ノードの中身が`{{lit-16848889075722862}}`と完全一致せず、

**コメント内の埋め込み**であると判定されます。

ここでできる`TemplatePart`は、

```javascript
{
  type: 'node',
  index: -1
}
```

です。のちのフェーズで`index=-1`は無視されることになります。

では、次のノードに行きます。

```html
<template>
  <div style="display: flex" class$lit$="some {{lit-16848889075722862}}">
    <!--  {{lit-16848889075722862}}  -->
    hello
    <!--{{lit-16848889075722862}}-->
  </div>
</template>
```

`hello`というテキストノードは、マーカー（`<!--{{lit-16848889075722862}}-->`や`{{lit-16848889075722862}}`）を含まない為、カウントはされますが、`TemplatePart`は作成されません。

そして次のコメントノードが`TemplatePart`の作成対象となります。

```html
<!--{{lit-16848889075722862}}-->
```

このコメントノードの「中身」は、`{{lit-16848889075722862}}`になり、マーカーと完全一致する為、動的な更新が必要な部位であると認識されます。

作成される`TemplatePart`は下記のようになります。

```javascript
{
  type: 'node',
  index: 3
}
```

空白のノードを除いたので、`TreeWalker`がこの`TemplatePart`が含まれるノードに出会うのは４番目になります。

なので、`index`は3です。

ここまでで、**探索は終了**になります。

これは、

× 残りのノードが無いから

ではなく

〇 ここまでで、動的な部分（`values.length`）に対する`TemplatePart`が作成されたから

です。

なので、余計なDOM探索は行われません。

こうして、集まった`TemplatePart`は、`Template`クラスのインスタンスの`parts`プロパティに設定されます。

こうして、`Template`クラスのインスタンスができたわけですが、

２回目以降に、同じことをしなくていいように、キャッシュが作成されます。

文字列をキーにもつ、`Map`オブジェクトにキャッシュされます。

キーに設定される文字列は、静的な文字列（`strings`）を`{{lit-16848889075722862}}`でつなぎ合わせたものです。

これが意味するところは、

**テンプレートが持つ静的な部分と動的な部分の構造が一緒**なら、使いまわすということです。

さらに、`TemplateResult.strings`という配列に対する`WeakMap`によるキャッシュも作成されます。

これは文字が完全一致する以前に、**参照そのものが一緒**なら、`Template`のインスタンスを使いまわすということです。

このようにして、まず`Template`のインスタンスに対するキャッシュが行われます。

## フェーズ３：`Template`をもとに、`TemplateInstance`が作成される

フェーズ３では、再度`<template>`要素を探索していくことになります。

先ほど作った`parts`をループし、`index`が示す対象のノードに到達するまで途中のノードはスキップされます。

対象のノードに辿りついたら、最初に作成した`TemplateResult`の`processor`プロパティに指定してある`TemplateProcessor`を用いて、中身を`Part`クラスのインスタンスに変換していきます。

`TemplateProcessor`はインターフェースで、デフォルトでは`DefaultTemplateProcessor`のインスタンスが使用されます。

なのでここからの説明は、`DefaultTemplateProcessor`の処理の説明になります。

これは、`TemplateProcessor`がもつメソッドです。

1. `handleAttributeExpressions`
2. `handleTextExpression`

先ほど、下記の2種類の`TemplatePart`が作られました。

1. `type='attribute'`
2. `type='node'`

それぞれ番号に対応した`TemplateProcessor`のメソッドが割り当てられます。

まず 1. の`handleAttributeExpressions`から説明します。

思い出すために、再度`type='attribute'`のオブジェクトの例を貼ります。

```javascript
{
  type: 'attribute',
  index: 0,
  name: "class",
  strings: ["some ", ""],
  sanitizer: undefined
}
```

ここで、`name`属性についているプリフィックスによって、処理が変わっていきます。

`lit-html`のテンプレートシンタックスでは、

1. `@` + 属性名　・・・　`@click=${e => ...}`のようにイベントを設定する属性に利用
2. `?` + 属性名　・・・　`?checked=${true}`のように真偽値によってON/OFFを切り替えたい属性に利用
3. `.` + 属性名　・・・　`Element`のプロパティ（`CustomElement`のプロパティ）として利用
4. 属性名のみ　　・・・　`id=${'hoge'}`のように文字列の属性に利用

というような書き方ができます。

このあたりのシンタックスを決定しているのが、`DefaultTemplateProcessor`であり、逆に言えばこのモジュールを入れ替えることで、シンタックスを変更できます。

それぞれ

1. `EventPart`
2. `BooleanAttributePart`
3. `AttributePart`または`AttributePart`の配列
4. `PropertyPart`

が作成され、これらはすべて`Part`というインターフェースを実装しています。

`Part`インターフェースは下記のようになります。

```javascript
interface Part {
  readonly value: unknown;
  setValue(value: unknown): void;
  commit(): void;
}
```

`setValue()`は、基本的には`value`プロパティに値をセットしているだけです。

実際に、差分更新の処理を行うのは、`commit()`になります。

詳しくは省きますが、この`Part`は**差分更新を行う対象のDOMノードに対する参照を保持**しています。

そして`TemplateInstance`のインスタンスの`__parts`プロパティに保持されます。

また、`TemplateInstance`のインスタンス自身も、`render()`メソッドの第２引数で指定したDOM要素に対する`WeakMap`に保持されます。※

（※ ここ実は微妙に違って、`WeakMap`に保持されるのは、`NodePart`でその中で、`TemplateInstance`の作成やフェーズ１、２というのが、連鎖的に実行されていきます。また、基本的には`NodePart`が入れ子になる形で、子要素に対する再帰的なツリーの構築も行われていき、それぞれの`NodePart`が差分更新のロジックを持っています。直感的に理解するために、このような書き方になりました。）

このフェーズ３によって、DOMツリーへの要素の挿入が行われます。

# おわり

こうして次回以降の`render()`では、フェーズ１・２・３によって生成された`Part`と参照しているDOMノードに対する差分更新のみが行われていきます。

動的な部分に対する`Part`のみが作成され、キャッシュされるので、メモリ的にも処理速度的にもコストが低いです。

テンプレートリテラルによる解析により、動的な部分のみが抽出でき、DOMノードに対する参照が保持されることで、仮想DOMのようなツリー全体を比較するコストもかかりません。

てっきり、テンプレートリテラルはあくまで、仮想DOMのようなツリー構造の構築のために使われていると思っていたので、動的な部分のみを抽出するという使い方に目から鱗という感じでした。

後半、かなり説明飛ばしてますが、ソースコードはコメントも多いですし、モジュールごとの責務が理解できていると、読みやすいと思いますので、ぜひ読んでみてください。

ここまで、読んでいただきありがとうございました～。