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: |$
  • ノード: 表のセル
    • このノード親になれるノード: 表の行
    • ノードの開始を検出する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」について、優先度の問題がある(例えば上の例の、表の行の終了と表のセルの終了)。この場合、

  1. 文字列内での一致位置がより前のものを優先
  2. ↑で互角なら、構文規則的により上位の要素の終了を優先 & より下位の要素の開始を優先
  3. ↑でも互角なら、一致した長さが長い方を優先

とすることで、優先度を解決できるのではあるまいか。

考えてみたので

ひとしきりまとめてみたところ、実現出来そうな気がしてみたので、晒してみて、実装する方向に自分を追い込んでみた。職場が無駄に忙しいのが問題だが、時には自分のコードも書かなくては。