RustでFlatBuffersのコンパイラを作り始めた話

Who am I?
---------

- @termoshtt (Twitter/GitHub/Qiita)
- Rustで数値計算するためのOSSとか作ってる
    - accel (GPGPU for Rust)
    - rust-numpy
    - ndarray-linalg (LAPACK)
- rust-math
    - intel-mkl-src / rust-fftw3 / rust-sfmt

![ぐだフェリス.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30426/3726a6ed-cf6c-e4e7-9402-ebfcc8b161a3.png)

----

FlatBuffersとは？
----------------

- Cross-Platform serialization library
- Serialize data **without** parsing/unpacking
- Strongly Typed
- Protocol Buffersのようにスキーマから各言語のコードを生成
    - 仮想テーブルを使うことであとから拡張可能に
- Googleが2014年にOSS化 (Apache license)

-----

Who uses FlatBuffers?
----------------------
- cocos2d-x (2D Game framework)
- Facebook (for client-server communication in their Android app)
- Apache Arrow (cross-language development platform for in-memory data)
- TensorFlow Lite

----

FlatBuffers schema
------------------
```:electric.fbs
    namespace Eclectic;

    enum Fruit : byte { Banana = -1, Orange = 42 }
    table FooBar {
        meal      : Fruit = Banana;
        density   : long (deprecated);
        say       : string;
        height    : short;
    }
    file_identifier "NOOB";
    root_type FooBar;
```
flatccのサンプルより（後述）

---

公式でRustサポートしてないの？
------------------------

- FlatBuffers 1.10 (2018/10)からRust/Dart/Lua/Lobsterがサポート
- 公式のコンパイラflatc (C++実装) からRustのコードが出力できる
- Cには別実装がある
    - flatcc: FlatBuffers Compiler and Library in C for C
- 今回はFlatBuffersの構成の理解とPure Rust実装が欲しかったので作ってみることに
    - 外部コマンドに依存するのは面倒

-----

没案：flatc-gen
---------------
Protocol Buffersみたいにflatcの実行もコンパイル時にやってしまいたい

```rust
use flatc_gen::flatc_gen;
flatc_gen!("../fbs/addressbook.fbs");
```

- proc-macroで実行すれば良いのでは！？
- コンパイル時にflatcをGitHubからダウンロードしてコンパイルしてRustのコードを生成してマクロとして展開する
    - flatc-gen: Procedural macro for FlatBuffers compiler
    - proc-macro中で相対パスを取れないのであきらめる
- build.rsで生成するやつはあるっぽい
    - https://github.com/frol/flatc-rust

----

rflatc
------
ゼロからコンパイラ作ることに
https://github.com/termoshtt/rflatc

- rflatc
    - combine3でパーサーを作成
    - コード生成は実装中...
- fbs: rflatc Runtime
    - バイナリのパーサーは完了
    - バイナリのビルダーは未着手...

----

FlatBuffers Binary format
-------------------------

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30426/c3572766-2901-284e-1317-7e506129b9e1.png)

- データのパースとビルダーはfbsが担当
- rflatcは`*.fbs`ファイルからVTableの正しい位置にアクセスするためのコードを生成
- `std::alloc`が（部分的に）安定化されてるので32bit-alignedなバッファーも確保できる

```rust
#[repr(C, align(32))]
#[derive(Debug)]
struct Table {
    vtable_offset: i32,
    data: [u8],
}

#[repr(C, align(16))]
#[derive(Debug)]
struct VTable {
    vtable_length: u16,
    table_length: u16,
    offsets: [u16],
}
```

-----

combine3：パーサコンビネーター
---------

```rust
/// enum_decl = ( enum ident [ : type ] | union ident ) metadata { commasep( enumval_decl ) }
fn enum_<I>() -> impl Parser<Input = I, Output = Stmt>
where
    I: Stream<Item = char>,
    I::Error: ParseError<I::Item, I::Range, I::Position>,
{
    string("enum")
        .skip(spaces())
        .and(identifier())
        .skip(spaces())
        .and(optional(token(':').skip(spaces()).and(ty()).map(|x| x.1)))
        .skip(spaces())
        .and(paren(sep_by1(enumval(), token(',').skip(spaces()))))
        .skip(spaces())
        .map(|(((_, id), ty), values)| Stmt::Enum(Enum { id, ty, values }))
}
```

---

まとめ・感想
------
- RustでFlatBuffersのコンパイラ作り始めて、バイナリパースまでは出来た
- FlatBuffersは数値計算とも相性が良さそう
- パーサコンビネータは人類の英知