HTML 用の XPath 機能テストを書いた
僕のパーサブームはまだまだ終わらない
すばらしいエントリが上がっています。
で、最近 XPath 処理系の実装が停滞してるんですけど。
飽きたんじゃなくて、Shibuya.JS と WEB+DB PRESS の〆が終わるまで待って＞＜！！
Firebug で XPath を簡単に試す方法
適当に XPath を試したい時に
以下のようにすれば、簡単に XPath をためせます。
document.evaluate( '//div[@class="hoge"]', // XPath 式 document, // 基準となるノード（要素とか null, // 名前空間の解決方法（適当にやるときは null 6, // 取得する形式の指定（適当にやるときは 6 null // 結果を再利用するかどうか（適当にやるときは null );
簡単ですね。
document.evaluate、式、ドキュメント、ヌル、６、ヌル。
覚えましたか？
というわけで、以下のブックマークレットを実行してあげてください。
javascript:void(XPathResult.prototype.__defineGetter__('length',function(){var l=this.snapshotLength;for (var i=0;i<l;i++)with({i:i})this.__defineGetter__(i,function(){ return this.snapshotItem(i)});return l;}));
えい！
で、 Firebug で XPaht を試す
おおおお！便利ー。
このブックマークレットでは以下のようなことをやってます。
Firebug では length プロパティが数値を持って存在していると、自動で配列っぽい扱いをしてくれます。
XPathResult.prototype.__defineGetter__('length', function() { var length = this.snapshotLength; for (var i = 0; i < length; i ++) with({i:i}) this.__defineGetter__(i, function(){ return this.snapshotItem(i) }); return length; });
ノードの集合を「ドキュメント順」に高速に並べ替える。その１
XPath ではこの「ドキュメント順」という概念がよく登場する。
たとえば、ノードを文字列化するときは子孫テキストノードを「ドキュメント順」に文字列として連結しなければならない。とかとか
でも、このドキュメント順へのソート
考えただけでもめちゃめちゃ重そうだ・・・。
いろいろ考えてみた。
で、今回は DOM アクセスをキャッシュしながらノードを比較する関数を作る
汎用的に作ったので XPath 目的以外でも使えます。
var order = function(node1, node2) { var wrapper1 = new order.wrapper(node1); var wrapper2 = new order.wrapper(node2); if (wrapper1 == wrapper2) return 0; var ancestors1 = [wrapper1]; while (wrapper1 = wrapper1.parent()) { if (wrapper1 == wrapper2) return 1; ancestors1.push(wrapper1); } var prev2; while (wrapper2 = (prev2 = wrapper2).parent()) { for (var i = 0; i < ancestors1.length; i ++) { if (wrapper1 == ancestors1[i]) { wrapper2 = ancestors1[i - 1]; if (!prev2) return -1; wrapper1 = prev2; while(wrapper1 = wrapper1.next()) if (wrapper1 == wrapper2) return -1 return 1 } } } return -1; }; order.id = 0; order.wrapper = function(node) { var wrapper = node.__order__; if (wrapper && wrapper._id === order.id) return wrapper; this._id = order.id; this._node = node; node.__order__ = this; }; order.wrapper.prototype = { next: function() { var next = ('_next' in this) ? this._next : (this._next = this._node.nextSibling); return next ? new order.wrapper(next) : null; }, parent: function() { var parent = ('_parent' in this) ? this._parent : (this._parent = this._node.parentNode); return parent ? new order.wrapper(parent) : null; } };
使い方
以下のような HTML で
<div id="id1"> <div id="id2"> <div id="id3"></div> </div> <div id="id4"></div> </div>
以下のようになる。
var $ = function(id) { return document.getElementById(id) }; alert(order($('id1'), $('id2'))); // -1 alert(order($('id3'), $('id3'))); // 0 alert(order($('id4'), $('id1'))); // 1
たとえば、配列相手なら
[$('id4'), $('id2'), $('id1'), $('id3'), $('id2')].sort(order); // order 関数を sort 関数に引数で渡してやる
こうすると以下のように「ドキュメント順」に並び変わる。
この時、DOM プロパティアクセスのキャッシュによって parentNode と nextSibling へのアクセスは各要素一回ずつしか行われない。その他の DOM プロパティアクセスはない。
ドキュメントを変更した場合は以下のようにすると、キャッシュを破棄できる。
order.id++; // id を変える
たとえば、
XPath の評価中はデータをキャッシュして、終わったら id をインクリメントしてやればいいことになる。
よし、次は
ノードの集合をリストで持つのと木構造で持つのとパフォーマンスがどのくらい変わるかを実験したい＞＜
XPath のパーサ書いた
ふー。XPath パーサが出来ましたよ＞＜
わーい。
昨日中に作ろうとは思っていたけど＞＜
もうすぐ朝の 6:00 か。
もう 18 時間くらいはずっとコード書いてたんだなあ。集中してて時間が過ぎるのが一瞬だったよ。
XPath パーサのデモ
http://amachang.art-code.org/xpathparser/
このデモでは、テキストボックスに書かれた XPath を動的に解析していきます。
実際に XPath を書き足していくと「うにょうにょ」構文木が構築されていく様子が分かります。
ちょっとおもしろいです。
注意
とりあえず、実装することだけを目標に書いたので、高速化や最適化やリファクタリングなどは一切やっていません。
あと、
パーサを作りながら、いろいろ勉強になって、いろんなことブログにも書きたいんだけど＞＜
でも、今日はもうヘロヘロ＆手がプルプル＆明日拡張勉強会なので、また今度まとめたいと思います。
忘れそうだあああ。
さあさあ、次は
いよいよ。処理系だ！！
でも、 Shibuya.JS とか、連載の〆とかが近いので伸び伸びになるのかなああ。
あああああああ。
ああああああああああ。さ。帰って仮眠とろう＞＜
せっかくの金曜と土曜を何してんだろうなあ＞＜
ひいいいい
正規表現の XPath 字句解析その２
またまた
XPath ネタです。
先日、XPath の字句解析をワンライナーで作ってみた。 - IT戦記で書いた正規表現の XPath 字句解析ですが、よく考えるといろいろおかしかった（不正な文字が無視されたりする）＆ id:otsune さんからコメントやブクマの突っ込みもありまして、１から正規表現を勉強してから新しく書き直すことにしました。
正規表現の勉強方法
以下の二つの方法で勉強しました。
1.SpiderMonkey の正規表現デバッグオプションを使う
SpiderMonkey をビルドするときに、以下のフラグを付けてビルドします。
$ make -f Makefile.ref "DEFINES=-DREGEXP_DEBUG -DDEBUG"
こうすると正規表現がどういう風に実行されたかを調べることができます。
こんな感じ
$ js js> 'foobar'.match(/o+/); 000001: plus 000004: flat1 'o' == 'f' 000001: plus 000004: flat1 'o' == 'o' * 000006: endchild 000001: repeat 000004: flat1 'o' == 'o' * BT_Push: 0,0 000004: flat1 'o' == 'b' 000007: end oo js>
JavaScript で XPath の構文木を考えてみる。
またまた
パーサーブームの続編です。
昨日は数式のパーサーを作って、帰り道にいろいろ考えたんですけど、普通の言語で考えると構文木って結構複雑になるんじゃないかなあって思いました。
で、横断歩道で明日 XPath の構文木を考えてみようと思ったわけです。
では、仕様と見比べながら XPath の構文木の構造を考えてみましょう。
仕様読むの大嫌いなんですけど、がんばります。
仕様のリンク
まず、冒頭に
The primary syntactic construct in XPath is the expression. An expression matches the production Expr.
http://www.w3.org/TR/xpath#section-Introduction
とあるので、 XPath 全体は Expr であることが分かります。
では、 Expr を見てみましょう。
Expr
[14] Expr ::= OrExpr
[21] OrExpr ::= AndExpr
| OrExpr 'or' AndExpr
[22] AndExpr ::= EqualityExpr
| AndExpr 'and' EqualityExpr
[23] EqualityExpr ::= RelationalExpr
| EqualityExpr '=' RelationalExpr
| EqualityExpr '!=' RelationalExpr
[24] RelationalExpr ::= AdditiveExpr
| RelationalExpr '<' AdditiveExpr
| RelationalExpr '>' AdditiveExpr
| RelationalExpr '<=' AdditiveExpr
| RelationalExpr '>=' AdditiveExpr
[25] AdditiveExpr ::= MultiplicativeExpr
| AdditiveExpr '+' MultiplicativeExpr
| AdditiveExpr '-' MultiplicativeExpr
[26] MultiplicativeExpr ::= UnaryExpr
| MultiplicativeExpr MultiplyOperator UnaryExpr
| MultiplicativeExpr 'div' UnaryExpr
| MultiplicativeExpr 'mod' UnaryExpr
http://www.w3.org/TR/xpath#NT-Expr
となっています。
なんだか、難しそうですが、よくよく見るとただの二項演算の数式にしかすぎません。
なので、構文木はJavaScript で数式パーサを書いてみた。 - IT戦記で書いたような演算子を分岐点とした UnaryExpr の木になることが分かります。
で、部分木を↓こんな感じのクラスで表現してみた。(JavaScript ではクラスを関数で表現します。)
var BinaryExpr = function(operator, left, right) { this.op = op; this.left = left; this.right = right; };
op を分岐点とした left right の枝を持つ部分木を表現しています。
じゃあ、次は UnaryExpr を見てましょう。
UnaryExpr
[27] UnaryExpr ::= UnionExpr | '-' UnaryExprhttp://www.w3.org/TR/xpath#NT-UnaryExpr
となっています。
これは簡単ですね。- (マイナス)が分岐点で UnaryExpr が枝です。 XPath には + (プラス)の単項演算子がないんですね。
というわけで、この部分木を↓こういうクラスで表現します。
var UnaryExpr = function(op, expr) { this.op = op; this.expr = expr; };
op は - (マイナス)演算子しかありえないんですが、一応データとして持つことにしました。
では、次に UnionExpr を見てみましょう。
UnionExpr
[18] UnionExpr ::= PathExpr | UnionExpr '|' PathExprhttp://www.w3.org/TR/xpath#NT-UnionExpr
| （パイプ）演算子で区切られた PathExpr を表しています。| (パイプ)演算子はその性質から結合順は左右どちらでもいいと思われます（書いてない？）。
UnionExpr では一つの演算子しかないため、複雑な数式のパースを行わず可変数の PathExpr (枝)を持つ部分木として扱います。
で、↓このようなクラスにしてみました。
var UnionExpr = function() { this.paths = []; }; UnionExpr.prototype.path = function(path) { this.paths.push(path); };
次は PathExpr です。
PathExpr
[19] PathExpr ::= LocationPath
| FilterExpr
| FilterExpr '/' RelativeLocationPath
| FilterExpr '//' RelativeLocationPath
[1] LocationPath ::= RelativeLocationPath
| AbsoluteLocationPath
[2] AbsoluteLocationPath ::= '/' RelativeLocationPath?
| AbbreviatedAbsoluteLocationPath
[3] RelativeLocationPath ::= Step
| RelativeLocationPath '/' Step
| AbbreviatedRelativeLocationPath
[10] AbbreviatedAbsoluteLocationPath ::= '//' RelativeLocationPath
[11] AbbreviatedRelativeLocationPath ::= RelativeLocationPath '//' Step
http://www.w3.org/TR/xpath#NT-PathExpr
これも、いろいろややこしく書いてありますが、実はとても簡単です。
要は Step が // か / によって区切られていて、最初に FilterExpr を持っている場合があったり、先頭に // や / を持つものがあるというだけです。
これを↓のようなクラスで表します。
var PathExpr = function(filter) { this.filter = filter; this.steps = []; }; PathExpr.prototype.step = function(op, step) { this.steps.push([op, step]); };
op は (// か / を表します。)と step は基本的にセットで考えて、先頭 step の例外は内部的に特殊な FilterExpr を生成して対応します。
ちなみに、 // は /descendant-or-self::node()/ の省略系だと定義してありますが、別々として扱った方が処理系を書くときに楽な気がした（getElementsByTagName とかあるから）ので別ものとして扱っています。
次は、 FilterExpr です。
FilterExpr
[20] FilterExpr ::= PrimaryExpr | FilterExpr Predicate
[15] PrimaryExpr ::= VariableReference
| '(' Expr ')'
| Literal
| <a class="okeyword" href="g:javascript:keyword:Number">Number</a>
| FunctionCall
http://www.w3.org/TR/xpath#NT-FilterExpr
これは、 FilterExpr は PrimaryExpr のあとに Predicate がいくつも続くという意味です。
PrimaryExpr は VariableReference か Expr か Literal か Number か FunctionCall になります。
ですので、↓のようなクラスで表します。
var FilterExpr = function(primary) { this.primary = primary; this.predicates = []; }; FilterExpr.prototype.predicate = function(predicate) { this.predicates.push(predicate); };
次は、 Step です。
Step
[4] Step ::= AxisSpecifier NodeTest Predicate*
| AbbreviatedStep
[5] AxisSpecifier ::= AxisName '::'
| AbbreviatedAxisSpecifier
[6] AxisName ::= 'ancestor'
| 'ancestor-or-self'
| 'attribute'
| 'child'
| 'descendant'
| 'descendant-or-self'
| 'following'
| 'following-sibling'
| 'namespace'
| 'parent'
| 'preceding'
| 'preceding-sibling'
| 'self'
[7] NodeTest ::= NameTest
| NodeType '(' ')'
| 'processing-instruction' '(' Literal ')'
[12] AbbreviatedStep ::= '.' | '..'
[13] AbbreviatedAxisSpecifier ::= '@'?
http://www.w3.org/TR/xpath#NT-Step
これもかなり複雑に見えますが、 AxisSpecifier と NodeTest を一つ持っていて Predicate を複数持っているにすぎません。
AxisSpecifier は特定の AxisName と AbbreviatedAxisSpecifier しかないので、この部分木に含めてしまいます。
NodeTest は processing-instruction が NodeType だとすると、 NodeType と NameTest の二種類に分けられます。これらのうちのどちらかをこの部分木に持つことになります。
そして、 Predicate は FilterExpr と同様に複数持っています。
これをクラスで書くと↓こうなります。
var Step = function(axis, test) { this.axis = axis; this.test = test; this.predicates = []; }; Step.prototype.predicate = function(predicate) { this.predicates.push(predicate); };
次は Predicate です。
Predicate
[8] Predicate ::= '[' PredicateExpr ']' [9] PredicateExpr ::= Exprhttp://www.w3.org/TR/xpath#NT-Predicate
Predicate は Expr しか持たない部分木なので Predicate は BinaryExpr クラスを用いて表すことにします。
次は、 NodeType です。
NodeType
[38] NodeType ::= 'comment' | 'text' | 'processing-instruction' | 'node'http://www.w3.org/TR/xpath#NT-NodeType
NodeType は Step の項で言ったように名前付きの processing-instruction も含めて考えているので、木には NodeType の名前と processing-instruction だった場合の Literal が含まれます。
クラスは↓こんな感じ
var NodeType = function(type, literal) { this.type = type; this.literal = literal; };
次は NameTest です。
NameTest
[37] NameTest ::= '*' | NCName ':' '*' | QNamehttp://www.w3.org/TR/xpath#NT-NameTest
ここでは、 NameTest の名前だけを保存しています。 QName は Prefix と NCName に分けられるのですが、悩んだ末、木にはそのまま QName で保存することにしました。
↓こんな感じ。
var NameTest = function(name) { this.name = name; };
次は VariableReference
VariableReference
[36] VariableReference ::= '$' QNamehttp://www.w3.org/TR/xpath#NT-VariableReference
これも変数名 QName は Prefix と NCName に分けずにそのまま保存します。
↓こんな感じ
var VariableRefernce = function(name) { this.name = name; };
次は、 Literal です。
Literal
[29] Literal ::= '"' [^"]* '"' | "'" [^']* "'"http://www.w3.org/TR/xpath#NT-Literal
Literal は文字列を表現しているので、そのデータを木に保存します。
↓こんな感じ
var Literal = function(text) { this.text = text; };
次は、 Number です。
Number
[30] Number ::= Digits ('.' Digits?)? | '.' Digits
[31] Digits ::= [0-9]+
http://www.w3.org/TR/xpath#NT-Number
Number は数値を表現しているので、そのデータを木に保存します。
↓こんな感じ
var _Number = function(digit) { this.digit = +digit; };
次は、 FunctionCall です。
FunctionCall
[16] FunctionCall ::= FunctionName '(' ( Argument ( ',' Argument )* )? ')'
[17] Argument ::= Expr
[35] FunctionName ::= QName - NodeType
http://www.w3.org/TR/xpath#NT-FunctionCall
Function は関数名と複数の Argument で出来てると分かります。 Argument は Expr なので BinaryExpr クラスを使います。
↓こんな感じ
var FunctionCall = function(name) { this.name = name; this.arguments = []; }; FunctionCall.prototype.argument = function(argument) { this.arguments.push(argument); };
全部終了！
ふー疲れた＞＜
これで、全部の構文の部分木の構造を定義したかなあ＞＜
まとめ
こうやって全部の構文を見てみて、 XPath って実装の簡単さを考えて作られてるんだなあと分かりました！スバラシス
っていうか、処理系作る時ってこんなやり方でいいのかなあ＞＜
もう、やってみないと分かりません＞＜
がんばります＞＜
