バイナリをパッケージングするのは実はとても楽しい

目次

• なぜこんなことをするのか？
• バイナリパッキングとは何か？
• スキーマ構文の設計
• 実装してみる
• データのエンコードとデコード
• コンパイラを作る
• 何が問題なのか
• 字句解析器を作る
• ASTとは何か？
• ASTを構築する
• 構文解析器を作る
• 意味解析器を作る
• 動的パッカー
• コード生成
• ビジターパターン
• CLIを作る
• おわりに

なぜこんなことをするのか？

Twitterで、データをJSONで保存するのは明らかに「真の™開発者」がやることじゃない、という議論を目にした。

ならば当然、私も「真の™開発者」にならなければならない。

そして辿り着いた答えは、バイナリだった。

そこで閃いた：

「自作のバイナリフォーマットを作るのって、どれくらい難しいんだろう？」

小さなwbがひとつあれば済む話でしょ。( ˶ˆᗜˆ˵ )

残念ながら、小さなwbひとつでは終わらなかった。

最終的に、JSONペイロードを80%削減するバイナリ・スキーマ言語を丸ごと作ることになった。

jBin

バイナリパッキングとは何か？

こんなデータがあるとする。

"hello world"

これをASCIIに変換すると

104 101 108 108 111 32 119 111 114 108 100
 h e l l o [SPACE] w o r l d

つまり h はASCIIで104になる。

これらのASCII値はすべて8ビットに収まるので、1文字あたり1バイトになる。

h e l
01101000 01100101 01101100 

l o [SPACE]
01101100 01101111 00100000 

w o r
01110111 01101111 01110010 

l d
01101100 01100100

これを少しのcで書ける：

FILE *f = fopen("file.bin", "wb");

unsigned char data[] = "hello world";
fwrite(data, 1, sizeof(data) - 1, f);

fclose(f);

簡単だ。では104を書いてみよう。

もちろん、104をそのままASCII文字として書くこともできる：

'1' '0' '4' → 49 48 52

しかし、1バイトで足りる数字が3バイトを占めている。

この2バイトを節約するには、デコーダに「これは整数であって文字列ではない」と伝える方法が必要になる。

ヘッダを足せばいいが、それで1バイト増えるだけだ（まあ、型がいくつあるかによる……128種類を超えていないことを祈る……超えたら、かなり厄介なことになる）。

よし！なら最初のバイトを型、2番目のバイトをデータにしよう。

[TYPE][DATA]

0がint、1がstringだとすると、104は

00000000 01101000

文字列なら……

00000001 01101000

おっと……

これではhしか得られない。

長さの異なるデータを表現する方法が必要だ。ならもう1バイト足して、文字列の長さを表そう。 するとバイナリはこうなる

[TYPE][LENGTH][DATA]

よし！これで文字列をこう表現できる：

 [TYPE] [LENGTH] [DATA]
(STRING) (11)
00000001 00001011 00...

h e l
01101000 01100101 01101100 

l o [SPACE]
01101100 01101111 00100000 

w o r
01110111 01101111 01110010 

l d
01101100 01100100

よし！これで文字列と整数をまとめてパックできる！ "userid": 123を表現したいとする。

これで全部まとめてパックできる

[TYPE:STRING][LENGTH:6][WORD:userid][TYPE:INT][LENGTH:-][DATA:123]

よし！123を1バイトの数字と2バイトのヘッダで表現できる。 でも待てよ、整数のLENGTHフィールドって実際には使ってないよな？ならなぜ必要？無駄なバイトじゃないか？

うーん……これを削ったら、バイナリリーダーはヘッダがどこで終わるかをどうやって知るんだ？

「ヘッダはここまで、ここから実データを読む」と示す何かが必要だ。

うーん。バイトの終わりを表すのに何が使えるだろう。

ヘッダ長のバイトとか？

いや。それは余分だ。長さフィールドを消したのに、また長さフィールドを足すことになる。

だが、ヘッダ自体の1ビットを使える。

1ビットでこう表せる：

「自分はヘッダの最後のバイトではない。まだ続きがある」

なぜLSBを使わないのか、と思うかもしれない。

それだと偶数しか表現できない。それは……あまり良くない。

だからMSBを使う。

するとタグはこんな感じになる：

[CONTINUATION BIT][7 BITS OF DATA]

