derivative algorithmにおけるerror recoveryの実装

James Clarkが7年前に書いたRELAX NGのderivative algorithmをもとに、RelaxngValidatingReaderにエラー回復を実装しようとしている。

JJCの説明はこんな感じだ:

• もしstartTagOpenDerivがエラーを起こしたら、Jingはまずいくつかの必要な要素が省略されているのではないかという推定に基づいて回復を試みる。実際には、パターンを変形して、それぞれのGroupにおける最初のオペランドをoptionalにして、再度startTagOpenDerivを試行する。
• もしこれでもエラーが起こる場合は、後続兄弟を検証するために、その要素を無視する。その要素自身を検証するために、スキーマ全体からその要素パターンの定義のうち、現在の要素の名前にname classが一致するものを探し出す。
  • もしそのような要素パターンが1つ以上発見されたら、それらの要素定義の全てから、最も名前を具体的に指定しているものを、choiceでくくったパターンを使う。
    • name classの具体性は、“name”が”nsName”や”anyName”よりも、“nsName”が”anyName”よりも、それぞれ高いものとする。
  • もしそのような要素パターンが1つも存在しなければ、その要素の中でスキーマが定義している要素パターンに合致するようなサブツリーのみが検証される。そのサブツリーに含まれないノードは無視される。
• startAttributeDerivがエラーを起こしたら、その属性を単に無視して回復する。
• startTagCloseDerivがエラーを起こしたら、全ての属性パターンをemptyに置き換えて回復する。
• textDerivがエラーを起こしたら（これは属性値あるいは子要素をもたない要素にのみ用いられる）、全てのトップレベルのAfterパターン（他のAfterパターンの中に含まれないAfterパターン）の最初のオペランドをemptyに置き換えて回復する。
• mixedTextDerivがエラーを起こしたら、そのテキストノードを無視して回復する。
• endTagDerivがエラーを起こしたら、全てのトップレベルのAfterパターン（上記）の2番目のオペランドをchoiceにしたものを使って回復する。

以上について自分の言葉で理由付けなどを補足説明してみよう。

• mixedTextDerivは、mixedにおけるテキストノードはRELAX NGの仕様上完全にoptionalなので、emptyに置き換えることで確かに回復できるはずだ。
• end of attribute (EndAttributeDeriv)については明記されていないが、これはendTagDerivと同じ規則で実装することになっているので、同じやり方で回復できるはずだ。
• textDerivについて説明されている方法は、直感的には分かりにくいが、
  • (1)Afterパターンのオペランドは、1つ目が「何かをvalidなものとして通過させた後、そのブランチにおいて次に出現すべきパターン」であり、2つ目が「ここまでのノードツリーをvalidなものとして通過させてきたパターン」であるところ、
  • (2)今ここではテキストノードしか登場しないので、関連するAfterパターン（パターンの内容としてトップレベルにあるやつ）の1つ目をemptyとすることで、そのテキストノードの検証を省略できる、ということだ。
  • トップレベル限定になっているのは、それ以外のノードは全て現在のノードとは関係ない内容だから。
  • emptyの代わりにtextを使っても同じことになるだろう（が、その必要もないだろう）。
• startTagOpenDerivは一見ややこしい。というか、やろうと思えばもっと簡単で不便なエラー回復を実装することができるだろう。期待されていた要素とは別の要素、あるいは存在しないはずの要素がインスタンス中に出現する理由は2つある:
  • 出現しなければならない要素が出現しなかった場合。この場合は、現在のパターンで、最初に必須になりうるものを全てoptional（simplified formなのだから、実際にはemptyとのchoice）にした上で、再試行すると通過するはずだ。
  • 想定外の要素が出現した場合。この場合、
    • この要素をスキップしてしまえばよい。ひとつの簡単な解決方法は、xs:anyのようなパターンを用意して、それに当てはめて解析してしまうというやり方だ。僕は面倒くさがりなのでこれで解決しようと思っている。
    • 一方で、この要素には定義済みの有効な内容が含まれているかもしれないのだから、定義されていそうな内容については、なおも妥当性検証を続けるというのはアリではないか…というのが、JJCが提示しているサブツリー検証だ。「定義済みの有効な内容」というのは、論理的にはありえないが、実際にはこのインスタンス要素は、grammarのトップレベルでdefineされていることも少なくないだろう、という前提に基づいて、この要素の定義にもっとも近いと思われるdefineを探し出して（それがname classの分析）、もっとも名前を具体的に指定している定義パターンをchoiceで結んで、改めてサブツリーだけ検証することも可能だ。

ちなみに、ValidationEventHandlerでエラーをスキップできるXmlReader（XmlValidatingReaderなど）についても、僕は単にエラーを起こしたノードをスキップするアプローチで実装している。そんな細かいところは.NETの動作なんて気にしていないし、実のところMonoのXML Schema実装は.NET実装なんてそっちのけでW3C仕様を追いかけて作ってあるので（そのため、少なからず.NETのバグを見つけたものだ）、エラー回復の実装は.NET APIにあったからというおまけ程度でしかなかったりする。

追記: 多分できたのでsvnに投げ込んでおいた。