Web
ブラウザ
自作

Webブラウザの作り方

この記事は何?

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

必要な知識としては:

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

これだけです。

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

いろいろとパースする

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

HTMLのパース

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

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

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

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

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

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()の中身です)

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

以下のように、^hを指すようになりました。

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

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

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

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

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

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

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

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

nodes = parse_nodes()

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

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

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

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

...

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

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

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

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

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

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

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

テキストのパース

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

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

となります。

ここまでのまとめ

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

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などの閉じダグの必要ない要素を処理できませんが、
閉じタグの必要ない要素は定義されているので比較的簡単に対応できます。
処理したい場合 parse_elementを以下のようにします:

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