continuation bitが1なら、ヘッダのバイトがもう1つある。 0なら、ヘッダはそこで終わり。

これを使えば、123はこう表現できる

[TYPE=0][DATA=123]

文字列ならこう。

[TYPE=1][LENGTH=11][DATA=104]...

型は1、長さは11。

でも待って……長さが127より大きかったら？7ビットでは127までしか表せない！

同じ手を使おう！ただし今度は整数に対して！

最初のビットが1なら、整数は続く。 128はこう書ける：

10000001 00000000
^
MSB / continuation bit

（ビッグエンディアン）

バイナリリーダーはこう動く：

• 最初のバイトを読む。
• MSBが1なので、もう1バイトある。
• 残りの7ビットは1。
• 2番目のバイトを読む。
• MSBが0なので、これが最後のバイト。
• 残りの7ビットは0。
• この2つの7ビット値を組み合わせて128を得る。

これがvarint（可変長整数）だ。

ここで使っているエンコーディングはリトルエンディアン：最下位の7ビットが先頭に来る。

10000000 00000001

なかなかいいだろう？同じバイナリの中に異なる型を表現できて、バイナリパーサーがそれをすべて正しく読み取ってくれる。

だが注意してほしい、データはフィールド単位で格納している。

[TYPE][DATA]
[TYPE][DATA]
[TYPE][DATA]

そしてほとんどのデータは、ただ漂うランダムな値の集まりではない。普通は構造を持っている。

Cのstructを例に取ろう：

struct {
 int i;
 char *s;
 int a[10];
}

32ビットシステムだと仮定する。

[32-bit int] [32-bit pointer] [10 × 32-bit ints]

毎回ヘッダ情報を付ける必要はない。struct自体からデータの型が分かるからだ。

うーん、バイナリデータにも同じことができるんじゃないか……

答えは、できる。

これがスキーマの役割だ！

このstructに対して、スキーマはこう書ける：

i: int
s: char *
a: list(int)

スキーマがあれば、値ごとに型情報を保存しなくても型が分かる。

バイナリフォーマットで型を気にする必要はもうない。考えるべきはデータのサイズだけだ！

これが protobuf のやり方だ。

次に、遭遇しうるさまざまなデータサイズを考えよう。

int、float、bool、string がある。

int と bool は varint として扱える。float は固定幅で、f32 か f64 だ。

string は別物だ。バイト列をそのまま varint にエンコードするわけにはいかない。そのバイト列こそが保持したい実データだからな。

だから読み始める前に、この string が何バイト占めるのかを知る必要がある。

するとエンコード型はこうなる：

• varint
• f32
• f64
• delimited

だが待て！各フィールドにはどうやってアクセスする？「あの string をくれ」では通じない。どれのことか指定しなければ。いいだろう、フィールドに番号を振ればいい。 順番にインデックスしてもいいし、ユーザーが自分で番号を指定してアドレス指定してもいい。これが field number の役割だ。

もう一つ気づくことがある。可能な型はたった4つしかない。

4つの値なら2 bit にちょうど収まる。

00 - varint 
01 - f32
10 - f64
11 - delimited

なかなか粋だろ。ならこれを直接エンコードして……field number に詰め込んでしまおう！

待て、どうやって詰め込む？

ちょっとしたバイナリの小技……いや、大したことじゃない。

ただくっつけるだけだ。

field number を2ビット左シフトして、その2 bit の型を入れる隙間を作り、型をその空きに OR で押し込む。

field number が10で、型が delimited だとしよう。

00001010 (10)

left shift that by 2

00101000

OR it with our type!

00101011

ほらな！この1バイトの数字が、型は何か、field number はいくつかを同時に教えてくれる！

だが、もう一歩踏み込んだら？

型はすでにフィールド番号に詰め込んだ。

なぜここで止める？

長さも詰め込んだら？

できる。

これで header に収まるのは

[FIELD NUMBER][LENGTH][TYPE]

全部ひとつの varint に収まった！！！！ ◝(ᵔᗜᵔ)◜

いいね。ただ一つだけ

これ、あまりにも面倒くさい。 文字列をパックするには、まず「これは区切りだ」と伝えて、長さを渡して、それからバイト列を渡す。毎。回。

そんなのは下々のやることだ。庶民のやること。我々はやらない。

