ものがたり(旧)

atsushieno.hatenablog.com に続く

derivativeアルゴリズムについて(1)

冬休みに入ってからしばらくはRELAX NGまわりをいじり直していた。まず長いこと懸念していたバグ潰しがようやく実行に移せた。そして直ったと思ったら、今度はパフォーマンスに（relaxng.rngを解析できないほどの）致命的な問題が生じて、最適化をいくつか実装する必要があった。結論から言えばwhitespaceの扱いがおかしかっただけなのだけど。そして今日、ようやく3年前にやっつけたwhitespaceまわりの問題を全て解消した（はず）。

僕の知る限り、現時点でバグの原因は3種類だけだ: 1) XLink section 5.4の制約が未実装であること、2) XML Schema datatypesのfacetが上手く機能していない（場合がある?）こと、3) exceptを子にもつname classをexceptにもつname classのanalysisに失敗すること。

というわけで、今日から何回か、RELAX NGの策定者James Clarkがまとめたderivativeアルゴリズムについて、書ける範囲で書いてみよう。（今頃になってこんなものを書いているのは、単純な話、これまではこのderivativeアルゴリズムについてきちんと理解しているという自信がまるでなかったからだ。）

Why this doc?

RELAX NG実装を作成するには、このアルゴリズムに基づいてコードを書けば、ほぼ間違いないし、このアルゴリズムは半ばHaskellコードによる実装そのものなので、実際には自分が実装しているという感覚すらないかもしれない。ただし、普通のプログラマーにとって、自分が書いているコードの意味が分からないというのはコワい話だし、これから書こうという初心者の人*1にとっては、このderivativeアルゴリズムというのは、一体何の魔法ですか?という状態だろう。

RELAX NGは数学的モデルに基づいている、と言われると、つい身構えてしまうが、そんなに難しく考える必要は無い。と思う。*2

Haskell?

derivativeアルゴリズムはHaskellで書かれているので、Haskellが読めないと読むことは出来ないけど、使われている記法さえ理解できれば簡単だ。具体的にはこんな感じか:



funcname :: arg1type -> arg2type ... -> argNtype -> return_value
funcname arg1 arg2 = return_value_expression
funcname _ _ = default_return_value_expression

引数と戻り値の両方を -> で表現しているのが特徴であろう。最初の行が関数の型の定義で、それ以降は「こういう引数が来たら、こういう値を返す」という定義のリストになっている。最後のものは、「その他の場合」に返す値を表している（'_'は任意の値という意味）。

Haskellでは、関数がオブジェクトで渡される。これは、delegateにでも置き換えて考えることもできる（ソースは汚らしくなるけど）。James ClarkのJingでは、関数を表現するクラス（たとえばcom.thaiopensource.relaxng.impl.StartTagOpenDerivFunction）が実装されている。僕は面倒がってdelegateですませた。ただし、delegateですませてしまうと、flip（たぶんHaskell独自のものだと思う）というかderivativeアルゴリズムで定義されるapplyAfter関数が多少面倒になる。僕はflipについては独自のクラス定義を余儀なくされてしまった（つまり余計なインスタンス生成が発生していることになる）。*3

引数 '_' には、その引数の型のクラスでvirtualメソッドとして定義してしまえば良い（それが無理でも、最終的には、関数はどれもstaticとしてインスタンス外に定義できる）。たとえば



textDeriv :: Context -> Pattern -> String -> Pattern
textDeriv _ _ _ = NotAllowed

こんなのは、PatternのクラスにtextDeriv()のvirtual実装を書けばよい。Javaで書くなら、その宣言はこんな感じだ:



public Pattern textDeriv(

  Context ctx, Pattern p, String text)

{

  return NotAllowed.Instance;

}

そもそもJingもJavaで実装されているのだから、derivativeで使われているHaskellは、Haskell以外の言語で実装されることを想定した、シンプルなものであるはずだ。

BlahBlahDeriv関数

