🐛

D言語でコンパイル時に Common Workflow Language パーサーを生成したい！(妥協編)

2022/01/01に公開

この記事は D言語 Advent Calendar 2021 の15日目および Common Workflow Language (CWL) Advent Calendar 2021 の5日目の記事です。

この記事は以下の二部三部構成になっています。

(最初の記事) ワークフロー記述言語 Common Workflow Language (CWL) とその文法定義形式 Semantic Annotations for Linked Avro Data (SALAD)、最近は教育用のプログラミング言語としてもその頭角を表しつつあるD言語の概要を示し、D言語でコンパイル時 SALAD パーサージェネレータを書いたら最強なのでは？という野望について語ります。
(前の記事) D言語でコンパイル時 SALAD パーサージェネレータを書く方針と、SALAD 定義に対応したD言語でのデータ構造を定義する話をします。
(この記事) D言語のつよつよメタプログラミングによりパーサーの大部分が自動生成できることを示し、最終的にコンパイラとカリカリチューニングされたコードの CTFEability という壁に阻まれ、コンパイル時 SALAD パーサージェネレーターを書くことに失敗した話をします(つらい)。

以降では、まず開発した CWL v1.0 の手書きパーサーの解説をD言語のつよつよメタプログラミング機能に簡単に触れつつ行い、そのあと今回のパーサージェネレーター実装を阻止したブロッカーについて解説します。

前回のあらすじ

これを手書きで

CommandLineTool.yml

type: record
name: CommandLineTool
documentRoot: true
fields:
  - name: id
    type: string?
  - name: class
    jsonldPredicate:
      "_id": "@type"
      "_type": "@vocab"
    type: string
  - name: inputs
    type:
      type: array
      items: CommandInputParameter
    jsonldPredicate:
      mapSubject: id
      mapPredicate: type
  - name: requirements
    type: ProcessRequirement[]?
    jsonldPredicate:
      mapSubject: class
  ...

こうする

cwl.d

@documentRoot class CommandLineTool
{
    SumType!(None, string) id_;
    static immutable class_ = "CommandLineTool";
    @idMap("id", "type") CommandInputParameter[] inputs_;
    @idMap("class")
    SumType!(
        None,
        SumType!(
            DockerRequirement,
	    InlineJavascriptRequirement,
            ...
        )[],
    ) requirements_;
    ...
    
    mixin genCtor;
}

あとは genCtor の中身を実装すればなんとかなるはず！

`genCtor`: コンストラクタ生成 (template mixin)

D言語の Template mixin を使い、コンストラクタを生成します。YAML 部分のパースは D-YAML に丸投げして、D-YAML のノード型であるNode から各データ型への変換部分のみを実装します。

genCtor の定義は以下になります。FieldNameTuple でフィールド名一覧を取得して、static foreach で各フィールドへの変換・代入を行う文を Assign テンプレート(後述)を mixin することでコンパイル時に挿入します。__traits(getMember, this, field) でフィールド名からフィールドを取得しているのが少しトリッキーかもしれませんが、基本的には素直なコードですね。

コンストラクタの引数 LoadingContext は各種名前解決に必要な情報を保持するデータ構造ですが、今回の解説では利用しません。

mixin template genCtor()
{
    this(in Node node, in LoadingContext context)
    {
        static foreach(field; FieldNameTuple!(typeof(this)))
        {
            mixin(Assign!(node, __traits(getMember, this, field), context));
        }
    }
}

D-YAML では各データ構造に対して this(const Node) を定義すれば Node#as!T を使った変換が可能になりますが、この方法では SumType などの既存のデータ構造に対しては使えません。今回は SumType に対しても適用可能な as_!(T, idMap) 関数を定義して、Node 型から各フィールドの型への変換を行います。

各フィールドの代入文生成 (文字列 mixin, `static if`, CTFE)

Assign(alias node, alias field, alias context) テンプレートでは、与えられた node をフィールド field の型に合わせて変換して代入する文字列を返すようにします。返された文字列を genCtor で mixin すると、実際に代入を行う文をコンパイル時に挿入できます。またここで SumType!(None, ...) のようなオプショナルなフィールドの対応も行います。