なら解決策は明らか、schema 言語を丸ごと書けばいい。 データは schema ファイルに宣言して、フォーマットやエンコードの面倒は全部プログラムに押し付ける。

---

schema の構文を設計する

さて……魂を削らない構文を決めないとな（言ってるぞ、protobuf）

フィールド番号……あれは何だ？インデックスだろ。買い物リストにどうやって番号を振る？数字を書いて、項目を書く。 なら同じやり方でいいじゃないか！

だいたいこんな感じだ：

1. name

schema は型も表せないと。他の言語のやり方をそのまま真似て、こう書く：

1. name: type

悪くないだろ。 だが待て。message（struct）の終わりはどう表す？

{} でもいいが、格好悪いだろ。何を難しくする必要がある、ただのリストだ。リストには終わりがある。なら終わりを与えればいい。

message name:
 1. name:type
 2. name:type
 3. name:type
end

あと、インデントに意味を持たせるべきじゃない。インデントに敏感な言語はうっとうしい、ただの拷問だ。これはやらない。

では……セミコロンなしで、行の終わりはどう判断する？改行か？

それでもいいが、一行で書きたい人がいたら？醜いが、何らかの理由でそう書きたいとしよう。止めるな。でもセミコロンは醜い。

数字を使えばいい！ 数字の後にドットが来たら、それを新しい項目とみなす！

いいね。𐔌_ˊᵕˋ_𐦯

問題は……コンパイラが読むとき、あるフィールドが見つからなかったら？ そのままクラッシュしてもいい……全フィールドでそうしてもいいが、optional なフィールドは欲しいだろ。なら一番明快な道を行こう、こう書く：

 number. name: type = defaultValue

これは optional で、しかも直感的だ。

ここまで来たら、人が表したいさまざまなデータも考えておこう……

うん、明らかにいろんな種類の項目がある。

おっ、リストが要る。それに複数の選択肢から選ぶ方法も要る、つまり enum だ。 よし、考えよう……

おっ、関数みたいにできる、これが直感的だ。

 number. name: structure(type)

例えば：

 1. friends: list(People)

おっと待て、people って何だ？ああ、これも message であるべきだ。たぶんこう：

message People:
 1. name: string
 2. location: string
end

うーん……カスタム型も要るな……言語内で、すべてを順番に扱うのか？うーん、それは馬鹿げてる。後でパスを一回回して、すべての table を繋ぎ合わせ、その struct を参照させればいい。

おかげで自己参照もできる。パックするときは struct へのポインタになるからな！だからこう書ける：

message People:
 1. name: string
 2. location: string
 3. friends: list(People)

次は enum。パスが2回あるから、enum を message の外に直接置ける！どこで宣言しても関係ない！enum はこう宣言できる：

enum Name:
 number. name 
 number. name
 number. name
end

あと protobuf には enum を0から始めさせるやり方がある 本当にそれが要るのか？コンパイラはそこまで馬鹿で、それが分からないのか？コンパイラにデフォルトで処理させればいい

おっと待て……enum を表す何かが要るが、すべての型が同じわけじゃない。 そう、それは union だ。加えればいい、問題ない

 number. name: union(type, type, type...)

おっと待って……デフォルト値の話だ。union の中ではどう扱うんだ。

こんな union があったとして：

 number. name: union(i32, i64) = 10

10 が i32 なのか i64 なのか、これでは曖昧になる。 じゃあフィールドが見つからなかったときはどうする？

型の隣にデフォルト値を置けば解決する。

 number. name: union(i32 = 10, i64)

これでフィールドが見つからなければ、値 10 の i32 になる。

よし、次は何かをマッピングしたくなるだろう……だから追加する。

 number. name: map(key_type, value_type)

さらに package を宣言したり、何かをインポートしたりする構文も：

package "package name"

import "package"

ほら見ろ、なかなか綺麗な構文になった。組み合わせると：

package "com.game.core"
import "math.jbin"

enum Activity:
 1. active
 2. inactive
end

message Player:
 1. name: string
 2. health: i32 = 100
 3. weapons: list(string)
 4. connections: list(Player)
 5. activeStatus: Activity
 6. inventory: map(string, i32)
 7. balance: union(string="empty", i32)
end

おっと待てよ……これでもう完全な言語じゃないか……

ともかく、.proto で書くとこうなる。

syntax = "proto2";

