XPathは正規表現のDOM版です。

JavaScript XPath DOM

正規表現といえば、

  • 文字列の検索や切り出しに大活躍。大量の規則や物量と格闘する際のバディ
  • プロトコルをRFC(BNF)を見てゴリゴリ書くひとにとっての福音
  • モダン言語に100%存在する機能(無いほうがおかしい)

なわけです。

JavaScriptで雅な表現(スケスケとかアニメとかAjax)をするには、ドキュメントツリーを多少なりとも操作する必要がありますが、
その前に、操作対象を何らかの方法で特定しなければなりません。

DOMによるノードの検索

DOMを使った従来の手法だと、

  • idから検索 document.getElementById()
  • タグから検索 document.getElementsByTagName()
  • CSSのクラスから検索 document.getElementsByClassName() - IE等では使えない
  • 親ノードの子供達から検索 Node.childNodes[]
  • 兄貴ノードを検索 Node.previousSibling
  • 妹ノードを検索 Node.nextSibling
  • ご先祖ノードを検索 Node.parentNode

これらを駆使して要素を特定するロジックを書く必要がありました。

XPathによるノードの検索

XPathは正規表現にも似た考え方で、ドキュメントツリーの検索性を向上する手法の一つです。

  • idから検索 document.evaluate('id("...")')
  • タグから検索 document.evaluate('.//div')
  • CSSのクラスから検索 document.evaluate('.//div[@class="..."]')
  • 親ノードの子供達から検索 XPathResult.snapshotLength, XPathResult.snapshotItem
  • 兄貴ノードを検索 document.evaluate('following-sibling::')
  • 妹ノードを検索 document.evaluate('preceding-sibling::')
  • ご先祖ノードを検索 document.evaluate('ancestor::')

今、使える技術なのか?

XPathは今使える技術です。

  • 互換性は?
  • 速度は?
    • 決め打ちで書いたDOMのロジックに、実行時スピードでは勝てないみたいだよ。
    • DOMをアセンブラとするとXPathは高級言語だけど、XPathがネイティブ実装されているFirefox,Opera,SafariではDOMよりも速いケースがあるよ。
      • 実行時のスピードも大事だけど、開発スピードはそれ以上に大事だよね。速度を稼ぎたいところは個別にDOMで書き直せばいいんだから。
  • 書いてて楽しい? それともつらい?
    • 知識体系を構築するまではつらい。でも、それは正規表現を学んだときと同じぐらいの辛さでしかなかったよ。
    • なれちゃえば楽しいよ。

実際に書いてみた

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>JavaScript::xpath.cheat test</title>
<!--[if IE]><script type="text/javascript" src="../../lib/xpath.js"></script><![endif]-->
<style type="text/css">body { background-color: black; color: white; }</style>
</head>
<body>

<div id="a">
  <div id="a_aa">
    <div id="a_aa_aaa">
    </div>
    <div id="a_aa_aab">
    </div>
    <div id="a_aa_aac">
      <p id="Hello">Hello</p>
    </div>
    <div id="a_aa_aad">
      <p id="world">XPath world!</p>
    </div>
    <div id="a_aa_aae">
    </div>
  </div>
</div>

<script type="text/javascript">
// --- Node extend ---
if (!window.Node) { // for IE
  var Node = window.Node = {
    ELEMENT_NODE:                 1,
    ATTRIBUTE_NODE:               2,
    TEXT_NODE:                    3,
    CDATA_SECTION_NODE:           4,
    ENTITY_REFERENCE_NODE:        5,
    ENTITY_NODE:                  6,
    PROCESSING_INSTRUCTION_NODE:  7,
    COMMENT_NODE:                 8,
    DOCUMENT_NODE:                9,
    DOCUMENT_TYPE_NODE:           10,
    DOCUMENT_FRAGMENT_NODE:       11,
    NOTATION_NODE:                12
  };
}

