頭打ち

　プログラミングの学習を始めて4箇月（10月は何もしていないので実質3箇月）が経ちました。
　何一つ身についた気がしません。やはり、学習だけでなく実践も必要ではないのかと思うようになりました。
　そこで、ソフトウェアの作成に挑戦することにしました。

ソフトウェア

解析器

　初めてのソフトウェアは、カレンダーや簡易電卓などのくだらないものではなく、できるだけ実用的で汎用的なものにしたいと思います。できれば長く改良していけるようなものが望ましいです。
　候補として思いついたのは、
・スレッドセーフなlogger
・設定ファイルの解析器
・namespace, chrootおよびcapabilityによるjail環境
です。
　今回は、最も汎用性が高そうな設定ファイルの解析器を作ることにしました。

C言語

　言語は、C言語を使いたいと思います。
　理由は、設計が古く多くの問題を抱えているからです。それらの問題を克服するために考えられた色々な仕組みは、新しい言語へと結実しています。
　逆説的ですが、最新言語の学習のために、一度は地獄を体感しておくのも悪くないでしょう。

設定ファイル

形式

　設定ファイルの形式についてネットで調べたところ、数え切れないほど見つかりました。
　それらの中で比較的定義がはっきりしていたのは、XML、JSON、ini（およびこれらの派生）でした。
　まずは、これらを候補とし、どれを採用するかを検討しました。

XML

　XMLは、厳密性が魅力的ですが規模が大きすぎます。特にDTDではなくSchemaを実装するとなると、手に負えません。これに初めてのソフトウェアで挑むのはただのアホです。

JSON

　JSONは、データ受渡しのための直列化の形式としてはともかく、設定ファイルの形式には向いていないと思います。
　その具体的（および個人的）な理由は以下の通りです。　
・コメントをつけることができない。
　説明文や設定例を併記できないのは致命的な欠点だと思います。
・割当て（付値）をコロンで表現する。
　等号のほうが一般的でわかりやすい、と個人的には思います（MACアドレスやIPv6アドレスなどのように、コロンは設定値に含まれる場合があり紛らわしい）。
・変数名（識別子）を二重引用符で囲む必要がある。
　いちいち面倒くさいし見た目も美しくない、と個人的には思います。
・重複する設定が上書きされる。
　一般的に、設定ファイルに意図して重複した設定を記述することは考えられません。重複は、誤記である可能性が非常に高いです。
　JSONではこれらの誤記が見逃されてしまいます。

ini

　ini（およびその派生）には、例えば、Cargo.tomlファイル（rustのあれです）があります。
　この形式は、最も読み易かったのですが、ただ一つ階層構造の記法が気に入りませんでした。
　iniでは階層構造をセクションのドット記法で表現します。
　例えば、神奈川県横浜市（または川崎市）のような構造は、iniでは、

[kanagawa]
[kanagawa.yokohama]
   wards = 18
[kanagawa.kawasaki]
   wards = 7

となります。
個人的には、これよりもJSONのように、

kanagawa = {
   yokohama = {wards = 18}
   kawasaki = {wards = 7}
}

と、入れ子にするほうが分かり易いと思います。

独自形式

　以上のように、既存の形式はどれも趣味に合わなかったので、独自に作ることにしました。

僕が考えた最強の設定ファイル！

　基本的には、iniを参考にJSONを改良した合の子です。なので、本ソフトウェアの解析器はJSONファイルの解析を行うことができます（完全に互換ではありません。#が予約語などの制限があります）。

字句

まずは、字句的な部分について説明します。

区切り文字

　カンマもしくはセミコロン、または改行（詳しくは後述）です。
　はじめはカンマだけにしていましたが、配列の区切り文字としてセミコロンが使われることもあるので、両方を採用しました。

コメント

　#から行末まではコメントとして扱われます。
　これは、Unixにおける一般的な設定ファイルと同じです。

ホワイトスペース