package com.game.core;

import "math.proto";

enum Activity {
 ACTIVE = 1;
 INACTIVE = 2;
}

message Player {
 optional string name = 1;
 optional int32 health = 2 [default = 100];
 
 repeated string weapons = 3;
 repeated Player connections = 4;
 
 optional Activity active_status = 5;
 map<string, int32> inventory = 6;
 
 oneof balance {
 string empty = 7;
 int32 amount = 8;
 }
}

見てくれよ、これ。うわ。

---

そろそろ本当に実装する時だ

実装するにあたって、当然 C++ を選んだ。

「当然」なのは、履歴書に書けるものが欲しかったからで、Rust の借用チェッカーと格闘する気力はなかったからだ。もう年だし。

よし。設計はもう十分。動かす時だ。

まずはバイナリをエンコードしないといけない。

データのエンコードとデコード

varint のエンコードは、基本的にこうなる：

void encodeVariant(std::vector<uint8_t> &buffer, uint64_t value) {
 while (value >= 128) {
 uint8_t lower = value & 127; // 127 = 01111111
 lower |= 128;
 buffer.push_back(lower);
 value >>= 7;
 }
 uint8_t lower = value & 127;
 buffer.push_back(lower);
}

これで varint が組み上がる。値が 128 以上なら、下位 7 ビットを取り、最上位ビットを 1 にして「まだ続く」ことを示し、バッファに追加する。

次に値を 7 ビット右シフトして、繰り返す。

最後のバイトは、最上位ビットを 0 のままにする。

簡単だ。デコードはこれ：

uint64_t decodeVariant(const std::vector<uint8_t> &buffer, size_t &offset) {
 uint64_t result = 0;
 int shift = 0;
 while ((buffer[offset] & 128) != 0 && offset < buffer.size()) {
 uint8_t byte = buffer[offset++];
 byte &= 127;
 const uint64_t cast = static_cast<uint64_t>(byte) << shift;
 result |= cast;
 shift += 7;
 }
 uint8_t byte = buffer[offset++] & 127;
 const uint64_t cast = static_cast<uint64_t>(byte) << shift;
 result |= cast;
 return result;
}

LEB128 で varint をエンコード・デコードできるようになったから、次は tag（さっき話したヘッダーのメタデータ）をエンコード・デコードする。

void encodeTag(std::vector<uint8_t> &buffer, uint32_t fieldNumber,
 wiretype wiretype) {
 uint64_t val = (static_cast<uint64_t>(fieldNumber) << 2);
 val |= static_cast<uint64_t>(wiretype);
 encodeVariant(buffer, val);
}

void decodeTag(const std::vector<uint8_t> &buffer, size_t &offset,
 uint32_t &outFieldNumber, wiretype &outType) {
 uint64_t val = decodeVariant(buffer, offset);
 outType = static_cast<wiretype>(val & 3);
 outFieldNumber = val >> 2;
}

文字列用のヘルパーもいくつか：

void encodeString(std::vector<uint8_t> &buffer, uint32_t fieldNumber,
 const std::string &text) {
 encodeTag(buffer, fieldNumber, wiretype::Delimited);
 encodeVariant(buffer, text.size());
 buffer.insert(buffer.end(), text.begin(), text.end());
}

std::string decodeString(const std::vector<uint8_t> &buffer, size_t &offset) {
 uint64_t size = decodeVariant(buffer, offset);
 std::string result =
 std::string(buffer.begin() + offset, buffer.begin() + offset + size);
 offset += size;
 return result;
}

文字列のエンコードはこれで3つだけ：tag を書き、長さを書き、バイト列を書く。

信じられないかもしれないが、コアエンジンはほぼこれだけだ！あとはコンパイラと JSON 変換まわりだけ！٩(^ᗜ^ )و ´-

よし！バイナリエンコードが書き終わったから……次はコンパイラを作ろう。簡単なはず……だよな？

コンパイラを作る

そう、これはコンパイラだ。黙ってくれ、トランスパイラとは呼びたくない、コンパイラだ。定義はこう：

コンパイラとは、あるプログラミング言語（ソース言語）で書かれたソースコードを、元のコードの意味と動作を正確に保ったまま、別のプログラミング言語（ターゲット言語）に翻訳するコンピュータプログラムである。

