ものすごく久しぶりにXPathを使おうと思ったのですが、「XPathってなんだっけ？」という程度に忘れています。
細部はリファレンスマニュアルを調べれば分かることなので、概念的にどんなものかを思い出すのが先。概念や構造を手っ取り早く理解するには、抽象化したほうが都合がいいです。抽象化すると本質がコンパクトにまとまるので忘れにくいし、忘れても思い出す手間も少ないですからね。
内容：
- 続きの記事：XPathの構文を割と具体的にまとめておく
ツリー、有向グラフ、ノードセット
XPathが相手にするデータ構造はツリーです。XMLのツリーには属性ノード、名前空間ノードとかもあるので、ノードにも辺にもいろいろな値（ラベル）が付着している有向グラフと考えましょう。ルートが特定されていてサイクルがない、という意味では確かにツリーなんですが、ノードも辺もそれぞれの特性を持つので、単なる形状としてのツリーじゃありません。
一般に、Gを“ノード・辺に値をくっ付けた有向グラフ”とします。そして、|G|はグラフGのノード集合とします。|G|の部分集合をノードセットと呼びましょう。ただし、S⊆|G| をGから切り離して考えるわけではないので、ノードセットを (G, S) （S⊆|G|）のように書いたほうがいいかもしれません、めんどうだから、単にSと書きますけどね。「ノードセット」はXPathで使っている用語です。
全順序付きノードセット
ノードセットはセット（集合）なので、ノードの順序は考えないことになっています。しかし、多くのケースで順序、しかも全順序（total order、線形順序とも呼ぶ）を想定しています。実際に、ノードセットに全順序が存在しないと出来ない操作があります。
XPathの仕様も利用者も、順序構造を持たないノードセットと全順序付きノードセットをあまり区別しないようですが、僕はこれを曖昧にするのは気持ち悪くて仕方ありません。全順序を持つときは、必ず全順序付きノードセットと言うことにします。
AとBがグラフG（もちろんツリーでもよい）のノードセットのとき、集合としての合併 A∪B は無条件に定義できます。しかし、AとBが全順序付きノードセットのときは、A∪B 上に適切な全順序を定義できるかどうかは明らかではありません。仮に定義できたとしても、全順序構造まで含めて考えると、A∪B = B∪A は成立しません。
XPathではしばしば、ノードセットを合併（統合、集約）する操作が出てきますが、全順序付きノードセットの合併には注意が必要です。A∪B 上に合理的な全順序構造が定義できる条件は次のとおり。
- Aの全順序をA∩B上に制限したものと、Bの全順序をA∩B上に制限したものが一致する。
実際に使う合併では、この条件が満たされているのですが、条件のチェックをしなくていいわけじゃないです。
軸
XPathの「軸」とは、グラフGのノードx（x∈|G|）に対して、|G|の部分集合を対応付ける関数です。ただし、いくつかの注意点があります。
Pow(X)は集合Xのべき集合を表すとして、aが軸であるとき、aを |G|→Pow(|G|) という関数だと思ってよいでしょうか？ x∈|G| を、もとのグラフGの構造から切り離して考えると、軸aの値（ノードセット）をうまく計算できません、一部の計算手段がなくなります。「グラフのノード」と言ったときは、離散的な（無構造な）集合|G|の要素xと考えるのではなくて、(G, x) のような組と理解したほうがよいでしょう。軸aも、(G, x)|→a((G, x)) という対応です。でも、a((G, x)) と書くのは欝陶しいので a(x) （x∈|G|）と略記することにします。
x∈|G| に対する a(x) はノードセットですが、さらに全順序（線形順序）が入ります。つまり、a(x) は、グラフGのノードセットSに加えて、S上の順序≦も指定することになります。そうです、Sを台（underlying set）とする全順序付きノードセットなのです。この点を強調するには、a(x) = (S, ≦) とでも書けばいいでしょうか。実際のXPathでは、全順序を指定するために、基数nの有限集合Sと{1, 2, ..., n}との双射を指定しています。この双射は、ようするに番号付けです。番号の大小がそのまま順序となっています。
コンテキスト
XPathでは、「コンテキスト」という言葉が3つくらいの意味で使われています。これは混乱を招きそうです。
- 変数名と値の束縛、関数名とその定義との束縛などを含む、評価環境全体のこと。
- 評価環境の一部となる全順序付きノードセット
- 全順序付きノードセットのなかの特定のノード
ここでは、単に「コンテキスト」と言ったら“全順序付きノードセットと特定されたノードの組”のことだとします。全順序付きノードセットを（全順序があることを前提として）コンテキストノードセット、特定されたノードをコンテキストノードと呼びます*1。コンテキストノードセットの基数をコンテキストサイズ、コンテキストノードセットがもつ全順序におけるコンテキストノードの順番（1からはじまる順序数）をコンテキストポジションと呼んだりします。
以上のような概念・用語は、コンテキストノードセットが全順序を備えていることを想定しないとまったく解釈・理解できません。
コンテキストノードセットCと、Cに含まれるノードxの組 (C, x) が、XPath式の評価環境（の一部）となります。背後には、もちろんグラフG全体が控えています。ここで大事なことは、x, y∈C として、(C, x) と (C, y) はコンテキストとしては異なることです（x≠yを仮定している）。コンテキストサイズ（コンテキストノードセットCの基数）がnなら、(C, x)という組はn個作れるので、ひとつのコンテキストノードセットCから異なるn個のコンテキストが作れます。
ステップ
XPathのステップ（ロケーションステップ）は、軸とノードテストと述語（predicate）からなります。ステップは、コンテキストに対して評価されます。ほとんどの場面でコンテキストノードセットは使われず、コンテキストノードだけで計算ができますが、述語（predicate）の評価のときに、コンテキストノードセット内の順序（position）が使われます。
与えられたコンテキストを (C, x) とします。ステップの軸がaなら、a(x) は全順序付きノードセットです。ノードテストと述語は、a(x) の部分ノードセットを選び出すために使われます。ステップ全体としては、コンテキスト (C, x) から新しい全順序付きノードセットRを作り出す働きを持ちます。
ノードテストと述語は、どちらもノードに関する条件式（condition expression）です。これは、適当な論理系（logical system）の論理言語です。原子論理式と関係演算子から作られた論理式（formula）がノードテストや述語なのです。（XPathの「述語」という言葉の使い型は論理とは異なっていますから要注意。）ノードテストと述語は、コンテキスト (C, x) に対して真偽のいずれかに評価されます。
コンテキスト (C, x) に対するステップの評価は次のように行われます。
- ステップの軸がaだとして、全順序付きノードセット a(x) を求める。a(x) をSと置く。
- y∈S に対して、コンテキスト (S, y) を作り、条件式（ノードテストと述語）を評価する。
- 条件式の値が真であったノードを集めて結果とする。
結果は、Sの部分集合Rと、Sから引き継いだR上の全順序構造です。
ロケーションパスの評価
ロケーションパスは、ステップの並びです。コンテキスト (C, x) に対してロケーションパスを評価した結果は全順序付きノードセットRとなります。次の手順でRを求めます。
- コンテキスト(C, x)に対して最初のステップを評価する。その結果をR1とする。
- y∈R1ごとに、(R1, y) という全順序付きノードセットセットを作る。
- すべての (R1, y) に対して2番目のステップを評価して、その結果を R2, yとする。
- R2, y をすべてのyに渡って合併した全順序付きノードセットをR2とする。
- ステップがある限り以上の手順を繰り返して、最後に得られた全順序付きノードセットをパスの評価結果とする。
「すべてのyに渡って合併」のときに、「ある順番で並べられた全順序付きノードセットの合併」が可能かどうかが問われます。結論を言えば「可能」ですが、条件をチェックしないとwell-definedの保証はできません。
以上のような「概念的にどんなものか」が分かれば、あとは構文を調べながらなんとか使えるでしょ。
