wikiforme もどきを作るとしたら
うだうだなメモ。そういえばこのブログにうだうだなメモを書いたことはなかったような。
やりたいことの核心
以下の二つが id:saiya_moebius 的にやりたいことだったのだが、それがちょうど上の元ネタとマッチしている事に最近気がついたという次第。
ただ、id:saiya_moebius としては、マークアップ言語の理想を追求して最初の記法と最後の出力形式との完全な直交性を確保する気はなく、あくまで書く手間と変換する手間を減らしたいだけ。
何がうれしいか
といったことを楽にしたいのである。
また、それらを活用するには、記法のパース結果(XML)から何らかの有意なコンテンツを出力できると、記法を扱うためのメカニズムの存在意義が出るというものであろう。
wikiforme について
上のやりたいことは wikiforme の中の人もそういっている*2のだが、id:saiya_moebius としては以下の点も考慮したいところである。
- 特定言語に癒着しない
- 仕組みをシンプルにとどめる
前者については、構文定義などが Ruby にべったりくっついていると実際問題困るというのが理由。RPC なり stdin/out 経由の通信なりで疎に分離したいところである。具体的には、インターフェースの仕様だけがあって、処理系は任意の言語なりで書けると嬉しい。
後者は、うっかり欲を出し過ぎたり、「もしかしてこういう場合も」を考えすぎてgdgdになるぐらいなら、前述の目的にフォーカスしてできるだけシンプルにしたい、のが理由である。wikiforme が、手っ取り早く記法を扱うためには複雑に思えることもあって、この点も意識したく思うのである。
wikiforme もどきの基本的な機構: 記法のパースと木構造(XML)の出力
思想は wikiforme と大きく変わらない。具体的には、
- 元の記法には何らかの形で、ノードの開始を明示する
- ノードの終了が明示されていない場合、適宜補完する
- 階層の一部を省略された場合、適宜補完する
- ノードの終了や階層の中間のノードの補完は、ノードの親子関係の制約に着目して行う
- 例: A の親は B、B の親は C という制約があるなら、A と C の中間を補完することが出来る
といったところ、だろう。
これを実現するためには、以下を実現すれば良さそうだ。
- 元の記法から、ノードの開始を検出する
- ノードの親子関係に関する制約を与えられるようにする
- 補完に使う
- ノードの親子関係を適切に補完する
そのためには、以下のような造りにすれば良さそうだ。
- ノードの開始を検出するための正規表現なりを、記法の定義に含めるようにする
- 親子関係の制約も記法の定義に含めるようにする
- 親子関係の補完は、親子関係のグラフをダイクストラ法なりで探索するだけ。
- 参考に: 補足的な機構: 親子関係の補完
wikiforme もどきの補足的な機構: 親子関係の補完
ref: WikiForme 0.5 開発裏話 1 - Blog by Sadayuki Furuhashi
補完の発想は↑のリンクにある wikiforme の振る舞いとほぼ同じであるが、リンク先の方法だと(id:saiya_moebius が理解するには)いささか面倒なので、もう少し簡略化してみた。
このやりかたのポイントは、要素の親子関係の規則からグラフを構築して、要素の自動補完は単なる最短経路の探索問題だと見なしてしまう点である。
こうすることで、煩雑な手続きを使わずとも、ダイクストラ法なりを適用するだけという簡潔な方法で木構造の自動補完が出来るはずである。
例: 箇条書き
たとえば、リンク先にもある箇条書き記法を用いて例を作ると、
- 1 - 2 -- 3-1 -- 3-2 - 4
というテキストと、
- ノード: 箇条書き全体(Lv1)
- (割愛)
- ノード: 箇条書きのアイテム(Lv1)
- このノード親になれるノード: 箇条書き全体(Lv1)
- ノードの開始を検出するregex: ^\-
- ノード: 箇条書き全体(Lv2)
- このノード親になれるノード: 箇条書きのアイテム(Lv1)
- ノード: 箇条書きのアイテム(Lv2)
- このノード親になれるノード: 箇条書き全体(Lv2)
- ノードの開始を検出するregex: ^\-\-
という記法の定義が与えられた場合に、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1</箇条書きのアイテム(Lv2)> <箇条書きのアイテム(Lv2)>3-2</箇条書きのアイテム(Lv2)> </箇条書き全体(Lv2)> </箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>4</箇条書きのアイテム(Lv1)> </箇条書き全体(Lv1)>
という木構造を得ることがゴールである。ちなみに、このゴールは XHTML のリスト構造と完全に同型であったりもする。
ここで、上の例の例の箇条書きを、ノードの補完なしで処理すると、上から順に
- 箇条書きのアイテム(Lv1) (= 1)
- 箇条書きのアイテム(Lv1) (= 2)
- 箇条書きのアイテム(Lv2) (= 3-1)
- 箇条書きのアイテム(Lv2) (= 3-2)
- 箇条書きのアイテム(Lv1) (= 4)
だけが得られる。
このとき、3-1 や 3-2 の親要素である 箇条書き全体(Lv2) を補完することを考える。
最初に下準備として、例に示してある構文の定義から、要素の親子関係の制約を表すグラフを描いてみると、こうなる。
まず、箇条書きのアイテム(Lv2) が最初(3-1)に出現した時、その時点で生成済みのツリーは以下のようになるだろう。
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2
この時点では、また箇条書きのアイテムの 2 が出現しただけなので、このようになるはずである。
ここで、箇条書きのアイテム(Lv2) が出現したのだから、これを追加したいのだが、上記の図の通り、箇条書きのアイテム(Lv1) の子要素に 箇条書きのアイテム(Lv2) を付けることはできない。
そこで、まず上のグラフ(というかツリー)上で、生成済みの一番下の要素である 箇条書きのアイテム(Lv1) から 生成したい要素である 箇条書きのアイテム(Lv2) の親になれる要素 への最短経路を探す。すると、
という経路がある。つまり、上の図で与えられた制約を満たすように補完するには、箇条書き全体(Lv2) を間に挟めば良い。
このことから、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1
という結果を得ることが出来た。
また、先述の例について、たとえば 箇条書きのアイテムの 4 の部分はどのように処理されるのだろうか。
箇条書きのアイテムの 4 が出現したとき、その時点で生成済みのツリーは以下のようになるだろう。
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1</箇条書きのアイテム(Lv2)> <箇条書きのアイテム(Lv2)>3-2
この時点では、また箇条書きのアイテムの 3-2 が出現しただけなので、このようになるはずである。
ここで、箇条書きのアイテム(Lv1) を 箇条書きのアイテム(Lv2) の子に追加しようとすると、また例の如く図に描いてある制約に反してしまう。ので、例によって図の上で親になれる要素への経路を探すと、
という経路がある。
この経路を見るに、生成済みの 箇条書きのアイテム(Lv2) と 箇条書き全体(Lv2) と 箇条書きのアイテム(Lv1) も閉じてしまえば良い。
よって、以下の結果になる。
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)> 2 <箇条書き全体(Lv2)> <箇条書きのアイテム(Lv2)>3-1</箇条書きのアイテム(Lv2)> <箇条書きのアイテム(Lv2)>3-2</箇条書きのアイテム(Lv2)> </箇条書き全体(Lv2)> </箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>4
例: 箇条書きと表
また、このグラフの最短経路を用いた補完は、もう少し厄介なシチュエーションにも対応できそうである。
たとえば、上の記法の定義に「セクションの中身」と「表」の規則を追加して以下のようにしたとする。なお、セクションの中身 は箇条書きと表の親である。
- ノード: セクションの中身
- (割愛)
- ノード: 箇条書き全体(Lv1)
- このノード親になれるノード: セクションの中身
- ノード: 箇条書きのアイテム(Lv1)
- このノード親になれるノード: 箇条書き全体(Lv1)
- ノードの開始を検出するregex: ^\-
- (中略)
- ノード: 表全体
- このノード親になれるノード: セクションの中身
- ノード: 表の行
- このノード親になれるノード: 表全体
- ノードの終了を検出するregex: |$
- ノード: 表のセル
ここで、以下のテキスト
- 1 - 2 |a1|b1|c1| |a1|b2|c2|
をパースした場合、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>2</箇条書きのアイテム(Lv1)> </箇条書き全体(Lv1)> <表全体> <表の行> <表のセル>a1</表のセル> <表のセル>b1</表のセル> <表のセル>c1</表のセル> </表の行> <表の行> <表のセル>a2</表のセル> <表のセル>b2</表のセル> <表のセル>c2</表のセル> </表の行> </表全体>
となって欲しい(ちなみにこれも XHTML の構造と一致している)。
ここで、箇条書きのアイテムの処理は先述した通りであるが、例えば箇条書きから表への切り替わり目がどのように処理されるのかを確認してみる。
まず、表のセルの a1 が出現したときには、生成済みのツリーは以下のようになっており、
<箇条書き全体(Lv1)> <箇条書きのアイテム(Lv1)>1</箇条書きのアイテム(Lv1)> <箇条書きのアイテム(Lv1)>2
この経路探索結果と、上の例での要領を併せると、
- 箇条書きのアイテム(Lv1) を閉じて
- 箇条書き全体(Lv1) を閉じて
- 表全体 を生成して
- 表の行 を生成して
- 最後に今回生成したかった 表のセル も生成
すると良いということが分かる。
あとは、表のセルや行の処理も、ほぼ同じ要領で処理してゆけばよい。
もちっと詳細に
上の例だと、例を簡潔にするためにいくつか曖昧にスルーしていた部分がある。が、それらも以下のように考えると、シンプルなまま解決できる、はずである。出来ない場合は筆者が見落としているので指摘して欲しい。
例えば、下のような、構文規則のグラフと経路探索した結果があったとする。
この時、
- 経路(矢印)がノードの上に出ている場合、そのノードを閉じる
- 経路(矢印)がノードの上から入っている場合、そのノードを補完する
- それ以外のノードについては、なにもしない
このような基準でノードを閉じたり足したりすることで、得られた経路を具体的にどのようなノードの操作に反映するのかが明確になるであろう。
それと、あるノードの親になれるノードが複数種類ある場合は、補完用の経路探索結果の長さが最も短いものを採用すれば良かろう。もし最短距離に複数あるなら、それは文法が曖昧であるので、エラーにするか、Warning を出しながらもとりあえず適当などれかにしておけばよかろう。
また、構文の「ノードの開始を検出するregex」や「ノードの終了を検出するregex」について、優先度の問題がある(例えば上の例の、表の行の終了と表のセルの終了)。この場合、
- 文字列内での一致位置がより前のものを優先
- ↑で互角なら、構文規則的により上位の要素の終了を優先 & より下位の要素の開始を優先
- ↑でも互角なら、一致した長さが長い方を優先
とすることで、優先度を解決できるのではあるまいか。
考えてみたので
ひとしきりまとめてみたところ、実現出来そうな気がしてみたので、晒してみて、実装する方向に自分を追い込んでみた。職場が無駄に忙しいのが問題だが、時には自分のコードも書かなくては。