我々のプログラムはまさにこれをやっている。コンパイラ原理主義者は消えてくれ。俺のプログラムは俺の schema を受け取り、それをバイナリかコードに翻訳する。

問題

我々の言語はなかなか可愛い。なかなか整っている。

残念ながら、コンピュータにはそれが何を意味するのか全く分からない。

ただのバイト列だ。

ならば、これらの記号に意味を与えよう！

我々の構文を持ってくる：

 1. name:string

構造はこうなっている：

number → dot → identifier → colon → type

そしてこれを使って、これらの項目の表現を組み立てる。これが Lexer の仕事だ。

Lexer を作る

そう、lexer は君が思っている通りのものだ。大きなループと if 文の山。 やることは一つだけ：我々のファイルを読み、これらの token を吐き出す。（AI のやつじゃない）

enum class TokenType {
 Keyword_Message,
 Keyword_Enum,
 Keyword_Optional,
 Keyword_Map,
 Keyword_Union,
 Keyword_End,
 Keyword_Package,
 Keyword_Import,
 Identifier,
 Number,
 StringLiteral,
 Comment,
 Equals,
 Colon,
 Comma,
 Dot,
 LParen,
 RParen,
 EndOfFile
};

では我々のファイル

message User:
 1. name: string
 2. id: i32

を tokenize した出力はこうなる：

 [Keyword_Message]
 [Identifier: "User"]
 [Colon]
 [Number: 1]
 [Dot]
 [Identifier: "name"]
 [Colon]
 [Identifier: "string"]
 [Number: 2]
 [Dot]
 [Identifier: "id"]
 [Colon]
 [Identifier: "i32"]
 [EndOfFile]

なかなかいい。これで parser は生の文字の山を解読する必要がなく、これらの token を直接扱えばいい。 parser がこれらを読み終えて本当に吐き出すのは AST（抽象構文木）だ。

AST とは？

これは我々がプログラムのデータを graphLang で表現する方法であり、そこでは文字通りツリーノードがすべてのデータを保持し、すべてのデータが一つの形しか持たない。 今回は schema をルートノードとして定義できる。今のところ messages と enums の2種類のメッセージしかないので、ヘッダーはこう定義できる：

struct Schema {
 std::vector<EnumDef> enums;
 std::vector<MessageDef> messages;
};

すると Schema がルートノードで、ツリーはこうなる：

 (Schema)
 / \
(enums) (messages)

AST を作る

では……enums と messages とは何か？上の定義から分かるように、struct の vector だ。 messages はこう定義できる：

struct MessageDef {
 std::string name;
 std::vector<Field> fields;
 int line = 0;
 std::string comment = "";
};

Field は：

struct Field {
 uint32_t number;
 std::string name;
 DataType type;
 bool isOptional = false;
 std::string defaultValue = "";
 int line = 0;
 std::string comment = "";
};

これで AST はこうなる：

Schema
└── messages
 └── MessageDef
 ├── name
 ├── line
 ├── comment
 └── fields
 └── Field
 ├── number
 ├── name
 ├── type
 ├── isOptional
 ├── defaultValue
 ├── line
 └── comment

あとは enum の定義：

struct EnumDef {
 std::string name;
 std::vector<EnumEntry> entries;
 int line = 0;
 std::string comment = "";
};

そして enum の項目：

struct EnumEntry {
 uint32_t number;
 std::string name;
 int line = 0;
 std::string comment = "";
};

よし！部品が全部揃った。AST は今こうなっている：

Schema
├── Enums
│ └── EnumDef
│ ├── name
│ └── entries
│ └── EnumEntry
│ ├── number
│ └── name
│
└── Messages
 └── MessageDef
 ├── name
 └── fields
 └── Field
 ├── number
 ├── name
 ├── type
 ├── isOptional
 └── defaultValue

parser を作る

これを使って parser を組む。そう、parser もループと if 文だ（厳密には再帰下降とか呼ばれるが、再帰は結局反復の別の形にすぎない）。

ループ全体は実に単純だ：