derivativeアルゴリズムには、ナントカDerivという関数がいくつか存在するが、これらがvalidationのコアとなる。validationは、document element（XMLのdocument fragmentであれば、それぞれのchild node）に対して、childDerivを適用する、というかたちで行われる。childDerivでは、テキストノードにはtextDerivが適用され、要素ノードには、以下のderivative関数が順次適用される:

  • startTagOpenDeriv
  • attsDeriv
  • startTagCloseDeriv
  • childrenDeriv
  • endTagDeriv

SAXの場合、startElement()で最初の3つが処理され、endElement()でendTagDerivが呼び出される。childrenDerivは直接には処理されない。というのも、これは子孫ノードを含む完全なinfosetが存在することを前提に記述されている関数なので、SAXのようなストリーミングプロセッサにおいては、分解して多少の加工を施してやる必要があるのである。childrenDerivについては、後のセクションで詳述する。

attsDerivは、実際にはattDerivの集合体になる。これについても、後のセクションで詳述しようと思う。

childrenDeriv

開きタグのvalidationが完了すると、次はその内容モデルのvalidationが行われる。ただし、XMLPull, StAX, XmlReaderといったpull型ストリーミングプロセッサにおいては、内容モデルを自分のタイミングで解析するわけにはいかない。そのため、derivativeアルゴリズムでは説明されていない手順が、追加で必要になる。

childrenDerivは2種類の入力がある。text onlyなchildrenと、elementを含むchildrenである。childrenのうち、コメントノードや処理命令ノードは除外される。

空白文字の扱いは複雑である。text onlyなchildrenのみが存在する場合、空白文字のみからなるテキストノードは処理対象となるが、elementを含むchildrenの場合は処理対象とならない*4。これはRELAX NG仕様書ではセクション6.2.7のweak match 2、derivativeアルゴリズムではstripChildrenDerivとして、それぞれ説明されている。

これに関連して、もうひとつ注意しなければならないのが、childrenDerivは、空白テキストノードだけを含む場合には、現在のパターンと、そのパターンに対してchildrenDerivを呼び出した結果とのchoiceを返す、ということである。

さらに、RELAX NGでは、空要素については、あたかも "" （空白文字列）が存在するかのように、""を引数にchildrenDerivを適用しなければならない。これはRELAX NG仕様書ではセクション6.2.7のweak match 3、derivativeアルゴリズムでは

childrenDeriv cx p [] = childrenDeriv cx p [(TextNode "")]

として説明されている。これはストリーミングプロセッサではそんなに簡単にできないかもしれない。（僕はXmlReader.Depthを使ってやっつけた。）

さらに、要素の内容が空白テキストノードしか無い場合、それは単なるインデントによって生じた空白かもしれない。これを仕様として定義した部分が、セクション6.2.7のweak match 2であり、この場合、その空白ノードは無視することができる。ただし、一方で、空白文字列はdataパターンの有効な内容かもしれないので、無視といっても、内容モデルとして空白テキストを適用した結果とのchoiceにする必要がある。これをderivativeで定義したものがこれだ:



childrenDeriv cx p [(TextNode s)] =

  let p1 = childDeriv cx p (TextNode s)

  in if whitespace s then choice p p1 else p1


なお、コメントや処理命令など、兄弟ノードの存在がvalidationに影響しうるので、文字列はそのテキストノード群が終わった時に、連結して処理する必要がある。これは、SAXで言えばstartElementあるいはendElementの時点でtextDerivを呼び出すという形で実現できる（もしmemoization最適化を行っているのであれば、textOnlyDerivやmixedTextDerivがtextDerivに先行する）。


…ツヅキマース

*1:3年くらい前にRelaxngValidatingReaderを作り始めた僕みたいなのがこれにあたる。

*2:僕は少なくとも数学の知識はほとんど高校生以下のはずだ。大学では、僕の周りは「√2 x √3 は」?と訊くと「√5だっけ?」と返ってくるようなレベルだった。

*3:もしかしたら僕の方式は関数オブジェクトのインスタンス生成よりローコストなのかもしれないけど、両方を実装して比較してみないと分からない。

*4:ちなみに、これを忘れると、exponential blowupが発生して、ハマることにもなる