重要なポイントは、field を alias として受け取っている部分です。これにより、各フィールドの宣言時に指定した @idMap などの属性を Assign 内で取得して利用することができます。変数の属性は hasUDA や getUDAsで存在確認および取得が可能です。

    static if (hasUDA!(field, idMap))
    {
        enum idMap_ = getUDAs!(field, idMap)[0];
    }
    else
    {
        enum idMap_ = idMap.init;
    }

あとは field の型が SumType!(None, ...) のように None があるかどうかで生成する文字列を変えればいいです。コンパイル時の条件分岐には static if を使います。使い方も通常の if 文とほぼ同様です。

    enum param = field.stringof[0..$-1]; // フィールド名末尾の "_" を取り除く
    static if (isSumType!T && is(T.Types[0] == None))
    {
        // SumType!(None, ...) の場合はフィールドの存在チェックと代入文を生成
        enum Assign = format!q"EOS
            if (auto f = "%s" in %s)
            {
                %s = (*f).as_!(%s, %s)(%s);
            }
EOS"(param, node.stringof, field.stringof, T.stringof,idMap_, context.stringof);
    }
    else
    {
        // SumType!(None, ...) でない場合は代入文のみを生成
        enum Assign = format!q"EOS
            %s = %s["%s"].as_!(%s, %s)(%s);
EOS"(field.stringof, node.stringof, param, T.stringof, idMap_, context.stringof);
    }

テンプレート名と同名の定数を宣言すると、そのテンプレートの返り値として利用できます。

また Assign に代入している部分で利用している format は文字列整形を行う関数です。関数なのですが、D言語は Compile Time Function Execution (CTFE) という機能があり、多くの関数はコンパイル時にも実行が可能です。今回は引数が全てコンパイル時に決定できる定数なため format もコンパイル時実行可能 (CTFEable) なので、Assign はコンパイル時に定数に畳み込まれます。例えば SumType!(None, string) id_; に対しては、上のコードは以下の文字列に畳み込まれます^[1]。

    enum Assign = q"EOS
        if (auto f = "id" in node)
        {
            id_ = (*f).as_!(SumType!(None, string), idMap.init)(context);
        }
EOS";

この文字列 mixin は非常に強力です。非常に強力なのですが、この記事での出番はここだけです。

そんな大層なことをしなくてもD言語ではパーサーを生成できます。

idMap によるパース方法変更

次に、データ構造部での宣言

cwl.d

    @idMap("id", "type") CommandInputParameter[] inputs_;

に対応する代入文

    inputs_ = (*f).as_!(CommandInputParameter[], idMap("id", "type"))(context);

について考えます。Node を CommandInputParameter[] に変換する as_ 関数を実装すればよいのですが、idMap の値によってパース方法が変わるので注意…する必要もなく、普通に static if でパース方法を変えればいいだけです。ちなみに idMap は以下のデータ構造です。

struct idMap { string subject; string predicate = ""; }

idMap が取りうる各場合についてパース方法を分岐させます。

subject が空文字列(もしくは idMap が未指定)の場合、通常と同様に配列の各要素を変換します

  static if (idMap_.subject.empty)
  {
      T arr; // `inputs_` の場合は T == CommandInputParameter[]
      foreach (elem; node.sequence)
      {
          alias E = ElementType!T;
          arr ~= elem.as_!E(context);
      }
      return arr;
  }