function perf(fn, n) {
  if (0) {
    alert(fn().toString());
  }
  var past = (new Date()).getTime();
  for (var i = 0; i < n; ++i) { fn(); }
  return (new Date()).getTime() - past;
}
function id(id) {
  return document.getElementById(id);
}
function xsnap1(expr, ctx) {
  return document.evaluate(expr, ctx, null,
                           XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
}
function countDownerNode(e) { // recursive
  var i = 0;
  e = e.firstChild;
  while (e) {
    if (e.nodeType === Node.ELEMENT_NODE) {
      if (e.hasChildNodes()) { i += countDownerNode(e); }
      ++i;
    }
    e = e.nextSibling;
  }
  return i;
}
function countUpperNode(e) {
  var i = 0;
  while (e && e.parentNode.nodeType === Node.ELEMENT_NODE) {
    e = e.parentNode;
    ++i;
  }
  return i;
}
function getElementNodePosition(e) {
  if (!e.parentNode) { return null; }
  var i = 0, j = 0, sz = e.parentNode.childNodes.length;
  for (; i < sz; ++i) {
    if (e === e.parentNode.childNodes[i]) { return j; }
    if (e.parentNode.childNodes[i].nodeType === Node.ELEMENT_NODE) { ++j; }
  }
  return null;
}
function prevElementNode(e) {
  do {
    e = e.previousSibling;
  } while (e && e.nodeType !== Node.ELEMENT_NODE);
  return e;
}
function nextElementNode(e) {
  do {
    e = e.nextSibling;
  } while (e && e.nodeType !== Node.ELEMENT_NODE);
  return e;
}
function enumElementNode(e) {
  var rv = [];
  while (e) {
    e = e.nextSibling;
    if (e && e.nodeType === Node.ELEMENT_NODE) { rv.push(e); }
  }
  return rv;
}
function enumLastElementNode(e) {
  var rv = [];
  while (e) {
    e = e.previousSibling;
    if (e && e.nodeType === Node.ELEMENT_NODE) { rv.push(e); }
  }
  return rv;
}

/** snippet1. child::の使用例, <div id="a-aa">以下の子ノードを検索し、先頭ノードのIDを取得する */
function snippet1_1() {
  var n = xsnap1("child::*", id("a_aa"));
  return [n.snapshotLength, n.snapshotItem(0).id]; // [5, "a-aa-aaa"]
}
function snippet1_2() {
  var n = xsnap1("./child::*", id("a_aa"));
  return [n.snapshotLength, n.snapshotItem(0).id]; // [5, "a-aa-aaa"]
}
function snippet1_3() {
  var n = document.evaluate('id("a_aa")/child::*[1]/@id', document, null,
                            XPathResult.STRING_TYPE, null);
  return [n.stringValue]; // ["a-aa-aaa"]
}
function snippet1_4() {
  var e = id("a_aa").firstChild;
  while (e && e.nodeType === 3) { e = e.nextSibling; }
  return [e ? e.id : null]; // ["a-aa-aaa"]
}

/** snippet2. descendant:: の使用例, <div id="a">以下の子孫ノードを検索しノード数を取得する */
function snippet2_1() {
  var n = document.evaluate("count(descendant::*)", id("a"), null,
                            XPathResult.ANY_TYPE, null);
  return [n.numberValue]; // [8]
}
function snippet2_2() {
  var n = countDownerNode(id("a"));
  return [n]; // [8]
}
function snippet2_3() {
  var n = id("a").getElementsByTagName("*");
  return [n.length]; // [8]
}
function snippet2_4() {
  var n = document.evaluate('count(id("a")/descendant::*)', document, null,
                            XPathResult.ANY_TYPE, null);
  return [n.numberValue]; // [8]
}

/** snippet3. parent:: の使用例, <div id="a_aa">の親ノードのIDを取得する */
function snippet3_1() {
  var n = document.evaluate("parent::node()/@id", id("a_aa"), null,
                            XPathResult.STRING_TYPE, null);
  return [n.stringValue]; // ["a"]
}
function snippet3_2() {
  var n = document.evaluate("../@id", id("a_aa"), null,
                            XPathResult.STRING_TYPE, null);
  return [n.stringValue]; // ["a"]
}
function snippet3_3() {
  var n = id("a_aa").parentNode;
  return [n.id]; // ["a"]
}

/** snippet4. ancestor:: の使用例, <div id="a_aa_aad">の祖先ノードを検索し階層数を取得する */
function snippet4_1() {
  var n = document.evaluate("ancestor::*", id("a_aa_aad"), null,
                            XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
  return [n.snapshotLength]; // [4] = [<html>, <body>, <div id="a">, <div id="a_aa">]
}
function snippet4_2() {
  var n = countUpperNode(id("a_aa_aad"));
  return [n]; // [4]
}

/** snippet5. following-sibling:: の使用例, <div id="a_aa_aac">の後ろにある兄弟ノードの2番目のノードのIDを取得する */
function snippet5_1() {
  var n = document.evaluate("following-sibling::*[2]/@id", id("a_aa_aac"), null,
                            XPathResult.STRING_TYPE, null);
  return [n.stringValue]; // ["a_aa_aae"]
}
function snippet5_2() {
  var n = nextElementNode(nextElementNode(id("a_aa_aac")));
  return [n.id]; // ["a_aa_aae"]
}
function snippet5_3() {
  var n = enumElementNode(id("a_aa_aac"))[1];
  return [n.id]; // ["a_aa_aae"]
}

/** snippet6. preceding-sibling:: の使用例, <div id="a_aa_aac">が親ノードの何番目の子供かを取得する */
function snippet6_1() {
  var n = document.evaluate("preceding-sibling::*", id("a_aa_aac"), null,
                            XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
  return [n.snapshotLength]; // [2]
}
function snippet6_2() {
  var n = getElementNodePosition(id("a_aa_aac"));
  return [n]; // [2]
}
function snippet6_3() {
  var n = enumLastElementNode(id("a_aa_aac"));
  return [n.length]; // [2]
}

function test() {
  var loop = 2000;
  var rv = [
    // child::
    "snippet1_1(XPath)=" + perf(snippet1_1, loop),
    "snippet1_2(XPath)=" + perf(snippet1_2, loop),
    "snippet1_3(XPath)=" + perf(snippet1_3, loop),
    "snippet1_4(DOM  )=" + perf(snippet1_4, loop),
    // descendant::
    "snippet2_1(XPath)=" + perf(snippet2_1, loop),
    "snippet2_2(DOM  )=" + perf(snippet2_2, loop),
    "snippet2_3(DOM  )=" + perf(snippet2_3, loop),
    // parent::
    "snippet3_1(XPath)=" + perf(snippet3_1, loop),
    "snippet3_2(XPath)=" + perf(snippet3_2, loop),
    "snippet3_3(DOM  )=" + perf(snippet3_3, loop),
    // ancestor::
    "snippet4_1(XPath)=" + perf(snippet4_1, loop),
    "snippet4_2(DOM  )=" + perf(snippet4_2, loop),
    // following-sibling::
    "snippet5_1(XPath)=" + perf(snippet5_1, loop),
    "snippet5_2(DOM  )=" + perf(snippet5_2, loop),
    "snippet5_3(DOM  )=" + perf(snippet5_3, loop),
    // preceding-sibling::
    "snippet6_1(XPath)=" + perf(snippet6_1, loop),
    "snippet6_2(DOM  )=" + perf(snippet6_2, loop),
    "snippet6_3(DOM  )=" + perf(snippet6_3, loop),
  ];
  alert(rv.join(",\r\n"));
}
window.onload = function() {
  setTimeout(test, 1000);
}
</script>

</body>
</html>

速度比較


child:: IE8.0 FF2.0 FF3.0 Op9.2 Op9.5 Sa3.1
snippet1_1(XPath) 1123 172 74 265 171 31
snippet1_2(XPath) 1357 156 82 297 187 47
snippet1_3(XPath) 2090 140 98 281 188 62
snippet1_4(DOM ) 47 94 28 31 15 0
descendant:: IE8.0 FF2.0 FF3.0 Op9.2 Op9.5 Sa3.1
snippet2_1(XPath) 1810 140 74 265 172 31
snippet2_2(DOM ) 327 453 157 94 92 62
snippet2_3(DOM ) 63 78 18 46 16 0
snippet2_4(XPath) 2106 109 85 281 187 47
parent:: IE8.0 FF2.0 FF3.0 Op9.2 Op9.5 Sa3.1
snippet3_1(XPath) 1228 157 86 265 172 31
snippet3_2(XPath) 1084 141 84 281 187 47
snippet3_3(DOM ) 45 61 18 15 16 0
ancestor:: IE8.0 FF2.0 FF3.0 Op9.2 Op9.5 Sa3.1
snippet4_1(XPath) 1595 110 86 281 171 31
snippet4_2(DOM ) 146 201 61 31 32 16
following-sibling:: IE8.0 FF2.0 FF3.0 Op9.2 Op9.5 Sa3.1
snippet5_1(XPath) 1606 156 91 281 187 47
snippet5_2(DOM ) 78 140 43 47 31 16
snippet5_3(DOM ) 94 187 58 31 31 15
preceding-sibling:: IE8.0 FF2.0 FF3.0 Op9.2 Op9.5 Sa3.1
snippet6_1(XPath) 1154 109 68 281 172 31
snippet6_2(DOM ) 203 453 172 62 46 78
snippet6_3(DOM ) 93 171 53 31 32 16
  • IE8.0 (IE8β)
  • FF2.0 (Firefox2.0.0.14)
  • FF3.0 (Firefox3β5)
  • Op9.2 (Opera9.27)
  • Op9.5 (Opera9.5β)
  • Sa3.1 (Safari3.1.1)
  • 単位はms

反省会

  • descendantのsnippet2_2(DOM)が重過ぎるのでsnippet2_3(DOM)を作成したんだけど、getElementsByTagName() を使うって発想がなかなか出てこなかった。
    • getElementsByTagName()で速度を稼げるケースって結構ありそう。
  • それにしてもSafariの性能が桁違い。
    • IE6とかIE7はいらない子。
      • でもIE8のDeveloper Toolsはやればできる子。
  • 今回のテスト用に、VistaなノートPCを用意して、各ブラウザをクリーンインストール(おおげさ)。
    • 途中で開発用の別PCのFirefoxのプロファイルやらブックマークを消しちゃって、軽くパニック。
  • JavaScript-XPathとネイティブ実装のグラフは、視点がおかしいよね?
    • 確かに。やっちゃったから載せたけど本来こういうノイズは控えめにすべき。反省。

参考リンク

2008-04-21 追記:
snippet2_4() を追加しました。
2_1: evaluate("count(descendant::*)", id("a")); と、2_4: evaluate('count(id("a")/descendant::*)', document); は同じ結果になりますが、contextを指定している2_1は、2_4よりちょっぴり速いです。