Webブラウザの作り方

# この記事は何？

ほとんどタイトル通りです。
順番に読み進めていけば簡単なWebページが表示できるレベルのWebブラウザを作ることができるように執筆していく予定です。
また**アルゴリズムだけをなるべくわかり易く解説していきたい**ので、記事内で紹介するコードは誰でも読める程度の**擬似コード**です。
自分で実装したい方は、面倒かもしれませんがそれぞれの言語に翻訳してください。

必要な知識としては:


- HTML/CSSが困らない程度に読める
- やる気

これだけです。

(あとこれはただの宣伝ですが、個人的にWeb ブラウザを作ってるので(http://github.com/maekawatoshiki/naglfar) スターをつけてもらえると喜びます) 

# いろいろとパースする

Webページは基本的にHTMLで書かれていますね。あとCSSも。
HTMLもCSSもそのままではただの文字列であって扱いづらいので、パーサを通してDOMノードを作りましょう。
コンパイラなどを作ったことがある方なら ただの字句解析器みたいなものか と思われるかもしれませんが、ここでは知らない人のためにちゃんと説明しようと思います。

## HTMLのパース

たとえば以下のようなHTMLがあるとします。(以後、このサンプルを元に解説を進めます）

```html
<html><body>hello</body></html>
```

とりあえず一文字目から、一文字ずつ読み進めてみましょうか。現在``^``の位置にある文字``<``を読んでいます。

```html
<html><body>hello</body></html>
^
```

HTMLで``<``が見えたら、それはタグであるとすぐにわかりますね。
パーサもそのとおりに実装していきましょう。``parse_nodes``という関数にパース処理を任せます。
今読んでいる文字が``<``なら``parse_element()``にタグの処理を渡し、
``<``でなければ、それはテキストだということなので``parse_text()``に処理を渡します。
また``parse_(element|text)``は処理した結果を返してくるでしょうから、それを``nodes``に追加していきます。
また当然ですが、``parse_nodes``内部のループは文字列の終端にたどり着くか、``</``に到達するまでの間継続します。
「``</``に到達するまで」というのが現時点ではいまいちよくわからないと思いますが、後ほどということで。

```cpp
parse_nodes() {
    nodes = []
    loop {
        if 文字列の終端にたどり着いた { break }
        if "</"という文字列にたどり着いた { break }

        if 現在読んでいる文字 == '<' {
            nodes += parse_element()
        } else {
            nodes += parse_text()
        }
    }
    return nodes
}

parse_element() {
    // 今は省略
}

parse_text() {
    // 今は省略
}
```

### 要素のパース

``parse_element()``の中ではタグの名前やアトリビュート、要素の中身を解析していきますが、この記事では簡単にするためにタグの名前と要素の中身だけを処理することにします。したがって、``<div>aaa</div>``は扱えますが``<div style=''>aaa</div>``はダメだということです。

さて、``<``の次には何が来るのかというと、タグの名前ですね。
現在読んでいる文字を一つ飛ばしましょう。**(ここからのコードはすべて``parse_element()``の中身です)**

```cpp
文字('<')をひとつ飛ばす
```
以下のように、``^``が``h``を指すようになりました。

```html
<html><body>hello</body></html>
 ^
```

すると現在読んでいる文字はタグの名前の一文字目となります。タグは英文字が連続したものなので、英文字が続く限り読み進めていきます。

```cpp
tag_name = "" 
while 現在読んでいる文字がアルファベットである {
    tag_name += 現在の文字
    文字をひとつ飛ばす
}
```

タグの名前が終われば``>``が来ます。飛ばしましょう。

```cpp
文字('>')をひとつ飛ばす
```

タグをひとつ読み終えましたね。

```html
<html><body>hello</body></html>
      ^
```

ここからは要素の中身を読んでいきます。
まず、以下のように``parse_nodes``を実行します。

```cpp
nodes = parse_nodes()
```

そして、``</``を飛ばして、タグの名前を飛ばして、``>``を飛ばせばいいですね。

```cpp
文字('<')をひとつ飛ばす
文字('/')をひとつ飛ばす
while 現在読んでいる文字がアルファベットである {
    文字(任意のアルファベット)をひとつ飛ばす
}
文字('>')をひとつ飛ばす
```

要素についての情報はすべて揃いました。あとは返せば``parse_element``の中身は終わりです。

```cpp
return (名前がtag_name, 中身がnodesの要素)
```

...

ちょっとついていけなくなった方もいると思います。
さきほど、「``</``に到達するまで」という条件の説明を後回しにしていましたが、それがここで重要になってきます。

```html
<html><body>hello</body></html>
      ^
```

上のHTMLで``nodes = parse_nodes()``とすると、``parse_nodes``は``<``を見つけて``parse_element``を呼んで``<body>``を読み始めます。
``<body>``を読み終わった``parse_element``は``nodes = parse_nodes()``を実行して、``parse_nodes``は``parse_text``を呼んで``hello``というテキストを読み込みます（テキストの処理は後ほど）。

```html
<html><body>hello</body></html>
                 ^
```

テキストを読み終えると、``</body>``に到達しますよね? すると``parse_nodes``内のループで「``</``に到達するまで」という条件が``true``になってループを抜けます。そして``parse_element``は``</body>``を飛ばして、完成した要素を返します。

```html
<html><body>hello</body></html>
                        ^
```

この説明じゃちゃんと伝わったのかよくわかりませんね（コメントいただけるとうれしい）。
つまり再帰的に動作するということです。関数がどう呼び出されるかを書き出してみると理解しやすくなるかと思います。

### テキストのパース

テキストのパースは簡単です。テキストはタグ(要するに``<XXX>``の``<``という文字)に到達するまでの文字列だと言えるので:

```cpp
parse_text() {
    str = ""
    loop {
        if 現在読んでいる文字 == '<' { break }
        str += 現在読んでいる文字
        一文字飛ばす
    }
    return (内容がstrのテキスト要素)
}
```

となります。


### ここまでのまとめ

ここまでで説明に使ったコードをまとめます。

```cpp
parse_nodes() {
    nodes = []
    loop {
        if 文字列の終端にたどり着いた { break }
        if "</"という文字列にたどり着いた { break }

        if 現在読んでいる文字 == '<' {
            nodes += parse_element()
        } else {
            nodes += parse_text()
        }
    }
    return nodes
}

parse_element() {
    文字('<')をひとつ飛ばす

    tag_name = "" 
    while 現在読んでいる文字がアルファベットである {
        tag_name += 現在の文字
        文字をひとつ飛ばす
    }

    文字('>')をひとつ飛ばす

    nodes = parse_nodes()

    文字('<')をひとつ飛ばす
    文字('/')をひとつ飛ばす
    while 現在読んでいる文字がアルファベットである {
        文字(任意のアルファベット)をひとつ飛ばす
    }
    文字('>')をひとつ飛ばす

    return (名前がtag_name, 中身がnodesの要素)
}

parse_text() {
    str = ""
    loop {
        if 現在読んでいる文字 == '<' { break }
        str += 現在読んでいる文字
        一文字飛ばす
    }
    return (内容がstrのテキスト要素)
}
```

### 少し発展

ここまでで説明したパーサだと、``img``などの閉じダグの必要ない要素を処理できませんが、
閉じタグの必要ない要素は[定義](https://developer.mozilla.org/ja/docs/Glossary/Empty_element)されているので比較的簡単に対応できます。
処理したい場合 ``parse_element``を以下のようにします:

```cpp
parse_element() {
    文字('<')をひとつ飛ばす

    tag_name = "" 
    while 現在読んでいる文字がアルファベットである {
        tag_name += 現在の文字
        文字をひとつ飛ばす
    }

    文字('>')をひとつ飛ばす

    // ***** 追加 *****
    if tag_nameが閉じタグの必要ないタグ名である {
        return (名前がtag_name, 中身が空の要素)
    }

    nodes = parse_nodes() 

    文字('<')をひとつ飛ばす

    文字('/')をひとつ飛ばす
    while 現在読んでいる文字がアルファベットである {
        文字(任意のアルファベット)をひとつ飛ばす
    }
    文字('>')をひとつ飛ばす

    return (名前がtag_name, 中身がnodesの要素)
}
```

また今回作ったパーサだと空白文字を飛ばすことや、エラー時の処理などを完全に省いているので実用には耐えません。
興味を持った方はBlinkやServoなどの実装を読んでみることをおすすめします。

## CSSのパース

この章は後で書きますが、
CSSの言語仕様は検索すればすぐに見つかるので、早く作りたい！という方は各自お願いします。

# レンダーツリー

レンダーツリーは、スタイルの適応されたHTMLのノード、つまり視覚的な情報を持った矩形が表示される際と同じ正しい順番で並んだものです。
まずはHTMLのノードに、スタイルシートで指定した属性を適応させていきましょう。

.....

# レイアウト計算

## Block要素

## Inline要素

# 画面への表示

... sorry, coming soon.

# 参考になりそうなサイト

ブラウザのしくみ 最新ウェブブラウザの内部構造: https://www.html5rocks.com/ja/tutorials/internals/howbrowserswork/#Parsing_general