Schema Parser::parse() {
 Schema s;
 while (!isAtEnd()) {
 if (peek().type == TokenType::Comment) {
 consume();
 continue;
 }
 if (peek().type == TokenType::Keyword_Package) {
 consume();
 if (peek().type == TokenType::StringLiteral) {
 s.packageName = consume().value;
 } else {
 error("Expected string literal after package");
 }
 } else if (peek().type == TokenType::Keyword_Import) {
 consume();
 if (peek().type == TokenType::StringLiteral) {
 s.imports.push_back(consume().value);
 } else {
 error("Expected string literal after import");
 }
 } else if (peek().type == TokenType::Keyword_Message)
 s.messages.push_back(parseMessage());
 else if (peek().type == TokenType::Keyword_Enum)
 s.enums.push_back(parseEnum());
 else
 error("Unexpected token in global scope");
 }
 return s;
}

各型について、条件判定を並べて、対応する AST ノードを返す。 consume() は現在の token を返してポインタを一つ進め、peek() はポインタを動かさずに次の token のデータを渡す。

よし！テストしてみよう。

 message User:
 1. name: adfasdfasdfasdfasd
 2. id: 012349

parser が何と言うか見てみる：

「Mighty good mate! seems excellent innit? want a cuppa?」

うーん……つまり、ユーザーの文法が正しいかどうかだけでなく、これが筋が通っているかどうかも見るものが必要だ。

つまりファクトチェッカーが要る。いわば Twitter のコミュニティノートだ。

これこそ、我々のセマンティックアナライザがやっていることだ！

セマンティックアナライザを構築する

これを検証するために、2パスで進める。

• 1パス目では、すべてのシンボルを構築してテーブルに入れる。（要するに、認識可能な正当なものすべて）
• 2パス目では、構築したテーブルを使って AST を検証する。

void SemanticAnalyzer::analyze(const Schema &schema) {
 buildSymbolTable(schema);
 validateEnums(schema);
 validateMessages(schema);
 validateCyclicDependencies(schema);
}

2パスにしたおかげで、宣言の順序は関係なくなる。なかなかいい。

というわけで、validateMessages の間、adfasdfasdfasdfasd を見つけるとシンボルテーブルを調べ、その型が存在しないことを突き止めてエラーを投げる。フィールド番号 1 を二度使うとか、リストを map のキーにするとかいった、馬鹿げたことをしていないかもチェックする。

よし！ここまでで何ができたか見てみよう！

• すべてをトークンに刻む Lexer
• トークンを受け取って AST を構築する Parser
• AST を検証してエラーを投げるセマンティックアナライザ
• LEB128 を使ったエンコーダ／デコーダ

残るは2つだけ。

• JSON ファイルを動的にバイナリへ変換する
• schema からコードを生成し、各言語でネイティブに使えるようにする

動的パッカー

次は動的パッカーだ。schema を受け取り、JSON ファイルを受け取り、バイナリを構築する。

JSON のほうは nlohmann/json をそのまま使った。この上さらに JSON を自前でパースするのは、完全に無駄な寄り道になる。

これで JSON がメモリに載った。AST もメモリに載っている。あとは両者を一緒に走査するだけだ。

JSON パーサがキー “id”: 123 を見ても、何をすべきか分からない。そこで AST に聞く！AST が言うには、

「ああ、id ？それはフィールド番号 2 で、型は i32 だ。」

するとパッカーは encodeTag() と encodeVariant() の関数を呼び、バッファにバイトを吐き出す。

ここで何をやっていないかに気づいたか？C++ のコードは一切生成していない。ラッパー層も一切コンパイルしていない。JSON を読み、schema を読み、バイナリを動的に構築しただけだ。

protobuf なんかくたばれ

試してみよう！

{
 "name": "Pranav",
 "health": 100
}

これを JSON として保存すると、空白と引用符込みでおよそ 35 バイト。

これをバイナリに詰め込んでみる。

結果は……

9バイト

最高だ、これを見ろ！！！

74.29% の削減。

文字列がなければもっと小さくなる。9バイトのうち6バイトは “Pranav” という語に使われている。まあ、どうでもいい。

保存サイズは大幅に削れた。

デコードもずっと簡単だ。バイナリ自体が各フィールドが何かを教えてくれるので、デコーダは JSON の構文や型表現を扱う必要がない。

だが、実行時に動的ルックアップのコストを払いたくないなら？自分の言語の普通の struct が欲しいだけなら？

そこで AOT コード生成の出番だ。

コード生成

うーん……コードはどう生成する？AST はすでにあって、それがどんな形で、セマンティクス的に何なのかは分かっている。つまり、それをターゲット言語に翻訳するだけ……