　空白とタブは無視されます。
　この扱い方は、設定ファイルに限らずソフトウェア全般における暗黙の了解事項ではないでしょうか。
　あぁ、モンティパイソン好きな某言語は違いましたね。ところで、モンティパイソンって、メンバーが高学歴であるという予防線を張っているのがクソダサいですね。「面白さが理解できない？それはお前が低学歴だからだよ！」はい、そうですか。

改行（行末）

　改行は、基本的には無視しますが、区切り文字として扱う場合があります。
　以下に具体例を示します。

person = {              #ここの改行は無視する
   name = "佐野 聡"      #ここの改行は区切り文字として扱う
   age = 41,            #ここの改行は無視する
   alive = true
}

　このようにした理由は、一つはUnixの設定ファイルのように、名前と値を羅列するだけの書き方を可能にしたかったからです。
　もう一つは、行末のカンマが美しくないという審美的な理由です。
　この要件のために構文解析が格段に難しくなったのですが、挑戦の意味もあり敢えて入れました。

トークン

　字句解析の結果は、以下の構造体my_tokenによる双方向リストとして表されます。

struct my_token {
   uint64_t type;
   union {
      int64_t int64;
      double float64;
      char *string;
   };
   struct location {
     size_t line;
     size_t column;
   } loc;
   struct my_token *prev;
   struct my_token *next;
};

　なお、構造体locationは、エラーが生じたときに位置を特定するためのものです。字句解析とは関係ありません。

構文

　次に構文的な部分を説明します（一部、字句についての説明もあります）。

テーブル

{one = 0x01, two = "弐", three = 3.0}

　テーブルは、JSONのオブジェクトに相当します。
　テーブルは、波括弧に囲まれた0以上の組からなります（空も可）。
　組は等号で結ばれた名前と値からなります（JSONとの互換性のために等号の代わりにコロンも使えるようにしました）。組同士は、区切り文字で区切られます。
　設定ファイルは、少なくとも一つのテーブルを有します（このテーブルをトップレベルと呼びます）。

struct my_pair {
   struct my_string *key;
   struct my_value *value;
   struct my_pair *next;
};
struct my_table {
   struct my_pair *head;
   struct my_pair *tail;
};

　取り敢えずは、テーブルをリストとして実装しました。
　この実装では、挿入がO(1)、探索と削除がO(N)です。削除はともかく探索に時間が掛かるのはよろしくありません。
　ボトルネックになるようなら木構造やハッシュ表（テーブルの名称はこれにするつもりだったから…）にしたいと思います。

名前（キー）

name
"n a m e"

　名前は、連続する文字の列か、二重引用符で囲まれた文字列です。
　これは、JSONの二重引用符が煩わしいので、省略可能にしたものです。
　ただし、名前の中に空白を入れることができるように、二重引用符の記法も残しました。

値

　値は、文字列、整数、浮動小数点数、ヌル、真理値、配列、テーブルのいずれかです。つまり、テーブルと配列は入れ子にすることができます。

struct my_value {
   uint64_t type;
   union {
      struct my_array *array;
      bool boolean;
      struct my_string *string;
      int64_t int64;
      double float64;
      struct my_table *table;
      void *nil;
   };
};

　typeの型をuint64_tにしたのは、unionと同じ大きさにしたかったからです。大きさを揃えることでAoSにおけるunion要素のアドレス計算が楽になります（不用意な型変換はバグの原因となるのでやらないでしょうが）。

文字列

"これはstringです"

　文字列は、二重引用符で囲まれた文字の列です（字句解析で処理されます）。

struct my_string {
   size_t len;
   uint8_t *seq;
};

　実装では、C言語の標準関数と互換性を考慮して、seqの末尾に番兵（'\0'）を配置しています。

整数

-123
0xff

　整数は、10進記法または、接頭辞0xによる16進記法（接尾辞hによる記法は、あまり見ないので止めました）で記述された符号および数字（aからfの文字）の列です（字句解析で処理されます）。
　実装では符号付き64ビット整数にしました。記法は関数strtollに依存しています。

