この記事はドワンゴ Advent Calendar 2020 16日目の記事です。アドベントカレンダーが好きすぎて、これに加えて最終日も書かせていただきます。急拵えなので内容は薄いですが、興味があればお付き合いください。
はじめに
この記事で紹介するXPath 1.0パーサは、ドワンゴ Advent Calendar 2020 最終日にて紹介予定のHTMLパーサである「gammo」向けに開発したものである。
最終日の内容はHTMLパーサに特化したものとなるため、この記事ではgammoが構築したDOMツリーをtraverseするための仕組みとして、XPath 1.0を実装した話を紹介する。
XPath 1.0
XPath 1.0は1999年に勧告されたXSLT 1.0と同時に公表されたもので、現在の最新バージョンである3.1と比較すると非常に機能が少ないシンプルな仕様となっている。
XPath 1.0を選択した理由は単に機能が非常にシンプルで実装し易そうであったこと、そしてgammoによって構築されたDOMツリーをtraverseするには必要十分なものであると考えたことが理由として挙げられる。
実装について
先に述べたように、XPathの仕様自体はさほど大きくはない。ましてや最新の仕様ではなく、XPath 1.0への追従を目指しているため、その実装に係るボリュームも小さなものとなっている。
詳細なXPath 1.0の文法はw3cによって定義されており、原則的にこの内容に沿った実装をすることによって、ASTを組み上げることができる。
gammoはnative extensionなどは使わずにPureなRubyによって実装されていることから、XPath 1.0についても同様のアプローチをとった。加えて、サードパーティ製のgemなどは使わずに、runtimeライブラリが標準添付となっているraccを用いて構文解析を行い、字句解析にはstrscanを採用することとした。
HTMLとの対比として、XPathは(E)BNFによって表現可能であり、W3Cの標準仕様でもEBNFによって構文が定義されている。この仕様に対応するのがGammo::XPath::Parserである。これによって構築したAbstract Syntax Treeを基に、XPathを用いてtraverseする際のcontext nodeとなる要素(XPathを実行する対象のrootとなる要素ノード)に対して、XPath ASTの各ノード(e.g. Path, Axes, Predicate, Function)を順番に評価していき、候補となる要素を検索・追加したり、あるいは濾し取っていく。これらのプロセスを経て、最終的に残ったノードの集合が、与えられたXPathの評価結果として返される。
Traverseの仕組み
gammoは原則的にXPath 1.0の仕様に倣って実装を行っているため、ここではXPathがどのように動作するのかについて触れることとする。
省略を加味しない場合、XPathは基本的に次のような構文で以てノード集合を構築する。
/軸::名前空間:ノードテスト[述語]/~
XPathにおいては、まず軸によって探索の方向を決定する。これはchild(子)や、ancestor(祖先)といった、現在のcontextノードから見た方向を意味する。そしてその方向に対して探索を開始し、候補となる要素群に対して、名前空間:ノードテストに指定された要素名や式によってその要素をフィルタしていくことで、集合を組み上げる。[述語]となっている部分については、上記の手順で組み上げた集合に対し、追加で複雑な式を用いてフィルタしていくことができる。
またXPathではURIのように、/でを区切り文字として、左から順番にHTML文書を追跡していくことも可能となっている。
これらを考慮して、例えば次のようなHTMLに対し、li要素のclass属性値にfooが指定されたもののみを取り出す。
doc = Gammo.new(<<-EOS).parse
<!DOCTYPE html>
<html>
<head>
<title>hello world</title>
<meta charset="utf8">
</head>
<body>
<ul>
<li class="foo">a</li>
<li class="bar">b</li>
<li class="foo">c</li>
<li class="bar">d</li>
<li class="foo">e</li>
</ul>
</body>
</html>
EOS
p doc.xpath('descendant-or-self::li[@class="foo"]').map(&:inner_text)
#=> ["a", "c", "e"]
関数について
筆者はこれを実装するまで存在を知らなかったが、XPathには関数という概念があるようだ。
文字列や数値・真偽値を扱う関数や、ノードの情報を扱う関数など、多くの関数が定義されている。
ここではその一例として、ある要素が特定の文字列をinner textとして持つかどうかを返す関数を紹介する。
doc = Gammo.new(<<-EOS).parse
<!DOCTYPE html>
<html>
<head>
<title>hello world</title>
<meta charset="utf8">
</head>
<body>
</body>
</html>
EOS
# contains関数を使い、title要素配下のテキストノードが
# `hello`という文字列を含むかどうかをテストする。
p doc.xpath('contains(//title/text(), "hel")', result_type: Gammo::XPath::BOOLEAN_TYPE) #=> true
このように、XPath式の中で関数を用いることも可能というわけである。
とはいえ、あまり個人的に使いたい場面がないため、対応も不十分なものとなっている。もしGammoやXPathの関数について興味があれば、対応表を見ながらパッチを送ってもらえると幸いである。
おわりに
この記事は最終日の記事のサブセットという位置付けで書かれたものだが、XPath 1.0の概要やRubyでの実装について、イメージを掴んでもらえれば幸いである。