subject が空文字列でない場合 (上の場合は "id")、配列ではなくオブジェクトが来る場合もあります。オブジェクトの場合、各キーは subject で指定したフィールド (上の場合は CommandInputParameter#id) とみなして変換を行います。
さらに predicate が空文字列でない場合には、オブジェクトの value として predicate で指定したフィールドの値が来る場合があります (subject の変換とまとめると、"inp1": "File" というオブジェクトのキーバリューのペアは配列要素 { "id": "inp1", "type": "File" } に変換されます)。この部分は多分コードを見たほうが早いです。

    else
    {
        // node が配列だった場合は idMap 未指定の場合の処理に投げ直す
        if (node.type == NodeType.sequence)
        {
            return node.as_!(T, idMap.init)(context);
        }

        // 各 key, value のペアを配列形式に置き換えてから変換する
        T arr;
        foreach (kv; node.mapping)
        {
            auto key = kv.key.as!string;
            auto value = kv.value;
            
	    Node elem;
	    elem.add(idMap_.subject, key); // key は subject で指定したフィールドになる
	    
            static if (idMap_.predicate.empty)
            {
                elem = value; // predicate 未指定の場合、残りはそのまま
            }
            else
            {
                if (value.type == NodeType.mapping)
                {
		    // idMap_.predicate.empty の場合と同様
                    elem = value;
                }
                else
                {
		    // predicate が未指定かつ value がオブジェクトでない場合には以下と同値:
		    // { $subject: key, $predicate: value}
		    // ここで $subject, $predicate は idMap の対応する値
                    elem.add(idMap_.predicate, value);
                }
            }
            alias E = ElementType!T;
            arr ~= elem.as_!E(context);
        }
        return arr;
    }

少しややこしく見えるかもしれませんが、全然メタメタしくない普通のコードですね。

`SumType` の変換: `static foreach` と `static immutable` フィールドを活用したディスパッチ

cwl.d

    @idMap("class")
    SumType!(
        None,
        SumType!(
            DockerRequirement,
	    InlineJavascriptRequirement,
            ...
        )[],
    ) requirements_;

に対応する代入文

    if (auto f = "requirements" in node)
    {
        requirements_ = (*f).as_!(SumType!(None, SumType!(...)[]), idMap("class"))(context);
    }

ですが、オプショナルフィールドや idMap については既に解説済みなので省略します。ここでは未解説だった以下の SumType (None なし)の変換方法について解説します。

    SumType!(
        DockerRequirement,
        InlineJavascriptRequirement,
        ...
    )

各 Requirement の SALAD 定義は、例えば以下の形になっています。

type: record
name: DockerRequirement
extends: ProcessRequirement
fields:
  - name: class
    type: string
    doc: "Always 'DockerRequirement'"
    jsonldPredicate:
      "_id": "@type"
      "_type": "@vocab"
  ...

対応するD言語でのデータ構造定義は以下です。

class DockerRequirement
{
    static immutable class_ = "DockerRequirement";
    ...
}

つまり与えられた Node オブジェクトの "class" フィールドの値でディスパッチできますね！

まずは SumType の型中からディスパッチに使える型一覧を列挙します。今回開発したコードでは、static なフィールドを持っていればディスパッチできると仮定しているので補助的なテンプレートも用意します(以下は全部コンパイル時に動く)。


// alias RecordTypes = // SumType.Types から None を除いた型

// T が持つ static なフィールド一覧を列挙
enum StaticMembersOf(T) = Filter!(ApplyLeft!(hasStaticMember, T), __traits(derivedMembers, T));
// T がディスパッチ可能かどうか
enum isDispatchable(T) = StaticMembersOf!T.length > 0;
// ディスパッチ可能な型一覧
alias DispatchableRecords = Filter!(isDispatchable, RecordTypes);
// ディスパッチには利用できない型一覧
alias NonDispatchableRecords = Filter!(templateNot!isDispatchable, RecordTypes);

ディスパッチに使えない型が混ざっている場合、1つまでなら許容できます(消去法で決定できるため)が、2個以上だと問題です。そのような状況は static assert を使ってコンパイル不可能にしてしまいましょう！

static assert(NonDispatchableRecords.length < 2,
              "There are too many non-dispatchable record candidates: " ~
              NonDispatchableRecords.stringof);

あとはディスパッチに使えるフィールド名を抽出して(抽出はコンパイル時に行われます)

    enum DispatchFieldName = StaticMembersOf!(DispatchableRecords[0])[0];

ディスパッチ用の switch 文を用意しましょう。switch する先の各 case 文は static foreach 文を使って生成します。

    auto id = node[DispatchFieldName[0..$-1]].as!string;
    switch (id)
    {
        static foreach (RT; DispatchableRecords)
        {
            case __traits(getMember, RT, DispatchFieldName): return T(node.as_!RT(context));
        }
        static if (NonDispatchableRecords.length == 0)
        {
	    // ディスパッチできない候補が全く無い場合は決定不能なので例外を投げる (実行時)
            default: throw new DocumentException("Unknown record type: " ~ id);
        }
        else
        {
	    // 列挙した DispatchFieldName のどれにも当てはまらない場合は消去法で決定
            default: return T(node.as_!(NonDispatchableRecords[0])(context));
        }
    }

フィールドの値によってディスパッチする効率的なコード生成！というと難しそうですが、非常に素直なコードですね。

CWL パーサ生成: モジュール中の定義一覧から `documentRoot` を持つクラスを抽出

ここまでで各 SALAD 定義に対応したD言語のデータ構造用のパーサーが完成しました。
さて、前回お話したデータ構造中の documentRoot は結局使っていませんね。最後にこれを使います。

cwl.d

@documentRoot class CommandLineTool { ... }

CWL の SALAD 定義では CommandLineTool や CommandInputParameter、DockerRequirement などの様々なデータが定義されますが、CWL のトップレベルにくるのは documentRoot: true (D言語で定義したデータ構造では @documentRoot が付いたクラス) のみです。

CWL のトップレベルにくるのは CommandLineTool、Workflow および ExpressionTool だけなので、以下の関数を直接書けば完成ですが、せっかく @documentRoot 属性をデータ構造に付けたので、この部分も自動化しましょう！

auto parser(in Node node, in LoadingContext context) {
    return node.as_!(SumType!(CommandLineTool, Workflow, ExpressionTool))(context);
}

各 SALAD 定義に対応する全てのデータ構造が1モジュール^[2](例えば cwl.d)にまとめてある場合、以下のコードで documentRoot が付いたクラスのみを取りうる SumType を定義できます。

template DocumentRootType(alias module_)
{
    alias StrToType(string T) = __traits(getMember, module_, T);
    
    // モジュール内の全ての定義を列挙
    alias syms = staticMap!(StrToType, __traits(allMembers, module_));
    // 定義中から documentRoot 持ちの定義を抽出
    alias RootTypes = Filter!(ApplyRight!(hasUDA, documentRoot), syms);
    
    // 抽出した型の SumType が CWL パーサーの返り値
    alias DocumentRootType = SumType!RootTypes;
}

パーサーも DocumentRootType を使って定義できますね。これで完成です！

auto parser(alias module_)(in Node node, in LoadingContext context)
{
    return node.as_!(DocumentRootType!module_)(context);
}

パーサージェネレーターを実装したかった…

これまで解説した手書きパーサーのうち、SALAD 定義に対応したD言語でのクラス定義部分以外は SALAD 定義とは完全に独立しています。

そのためコンパイル時パーサージェネレーター実装には、これから

CommandLineTool.yml

type: record
name: CommandLineTool
documentRoot: true
fields:
  - name: id
    type: string?
  - name: class
    jsonldPredicate:
      "_id": "@type"
      "_type": "@vocab"
    type: string
  - name: inputs
    type:
      type: array
      items: CommandInputParameter
    jsonldPredicate:
      mapSubject: id
      mapPredicate: type
  - name: requirements
    type: ProcessRequirement[]?
    jsonldPredicate:
      mapSubject: class
  ...

次のコードをコンパイル時に生成すればいいことになります。

CommandLineTool.d

@documentRoot class CommandLineTool
{
    SumType!(None, string) id_;
    immutable class_ = "CommandLineTool";
    @idMap("id", "type") CommandInputParameter[] inputs_;
    @idMap("class")
    SumType!(
        None,
        SumType!(
            DockerRequirement,
	    InlineJavascriptRequirement,
            ...
        )[],
    ) requirements_;
    ...
}

楽勝では！？と思いきや、いくつかの理由で実装できませんでした。
以下、ブロッカーを列挙します。誰か倒してください。

`$import` および `$include` ディレクティブがコンパイル時に実行できない: `import` 式の CTFEability

SALAD には $import と $include ディレクティブという、外部の SALAD 定義ファイルなどを読み込む機能が存在します。実行時であれば readText が利用でき、またコンパイル時に外部ファイルを読み込む import 式も存在するため、以下のように __ctfe 変数で分岐すればコンパイル時と実行時のどちらでも動く関数は作れるんじゃないの？と思っていました^[3]。

// 注意: CTFEable ではありません！
auto fetchText(string file)
{
    if (__ctfe)
    {
        // CTFE 中は `import` 式で読み込む
        return import(file);
    }
    else
    {
        // 通常の実行時は `readText` で読み込む
        return readText(file);
    }
}

が、動かなかったので issue 登録したのですが、RESOLVED INVALID として close されてしまいました。CTFE と import 式ではコンパイラ中での実行フェイズが異なるので CTFE 中では import 式がうまく評価できないわけですね。

参考: https://blog.kotet.jp/2018/12/compile-time-vs-compile-time/

D-YAML が CTFEable ではない: カスタムアロケーターと unsafe cast

そもそも SALAD を読み込むのに使っている D-YAML が CTFEable ではないという問題があります。
この問題を掘っていくと、

D-YAML が timestamp 型のパースに利用している std.regex の ctRegex および regex に対する matchAll が CTFEable ではない
std.regex 内部ではカスタムアロケーター(さらに内部で malloc、free)を用いたメモリの確保や再利用などを行っている
ctRegex、regex の内部では BacktrackingMatcher および ThompsonMatcher という二種類のアルゴリズムが使われており、各アルゴリズム中ではカスタムアロケータで確保したメモリをそれぞれ別の型として扱っている
CTFE 中では T* <-> void* のキャストはできるが T* <-> void* <-> U* のキャストができない

コンパイル時だけ new 使えばいいじゃん！という話ではあるのですが、メモリ確保を行っている場所が結構散逸していて(かつ確保方法がカスタムアロケータ経由だったり普通の new だったり)、自分のパワーでは倒せませんでした。

逆にパワーがあれば倒せると思うので誰か倒してください…

今後の方針

SALAD 定義からD言語でのクラス定義の部分だけを schema-salad-tool に生成してもらう？(もはやコンパイル時パーサージェネレーターではないですが…)
パーサー部分はもう少し改善できる点(一部ゴリ押し実装だったり、フィールド名の名前解決をさぼっていたり)が残っています。

まとめ

惜しくもコンパイル時パーサージェネレーターは実現できませんでしたが、パーサーのほとんどは自動生成できました。~~ほぼコンパイル時パーサージェネレーターと言ってもいいのでは~~

この一連の記事の最初に引用したツイートでは、D言語が メタプログラミングが特に強力 と紹介されていました。今回の記事では、単にメタプログラミングが強力なだけではなく、黒魔術を駆使しなくても強力なメタプログラミングが行えることがわかっていただけたと思います。~~強力すぎて書くことが無くなりそうになった~~

脚注

この部分では Delimited Strings (いわゆるヒアドキュメント) と Uniform Function Call Syntax (UFCS) (mixin される文字列内)という機能も使われています。メタプログラミングと直接関係はないですが、地味ながら便利ですね。 ↩︎
D言語では、各モジュールとソースファイルは1対1対応しています。 ↩︎
import 式を見たときに嫌な予感はしていたのですが… ↩︎

前回のあらすじ

genCtor: コンストラクタ生成 (template mixin)

各フィールドの代入文生成 (文字列 mixin, static if, CTFE)

idMap によるパース方法変更

SumType の変換: static foreach と static immutable フィールドを活用したディスパッチ

CWL パーサ生成: モジュール中の定義一覧から documentRoot を持つクラスを抽出

パーサージェネレーターを実装したかった…

$import および $include ディレクティブがコンパイル時に実行できない: import 式の CTFEability

D-YAML が CTFEable ではない: カスタムアロケーターと unsafe cast

今後の方針

まとめ

Discussion

`genCtor`: コンストラクタ生成 (template mixin)

各フィールドの代入文生成 (文字列 mixin, `static if`, CTFE)

`SumType` の変換: `static foreach` と `static immutable` フィールドを活用したディスパッチ

CWL パーサ生成: モジュール中の定義一覧から `documentRoot` を持つクラスを抽出

`$import` および `$include` ディレクティブがコンパイル時に実行できない: `import` 式の CTFEability