C++ で手書きパーサーを作るメモ

## 背景

設定ファイルとか小規模なもののパーサーは PEG, BNF とかで記述したことがある.

グラフィックスのシーンファイルフォーマットなど, データサイズがおおきい(e.g. 100MB)と PEG ライブラリなど使うと性能があまりよくない. またデバッグも大変.

グラフィックス関連だとだいたい型が決まっている, もしくは変数定義のときに型を指定するので, 後続のパースがどの型になっているかが既知である. e.g.

```
float[] a = [1, 2, 3.0, 4.0];
``` 

この場合 `a` までパースした段階で float の配列だとわかるので, 後続は float 配列に対するパーサーを使えばよい.
しかし, PEG 系とかだと一旦パースしたものに対して(e.g. any 型), float かどうかのチェックを入れたりが必要になりめんどい.

また上記データサイズと絡んで, パースしたら C++ の型に直接復元したいときがある

手書きでパーサーを書くのを考えてみます.

多言語データ(e.g. UTF-16, UTF-32)な文字列のパースはとりあえずは考えないことにします(UTF-8 を想定)

## 構成

基本は PEG 系 + Haskell Parser combinator 系とします.

Haskell になりますが,

Write Yourself a Scheme in 48 Hours
https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours

あたりを読んだり実装しておくと理解深まります.

文字を位置文字づつ読んでいき, パターンにマッチするかどうか判定, マッチしなかったら必要な文字数ぶん戻ってやりなおし.

メモ化とかは考えません.

上記グラフィックス関連のデータだとあまりパース失敗による手戻りというのがあまりないので, naiive な実装にしてもそんなに性能に影響は無いはず.

## 例

https://github.com/syoyo/tinyusdz/blob/dev/src/ascii-parser.cc

## StreamReader

まず, データ(文字列配列)に対して, n 文字進むとか, -n 文字戻るとかできるクラスが要ります.

c++ `stringstream` でもいいかもですが, メモリ上のデータに対して処理したい(endian swap も内包したい)ため, 自前のを用意しました.


```c++
class StreamReader {
 public:
  explicit StreamReader(const uint8_t *binary, const size_t length,
                        const bool swap_endian)
      : binary_(binary), length_(length), swap_endian_(swap_endian), idx_(0) {
    (void)pad_;
  }

  bool seek_set(const uint64_t offset) const {
    if (offset > length_) {
      return false;
    }

    idx_ = offset;
    return true;
  }

  bool seek_from_current(const int64_t offset) const {
    if ((int64_t(idx_) + offset) < 0) {
      return false;
    }

    if (size_t((int64_t(idx_) + offset)) > length_) {
      return false;
    }

    idx_ = size_t(int64_t(idx_) + offset);
    return true;
  }

  size_t read(const size_t n, const uint64_t dst_len, uint8_t *dst) const {
    size_t len = n;
    if ((idx_ + len) > length_) {
      len = length_ - size_t(idx_);
    }

    if (len > 0) {
      if (dst_len < len) {
        // dst does not have enough space. return 0 for a while.
        return 0;
      }

      memcpy(dst, &binary_[idx_], len);
      idx_ += len;
      return len;

    } else {
      return 0;
    }
  }
  bool read1(uint8_t *ret) const {
    if ((idx_ + 1) > length_) {
      return false;
    }

    const uint8_t val = binary_[idx_];

    (*ret) = val;
    idx_ += 1;

    return true;
  }

  bool read_bool(bool *ret) const {
    if ((idx_ + 1) > length_) {
      return false;
    }

    const char val = static_cast<const char>(binary_[idx_]);

    (*ret) = bool(val);
    idx_ += 1;

    return true;
  }

  bool read1(char *ret) const {
    if ((idx_ + 1) > length_) {
      return false;
    }

    const char val = static_cast<const char>(binary_[idx_]);

    (*ret) = val;
    idx_ += 1;

    return true;
  }

  bool read2(unsigned short *ret) const {
    if ((idx_ + 2) > length_) {
      return false;
    }

    unsigned short val =
        *(reinterpret_cast<const unsigned short *>(&binary_[idx_]));

    if (swap_endian_) {
      swap2(&val);
    }

    (*ret) = val;
    idx_ += 2;

    return true;
  }


  bool read4(uint32_t *ret) const {
    if ((idx_ + 4) > length_) {
      return false;
    }

    uint32_t val = *(reinterpret_cast<const uint32_t *>(&binary_[idx_]));

    if (swap_endian_) {
      swap4(&val);
    }

    (*ret) = val;
    idx_ += 4;

    return true;
  }

  bool read4(int *ret) const {
    if ((idx_ + 4) > length_) {
      return false;
    }

    int val = *(reinterpret_cast<const int *>(&binary_[idx_]));

    if (swap_endian_) {
      swap4(&val);
    }

    (*ret) = val;
    idx_ += 4;

    return true;
  }

  bool read8(uint64_t *ret) const {
    if ((idx_ + 8) > length_) {
      return false;
    }

    uint64_t val = *(reinterpret_cast<const uint64_t *>(&binary_[idx_]));

    if (swap_endian_) {
      swap8(&val);
    }

    (*ret) = val;
    idx_ += 8;

    return true;
  }

  size_t tell() const { return size_t(idx_); }
  bool eof() const { return idx_ >= length_; }

  const uint8_t *data() const { return binary_; }

  bool swap_endian() const { return swap_endian_; }

  size_t size() const { return length_; }

 private:
  const uint8_t *binary_;
  const size_t length_;
  bool swap_endian_;
  char pad_[7];
  mutable uint64_t idx_;

```