浮動小数点数

0.1010101

　浮動小数点数は、小数点を含む10進記法で記述された符号および数字の列です（字句解析で処理されます）。
　実装では倍精度の浮動小数点にしました（明示的に64bitを指定したかったのですが、方法が分かりませんでした）。記法は関数strtodに依存しています。

真理値

true
False

　真理値は、trueとfalseであり、大文字、小文字は区別されません（字句解析で処理されます）。
　yesとnoを入れるか否かで迷ったのですが、他にもonとoffやenableとdisableなど切りがないので入れないことにしました。

配列

[0, 1, 2, 3]
["0"; "1"; "2"; "3"]

　配列は、角括弧に囲まれ区切り文字で区切られた0以上の値からなります（空も可）。値は、括弧内での順番により順序づけられています。
　角括弧やセミコロンの区切り文字は、octave（或いは元のMATLAB）の記法を真似たものです。
　JSONやiniと違い「配列の要素は同じ種類の値でなければならない」という制限を付けました。この制限はJSONとの互換性を大きく損なうので止めるかもしれません。

　実装についてはまだ迷っています。素直に実装すると、

struct my_array {
   size_t len;
   struct my_value **data;
};

になります。実装を隠蔽しない場合はこれが無難な気がします。
　他の案としては、

struct my_array {
   uint64_t type;
   size_t len;
   void *data;
};

があります。
　この案の利点は、以下の通りです。
　・typeが一つで済むので、確保すべき記憶領域が第一案と比べて約半分になります。
　・整数や浮動小数点数を要素とする場合に、型キャストだけで要素を取り出すことができます。
　・要素が文字列の場合も、オフセット（8バイト）と、ストライド（16バイト）により容易にアクセスできます（行儀が悪いのでやるべきではないかもしれません）。実際にはコンパイラによる埋め草を考慮しないといけないので、各バイト値はoffsetofとsizeofで求めなければなりません。

　欠点は、以下の通りです。
　・値が同一種類でなければならないという制限が付きます。
　・連続する記憶領域を割り当てる必要があります（少し面倒）。字句解析で確保した記憶領域の使い回しもできません（コピーが必要）。
　・定義が直感的ではないので、実装の隠蔽が前提となるでしょう。そのため、所謂accessor関数や、map関数およびreduce関数などを準備する必要があります。

略記法

　読み書きし易くするために、二つの略記法を導入しました。

・トップレベルのテーブルは、名前と波括弧を省略できるようにしました。
これは、Unixの一般的な設定ファイル（度々登場するが一体何のことやら）に近づけるためのものです。

# 略記なし
top_level = {
   timeout = 30
   log_file = "/var/log/server.log"
   server = {
      host = "192.168.0.1"
      port = 80
      keep_alive = false
   }
}

# 略記
timeout = 30
log_file = "/var/log/server.log"
server = {
   host = "192.168.0.1"
   port = 80
   keep_alive = false
}

改めて比べると前者でも悪くないような...

・要素が一つの無名テーブルは、波括弧を省略できるようにしました。
これは、いちいち括弧を付けるのが面倒だったからです。また、括弧がないほうが読み易く感じます。

# 略記なし
行動 = [
   {x移動 = 2.5},
   {y移動 = -1.0},
   {回転 = 60},
]

# 略記
行動 = [
   x移動 = 2.5
   y移動 = -1.0
   回転 = 60
]

まとめ

　なんだか、独自形式の説明をしたいのか、実装の苦労を語りたいのか、よく分からないグダグダな文章になってしまいました。
　ですが、「ゴミでも積極的に投稿」がnoteの基本方針なので、これで良いでしょう。

今後の予定

ポンプの補題

　これを機会に形式言語について学びたいですね。
　「僕の考えた最強設定ファイル！」の文法（言語）が何型なのか証明することが当面の目標になるでしょうか。