(20日目) blockdiag の中を見てみよう

今日は blockdiag の構造について紹介していきたいと思います。
blockdiag は大きく分けて 4つのモジュールから構成されています。

  • parser
    • テキストファイルを解析するモジュール
  • builder
    • 解析した図をレイアウトするモジュール
  • drawer
    • 図を描画するモジュール
  • metrcis
    • 図を描画する際に位置を決めるモジュール

他にも細かいモジュールはいくつもありますが、今日はこの 4つのモジュールにフォーカスして
掘り下げていこうと思います。

parser モジュール

parser モジュールは名前の通り、ユーザが記述したテキストデータを解析するモジュールです。
テキストデータが文法に一致しているかのチェックや中間データ形式である AST (中間構文木)への変換を行います。

blockdiag は graphviz の文法(DOT言語)を参考にツールごとに文法を追加したり、
属性の数を大幅に増やしたりして作られています。

parser の文法定義は独自に作成したものを利用していますが、
パーサをまっさらな状態から書き起こすのは苦労するので、
blockdiag では funcparserlib というパーサジェネレータを利用しています。
funcparserlib は Python 上でトークンと構文を定義するだけで、かんたんにパーサが生成できるので重宝しています。

以下に、class 構文の定義のところを抜粋します。
なお、意味がつかみやすいよう定義順を入れ替えています。*1
パッと見では理解しづらいかもしれませんが、雰囲気を掴んでもらえたら幸いです。

    // class 構文
    class_stmt = (
        skip(n('class')) +
        node_id +
        attr_list
        >> unarg(AttrClass))

    // 属性リスト (cf. [foo = xxx, bar = yyy, baz = zzz])
    attr_list = (
        many(op_('[') + many(a_list) + op_(']'))
        >> flatten)
    a_list = (
        id +
        maybe(op_('=') + id) +
        skip(maybe(op(',')))
        >> unarg(Attr))

    // ノード名
    node_id = id  # + maybe(port)

parser モジュールはやることがシンプルなので、文法さえ決まってしまえば素直に作ることのできます。
慣れてくると新しい文法の追加も 10分程度でできるようになります。

builder モジュール

builder モジュールは parser モジュールが生成した AST から論理的な図を作成するモジュールです。
どのノードがどういった属性を持つのか、どの位置に配置されるのかなどを計算します。

レイアウトの部分は特に適切なアルゴリズムやルールがあるわけでもないので、
たくさん図を書いてよさそうなルールを見つけていって、コードとして実装しています。
今でも見ていて望ましくない配置が見つかった場合に変更しています。

この builder モジュールは各 blockdiag シリーズごとにまったく違う実装になっていて、
それぞれのツールごとにレイアウトの基本方針が異なります。
blockdiag は左から右、上から下という並び替えのルール、
seqdiag は上から下というルール、
nwdiag ではネットワーク毎に左から右へというルールをそれぞれ持っています。

ここでは blockdiag がどうやってノードを並べているか、イメージ化してみました。

blockdiag {
  A -> B -> C, D;
  E -> F -> G;
}

という定義があった場合、builder でレイアウトしはじめる際は、すべて座標 (0, 0) に配置されます。

ここから、親子関係を元に左から右へノードを並べていきます。
まずは A の子供となるノード、ここでは B を A のひとつ右(1, 0)に配置します。

次に B の子供となるノード、ここでは C と D を B のひとつ右(2, 0)に配置します。

C および D には子ノードが存在しませんので、何も行われません。
E, F, G も同様に親子関係を元に右に伸ばしていきます。

横方向(x方向)のレイアウトはこれで終了です。

次に縦方向(y方向)のレイアウトを行います。
縦方向のレイアウトは重なっている箇所を縦にずらしていきます。
真新しい方眼紙にひとつずつノードを置いていくイメージをしてください。

まずは A を配置します。

次に B, C と続けて配置します。(横方向の位置は先ほどのレイアウトのものを踏襲します)