## 整数

overflow や underflow のエラーも扱いたいとなるとちょっとめんどいです.

`atoi` や `stoul` などではきちんと扱ってくれません.

また, 例外を出したくないときもあります.
既存の atoi を参考に実装してみました.

https://github.com/syoyo/tinyusdz/blob/dev/src/external/jsteemann/atoi.h



## 浮動小数点数

### Lexing

https://github.com/syoyo/tinyusdz/blob/bd27c68addf1a01473472b9d0ec9ddf4187ca00e/src/usda-parser.cc#L276

### パース

文字列表現から浮動小数点数を復元(およびその逆), 正確にやるには結構めんどいです.

https://github.com/ulfjack/ryu

ryu か, 

https://github.com/fastfloat/fast_float

高速 JSON パーサー simdjson で有名な Lemire 先生の fast_float を使うといいでしょう.



## error 報告

読んだ位置を記録しておくことで, エラー報告はまあまあやりやすいと思います.
clang とかみたいに範囲を指定してエラー報告とか, typo かも?みたいなのをやろうとするとめんどいかもです.

## expected

パースエラーになったらエラーメッセージなどがほしい.

std::optional だとそのような仕組み作るのが面倒です.

std::expected を使います!(標準入りが検討されているがまだ)

C++11 などの場合は expected-lite 使いましょう.

https://github.com/martinmoene/expected-lite

例として double 文字列のパースは以下のようになります.

```c++
static nonstd::expected<double, std::string> ParseDouble(const std::string &s) {
  // Pase with Ryu.
  double value;
  Status stat = s2d_n(s.data(), int(s.size()), &value);
  if (stat == SUCCESS) {
    return value;
  }

  if (stat == INPUT_TOO_SHORT) {
    return nonstd::make_unexpected("Input floating point literal is too short");
  } else if (stat == INPUT_TOO_LONG) {
    return nonstd::make_unexpected("Input floating point literal is too long");
  } else if (stat == MALFORMED_INPUT) {
    return nonstd::make_unexpected("Malformed input floating point literal");
  }

  return nonstd::make_unexpected("Unexpected error in ParseFloat");
}
```

## 実装

あとはひたすらルールを手書きしていけばいけます!