cCodeGen() 関数を書いてクラスに追加し、呼び出せばいい。

Python のジェネレータが欲しい？簡単だ！pythonCodeGen を追加するだけ！

ああ、jsCodeGen() も要るな、分かった。話がそれた。なんで JavaScript なんて書くんだ。まあいい。

だが、言語の好みについて顧客は常に正しいらしい、たぶん。 分かった、このクラスは今の俺にはちょっと太りすぎだ。

だからこそ visitor パターンが必要なんだ！

Visitor パターン

で、visitor とは何か。後知恵で言えば、言語に代数的データ型がない不運な連中のためのデザインパターン製プラセボだ。cpp には std::variant があるのに、なんで使ったかって？分からん、どこかの記事で読んで、学んでみたかったんだ。

ともあれ。visitor パターンとは、呼び出し側と呼ばれる側の小さな握手だ。ここから型安全性が得られる。我々の実装では、呼び出し側が自分自身を渡し、visitor になる。呼ばれる側、つまり acceptor はその visitor を受け取り、visitor に対して関数呼び出しを行い、自分自身を渡して二重ディスパッチを引き起こす。巧妙ではある……が、こんな単純な問題には精神的負担が大きすぎる。

これを実現するには、ADT の struct を変更して、関数も持たせる必要がある。

void accept(SchemaVisitor &visitor) const;

そして抽象クラスを作り、そこに虚メソッドを並べ、各ジェネレータが実装する：

#pragma once
#include "Schema.hpp"

class SchemaVisitor {
 public:
 virtual ~SchemaVisitor() = default;
 virtual void visit(const Schema &s) = 0;
 virtual void visit(const MessageDef &m) = 0;
 virtual void visit(const EnumDef &e) = 0;
 virtual void visit(const EnumEntry &ee) = 0;
 virtual void visit(const Field &f) = 0;
};

たとえば C ジェネレータはこうなる：

#pragma once
#include "SchemaVisitor.hpp"
#include <ostream>
#include <string>

class CGenerator : public SchemaVisitor {
 private:
 std::ostream &out;
 std::string currentEnumName;
 const Schema* currentSchema = nullptr;

 public:
 CGenerator(std::ostream &outputStream) : out(outputStream) {}

 void visit(const Schema &schema) override;
 void visit(const MessageDef &message) override;
 void visit(const EnumDef &enumDef) override;
 void visit(const EnumEntry &ee) override;
 void visit(const Field &field) override;
};

C ジェネレータはこれらの関数をオーバーライドし、対応する visit でそれぞれの処理をこなすだけだ：

void CGenerator::visit(const EnumDef &enumDef) {
 currentEnumName = enumDef.name;
 out << "typedef enum {\n";
 for (const auto &ee : enumDef.entries) {
 ee.accept(*this);
 }
 out << "} " << enumDef.name << ";\n\n";
}

ee.accept(*this) を呼ぶと、これが実行される：

void EnumEntry::accept(SchemaVisitor &visitor) const { visitor.visit(*this); }

これは CGenerator.visit(ee) を呼ぶだけなので、CGenerator の environment entry 用の visit が呼ばれる。

void CGenerator::visit(const EnumEntry &ee) {
 out << " " << currentEnumName << "_" << ee.name << " = " << ee.number << ",\n";
}

これを各型について繰り返す。コードはこうやって生成される。

よし！テストしてみよう……

おっと待った、テストできない。まだ実行できない。CLI が要る。

CLI を構築する

CLI には jarro2783/cxxopts を使った。手書きでパースしたくなかった。これも json もなかなか面白いプロジェクトだから、いずれ別でやるとして、今はこの2つのライブラリで済ませる。

このライブラリがあれば、CLI を組むのはかなり楽だ。多くのものがすぐ使える。

自分で書く必要があるのはオプションだけ。

options.add_options()("command", "Command to run (e.g. build, pack)",
 cxxopts::value<std::string>())(
 "input", "Input schema file", cxxopts::value<std::string>())(
 "o,out",
 "Output (target language for build, or output binary file for "
 "pack)",
 cxxopts::value<std::string>())("j,json",
 "Input JSON file (for pack command)",
 cxxopts::value<std::string>())(
 "m,msg", "Root message name to pack (for pack command)",
 cxxopts::value<std::string>())("h,help", "Print usage");

 options.parse_positional({"command", "input"});
 auto result = options.parse(argc, argv);