そして D を配置します。
D は先程 (2, 0) に配置されていましたが、方眼紙を見ると (2, 0) にはすでに C が配置されています。
場所が重なってしまうので、D はひとつ下方向にずらして配置します (2, 1)。

そして、今度は E を配置します。
E は A のノード群とは別系統となるため、A 系統を避けるように下にずらします。
A 系統で一番下に配置されているのは D の (2, 1) になるので、(0, 2) に配置します。

F, G も同様に配置していきます。

実際には複雑な図でも綺麗に並べられるよう細かいルールを定義していますが、
blockdiag のレイアウトルールはこういったもので構成されています。

blockdiag シリーズの使い勝手の良さを決める自動レイアウト機能は
この builder モジュールが担っており、blockdiag のコア中のコア機能といえます。
それだけに細かいニーズに対応できるよう複雑な作りになっています。(特に blockdiag)


ちなみに、blockdiag で苦労している複雑な定義はつぎのようなものです。
どうやって並べると良いか、考えてみてはいかがでしょうか。

blockdiag {
  A -> B -> C -> D -> E -> A;
  F -> C;
}
blockdiag {
  A -> B -> C -> D, E, F;
  A -> G -> H -> I;
}
blockdiag {
  A -> E;
  A -> B -> C -> D -> E;
}

drawer モジュール

drawer モジュールは builder モジュールで並び替えた論理的な図を
画像ファイルとして出力するモジュールです。

blockdiag では PNG, SVG, PDF の 3種類のフォーマットに対応しています。
実は blockdiag 内部では、出力に利用しているライブラリがそれぞれ異なります。

この異なる 3つの異なるライブラリを統一的に扱うことが出来るよう、
blockdiag では PIL ライブラリの関数をベースに描画ライブラリインターフェースを定義しています。

imagedraw と呼ばれるそのライブラリは単にインターフェースを整えるだけではなく、
それぞれのライブラリが持っていない機能を少しずつ補っています。
例えば、PIL は点線を書く機能を持っていないため、独自に点線を書く機能を実装しています。
また、テキストの大きさから折り返し位置を計算する機能を持っていたり、
図をぼかす、回転させるなども統一的に行うことができます。

imagedraw では、line(線を引く), rectangle(四角を書く), ellipse(楕円を描く) などの
基本図形を書く機能だけしか提供していませんが drawer モジュールはこれを呼び分けることで
最終的な図を生成しています
blockdiag ではいくつもの shape を利用することができますが、これもこれらの基本関数で構成されています。

metrics モジュール

metrics モジュールは drawer モジュールで画像ファイルを生成する際に利用する補助モジュールで、
ノードやエッジ、グループなどの様々な要素の座標を決定するモジュールです。

builder モジュールでは (0, 0)、(2, 1) などの論理座標をつかってレイアウトしていましたが、
drawer モジュールで図を作成する際はピクセル単位の座標を使用します。
その変換は metrics モジュールで行うわけです。

最近よく変更しているのは seqdiag の metrics モジュールです。
seqdiag ではエッジのラベルが長い場合は自動的に折り返しを行うようになっているため、
エッジのテキストにあわせてエッジを描画する y 座標を自動的に調整しています。

ここでも基本的な考え方は方眼紙モデルで、各マス目(ノード)ごとに幅を調整することができたり、
マス目とマス目の間(span)を調整することで柔軟なレイアウトを行なっています。

まとめ

今日は趣向を変えて blockdiag の内部構成についてご紹介しました。
開発しているとbuilder 以外はあまり複雑に感じないのですが、
使っている皆さんは予想もできない複雑な仕組みで動いていると勘違いされているようなので
今日はおおざっぱに内部構成をまとめてみました。

興味が有る方はソースコードを読んでいただいたりして、プログラムとしての blockdiag も見ていただけるとありがたいです。
興味があるけどよく分からない人も遠慮なく言っていただければ、一緒にコードリーディングなどもできると思います。

blockdiag はほとんどひとりで作っているので、興味を持った方は是非いじってみてください :-)

*1:本来は細かい要素から定義していきます。この引用の順を実行しようとした場合、未定義エラーが発生します。