動くし、調子もいい。これらのオプションは if 文の山で処理している（今思えば、このプロジェクトのコードの大半も、ループ一つに if の山だ）。

if (command == "build") {
 if (!result.count("input")) {
 std::cerr << "Error: No input file specified." << std::endl;
 return 1;
 }
 if (!result.count("out")) {
 std::cerr << "Error: --out flag is required (e.g., --out c)."
 << std::endl;
 return 1;
 }

 std::string inputFile = result["input"].as<std::string>();
 std::string targetLang = result["out"].as<std::string>();

 std::ifstream file(inputFile);
 if (!file.is_open()) {
 std::cerr << "Error: Could not open file " << inputFile
 << std::endl;
 return 1;
 }

 std::stringstream buffer;
 buffer << file.rdbuf();
 std::string schemaText = buffer.str();

 std::vector<Token> tokens = tokenize(schemaText);
 Parser parser(tokens);
 Schema schema = parser.parse();

 SemanticAnalyzer analyzer;
 analyzer.analyze(schema);

 if (targetLang == "c") {
 CGenerator cGen(std::cout);
 schema.accept(cGen);
 } else if (targetLang == "py" || targetLang == "python") {
 PythonGenerator pyGen(std::cout);
 schema.accept(pyGen);
 } else {
 std::cerr << "Code generation for '" << targetLang
 << "' is not supported yet!" << std::endl;
 }

ともあれ、試してみよう。

schema はこう書く：

package "com.mmo.game"

enum Faction:
 1. alliance
 2. horde
 3. neutral
end

message Vector3:
 1. x: i32
 2. y: i32
 3. z: i32
end

message InventoryItem:
 1. itemId: i32
 2. quantity: i32
 3. isSoulbound: bool
end

message Character:
 1. id: i64
 2. name: string
 3. level: i32
 4. faction: Faction
 5. position: Vector3
 6. inventory: list(InventoryItem)
 7. attributes: map(string, i32)
end

あとは build を実行して、出力に c を選ぶ……結果は：

#pragma once
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

typedef struct Vector3 Vector3;
typedef struct InventoryItem InventoryItem;
typedef struct Character Character;

typedef struct {
 InventoryItem* data;
 size_t length;
 size_t capacity;
} jbin_list_InventoryItem;

typedef struct {
 char** keys;
 int32_t* values;
 size_t length;
 size_t capacity;
} jbin_map_char_ptr_int32;

typedef enum {
 Faction_alliance = 1,
 Faction_horde = 2,
 Faction_neutral = 3,
} Faction;

struct Vector3 {
 int32_t x;
 int32_t y;
 int32_t z;
};

struct InventoryItem {
 int32_t itemId;
 int32_t quantity;
 bool isSoulbound;
};

struct Character {
 int64_t id;
 char* name;
 int32_t level;
 Faction faction;
 Vector3 position;
 jbin_list_InventoryItem inventory;
 jbin_map_char_ptr_int32 attributes;
};

見てくれ！！プログラムはもう何にも依存していない。必要なものはすべてこの schema が供給している！！！

（注：これは生成された完全な C ファイルではない。中にはメッセージ単位の pack/unpack 関数、setter と getter、そして encode/decode 関数が大量にある）

json ファイルを渡してバイナリにエンコードすることもできる。

{
 "id": 123456789,
 "name": "LeroyJenkins",
 "level": 60,
 "faction": "alliance",
 "position": {
 "x": 100,
 "y": 200,
 "z": 300
 },
 "inventory": [
 { "itemId": 999, "quantity": 1, "isSoulbound": true },
 { "itemId": 45, "quantity": 100, "isSoulbound": false }
 ],
 "attributes": {
 "strength": 120,
 "agility": 45
 }
}

この json のサイズは 401 bytes

これをバイナリにパックすると、ファイルサイズは……

80 bytes!

80%削減

80.05%

結論

というわけで、こうなった。最初は腹いせに JSON を保存しようとしただけなのに、気づいたら字句解析器、構文解析器、AST、意味解析器、動的バイナリパッカー、そして多言語コード生成器まで書き上げていた。正直に言うと、バイナリのパッキングはなかなか面白かった。

とにかく、リポジトリを見てほしい。

jBin