機械学習やデータ処理をやっていると、一部だけ Python では遅すぎるので C, C++, Rust のような高速な言語で処理を書きたくなることがまれによくあります。
C++ なら [pybind11](https://github.com/pybind/pybind11)、Rust なら [PyO3](https://github.com/PyO3/pyo3) が非常に有名で、これらをつかえばかなり簡単に Python <-> C++ / Rust を相互に行き来する処理を書くことができます。

と、ここまでは昔の知識で把握していたのですが、最近改めて必要に迫られて Rust で Python Extension を書こうとドキュメントを読んでいたところ、更に簡単にそういった処理を書けるようにする開発ツールである [maturin](https://github.com/PyO3/maturin) なるものがリリースされているのを知りました。

## セットアップ

[Maturin User Guide](https://maturin.rs/) がきちんとしているので、わざわざ使い方を書く必要もないのですが、

```sh
$ maturin new --bindings pyo3 foo
$ tree foo
.
├── Cargo.toml
├── pyproject.toml
└── src
 └── lib.rs
```

で新規プロジェクトを生成できます。
pyproject.toml は、以下のようになっており、 `build-system` が指定されているため、もうこの時点で `pip install <name>` すれば Python から使える状態になります。
(ref. [PEP517](https://www.python.org/dev/peps/pep-0517/), [PEP518](https://www.python.org/dev/peps/pep-0518/))

```toml
[build-system]
requires = ["maturin>=0.12,<0.13"]
build-backend = "maturin"

[project]
name = "foo"
requires-python = ">=3.6"
classifiers = [
 "Programming Language :: Rust",
 "Programming Language :: Python :: Implementation :: CPython",
 "Programming Language :: Python :: Implementation :: PyPy",
]
```

ちなみに `Cargo.toml` があるので `cargo build` したくなるのですが、それはできません。 (あんまり調べてないですが、Python 関連のシンボルが undefined になってビルドに失敗する。)
代わりに `maturin develop` でビルド + 現在アクティブになっている virtualenv へのインストールを行います。
(`maturin develop --release` でリリースビルドができる。)

Rust コードだけでなく Python wrapper も同時に開発するようなケースでは、 `pip install -e foo` をつかうほうが便利かもしれません。
Python wrapper 側の変更だけならビルドしなおす必要がなくなり、即座に反映されるようになります。
(Rust 側をいじったときはビルドしなおす必要がある。)

## 配布

まだ自分で使っている範囲では PyPI に publish することはなく、プロジェクト内ローカルなパッケージとして使用しているだけなので、基本的には上記のようなコマンド群だけで開発が完結しているのですが、maturin では配布のことも考えたユーティリティも用意されています。

`maturin build` で配布用の wheel を生成できるのですが、これがまた便利そうで、システムに存在しているすべての Python バージョンに対して wheel を生成してくれます。
たとえば、仮に現在アクティブな virtualenv が Python 3.10 系だとしても、Python 3.9 系がインストールされているシステム上で `maturin build` をすると、3.9, 3.10 用の wheel をそれぞれビルドしてくれるのです。

さらに、もろもろセットアップが必要ですが、クロスコンパイルのための仕組みも充実しており、 `maturin build --universal2` で macOS 用の universal binary (x86_64, arm 両対応)を出力したり、 `maturin build --target=...` でクロスコンパイルしたりできます。

さらにさらに Python の Native Package のお作法である manylinux 対応(特定の動的ライブラリとしかリンクしないことで、いろんな Linux 環境でうごくことを保証する) もビルドオプションで解決可能です。 (`maturin build --release --target aarch64-unknown-linux-gnu --zig`。 ここで zig がでてくるのにちょっと感動しました。)

[Docker イメージ](https://hub.docker.com/r/konstin2/maturin) や [GitHub Actions](https://github.com/messense/maturin-action) もすでにコミュニティによってサポートされており、CI 上でも簡単に build & publish ができそうです。

## まとめ

Python だと遅いけど C++ や Rust でかいてブリッジするのも面倒だし、そこまでやるのは大袈裟かなーとかおもって結局 Python のままいったり Cython, numba でいったりする、という経験をいままで何度かしてきました。
が、maturin が想像以上に体験が良く、開発効率もよかったので、今後はより気軽に Python プロジェクトに Rust をつっこんでいくスタイルが通用しそうだなと思いました。

また、Rust は効率追いもとめたいときには本当に優秀なツールだと改めて実感しました。PyO3 もめちゃくちゃ良くできていて、混み入ったアルゴリズムだったら Rust で書いたほうが、開発効率的にも好ましいんじゃないかと思います。

maturin でさくっと Rust 製 Python 拡張を書く

Rust でシグナルハンドリングをする必要があったのですが，あまり自分の用途にあるライブラリがなかったので作りました．
僕が Windows のことをほとんどわからないので，Windows 未対応です．

[github.com](https://github.com/agatan/signal-notify)

[docs.rs](https://docs.rs/signal-notify/0.1.2/signal_notify/)

[https://crates.io/crates/signal-notify](https://crates.io/crates/signal-notify)

golang の `signal.Notify` に寄せた API になっていて，標準ライブラリの `std::sync::mpsc::{Sender, Receiver}` 経由でシグナルを待ち受けることができます．

```
extern crate signal\_notify;
use signal\_notify::{notify, Signal};
use std::sync::mpsc::Receiver;

fn main() {
 let rx: Receiver<Signal> = notify(&[Signal::INT, Signal::USR1]);
 for sig in rx.iter() {
 match sig {
 Signal::INT => {
 println!("Interrupted!");
 break;
 }
 Signal::USR1 => println!("Got SIGUSR1!"),
 }
 }
}

```

Rust で Unix シグナルを取るライブラリとしては [GitHub - BurntSushi/chan-signal: Respond to OS signals with channels.](https://github.com/BurntSushi/chan-signal) というのが有名です．
こちらは標準ライブラリの `mpsc::channel` ではなく，`chan` クレイトの `channel` を使っています．
`chan` クレイトはケースによってはかなり便利で，

1. 複数の consumer を作れる (`receiver.clone()` ができる)
2. `chan_select!` マクロによって golang の `select` 的なことができる

という利点があります．

一方で複数 consumer にする必要がない & `chan_select!` が必要ないケースでは，シグナルハンドリングのためだけに `chan` にも依存するのもなんとなくはばかられるという気持ちがありました．
また，自分の目的として「`SIGWINCH` と `SIGIO` が取りたい」というのがあったのですが，`chan-signal` の仕組みだとデフォルトで無視されるシグナルをキャッチできない(macOS だけ)という問題もありました．
報告するときに方法を考えていたのですが，あまり自信がなかったのとほとんど完全に仕組みを書きなおす形になりそうだったので，自分の手元で `std::sync::mpsc` を使って実験してみたという経緯です．

## 仕組み

1. 初期化時にパイプを作る
2. シグナルごとに通知すべき `Sender` を覚えておく
3. シグナルごとに `sigaction` でハンドラをセットする
 - シグナルが来たらそれをパイプに `write(2)` する
4. シグナル待受＆通知用のスレッドを起動する
 - パイプからシグナル番号を読んで，適切な `Sender` に `send` する

という仕組みで動いています．
自信がなかったのは，「シグナルハンドラでやっていいこと一覧」をちゃんと把握していないという点です．
一応 `sigaction` の man を見ると `write` は読んでもいい関数一覧にいる気がするし，実際動いてはいるのでセーフだろうと判断しました．
（もしアウトだったら教えてください）

ちなみに `chan-signal` の方は，

1. シグナルごとに通知すべき `Sender` を覚えておく
2. 監視用スレッドを起動し，メインスレッドでは `pthread_sigmask` を使ってシグナルをブロックする
 - シグナルがすべて監視用スレッドに渡るようにする
3. 監視用スレッドで `sigwait` して適切な `Sender` に `send` する

という仕組みで動いているようです．
`sigwait` は指定したシグナルが投げられるまでブロックします．
ただし，macOS で `sigwait` の man を見ると，

> Processes which call sigwait() on ignored signals will wait indefinitely. Ignored signals are dropped immediately by the system, before delivery to a waiting process.

とあって，無視されるシグナルを `sigwait` で待っても補足できないようです．
Linux の man を見るとそんなことは書いていないし，普通に動くっぽいです．

今の実装だと，シグナルを受け取る `Receiver` がすべて閉じても，監視スレッドは動き続けるしハンドラも残り続けるので，これはなんとかしたいなぁと思っています．
アプリケーションの実行時間のうち，ある期間だけシグナルをとってそれ以外はスルーしたいというケースもそんなにないかなというのと，内部的な変更にしかならないので API が変わらないというのがあるので，この状態でとりあえず public にしました．

CLI を書いていると意外と普通に `SIGINT` は取りたくなることがあると思うので，ぜひ使ってみてください．
issue 報告等お待ちしています．

---

---

Rust で Unix のシグナルを channel 経由でキャッチする

プログラムを書いていると何かしら木構造っぽいものやグラフっぽいものを作りたい場面が多々あると思います．
Rust は所有権や `Size` の都合で，これらを作ろうと思うと地味にハマるのでまとめておきます．

### Rust で木構造

最も単純な木構造は Rust だと

```
enum Tree<T> {
 Leaf(T),
 Node(Box<Tree<T>>, Box<Tree<T>>),
}

```

といった形で表せます．
Rust では明示的に boxing してあげないと再帰的なデータ構造は作れないのでちょっと複雑に見えるかもしれませんが，まぁ単純です．

この木構造を書き換えたい場合は，ownership をとって書き換えた値を返すこともできますし，`&mut Tree<T>` をとって in-place に書き換えることもできます．

```
fn inc(&mut self) {
 match *self {
 Tree::Leaf(ref mut i) => *i = *i + 1,
 Tree::Node(ref mut left, ref mut right) => {
 left.inc();
 right.inc();
 }
 }
}

fn inc2(self) -> Tree<i32> {
 match self {
 Tree::Leaf(i) => Tree::Leaf(i + 1),
 Tree::Node(left, right) => Tree::Node(Box::new(left.inc2()), Box::new(right.inc2())),
 }
}

```

### Rust で有向非巡回グラフ

有向非巡回グラフ構造は，グラフのエッジに向きがあり，かつ循環がない構造で，これは割りと単純に表現できます．

```
struct Node<T>(T, Vec<Rc<Node<T>>>);

```

`Node` は自身の値 `T` と，つながっているノードの `Vec` を持ちます．(対象問題によっては `Vec` ではなくて `HashMap` とか `HashSet` とか)

`Rc` は参照カウント方式のスマートポインタです．
グラフでは，`Node` は複数の `Node` から参照される可能性があるので， `Box` は使えません．

これを変更可能にしたい場合はちょっと面倒ですが `RefCell` を使う必要があります．

Rust では基本的に mutable borrow は常にひとつしか存在できず，mutable borrow が生きている間は immutable borrow もつくることができません．
`Rc` から mutable な参照を取り出すこともできません．

そこで `RefCell` を使うことで borrow check をランタイムに行うようにします．
`RefCell` は immutable な参照から mutable な参照を取り出せるようにする働きをしますが，
mutable な参照を取っている間に，さらに mutable な参照を作ろうとしたり immutable な参照を作ろうとすると，ランタイムに `panic` します．
コンパイル時検査ではなくランタイム検査になるので，プログラマの責任できちんと管理しないと死にます．

`RefCell` 版がこちら

```
struct Node<T>(T, Vec<Rc<RefCell<Node<T>>>>);

impl Node<i32> {
 fn inc(&mut self) {
 self.0 += 1;
 for n in &self.1 {
 n.borrow\_mut().inc();
 }
 }
}

```

### Rust で巡回有向グラフ

循環がある場合は厄介です．
Rust で参照を共有するための `Rc` は参照カウントなので，循環参照があるとリークします．
したがって循環のある構造を表すために `Rc` は使えません．

木構造で親を参照するポインタを子に持たせておきたいといったケースでは，親は子を `Rc` で持ち，子は親を `Weak` で持つという形で対応できますが，
グラフだとそういうわけにもいきません．

そこで出て来るのが `Arena` という方法です．

オブジェクトの実体は `Arena` の中に作り，グラフにはその ID を持たせて管理します．

```
type NodeId = usize;

struct NodeArena<T> {
 arena: Vec<Node<T>>,
}

impl<T> NodeArena {
 fn alloc(&mut self, value: T) -> NodeId {
 let id = self.arena.len();
 let node = Node(id, value, Vec::new());
 self.arena.push(node);
 id
 }
 fn get(&self, id: NodeId) -> &Node<T> {
 &self.arena[id]
 }
 fn get\_mut(&mut self, id: NodeId) -> &mut Node<T> {
 &mut self.arena[id]
 }
}

struct Node<T>(NodeId, T, Vec<NodeId>);

```

こんな感じです．

こうすることでコンパイル時の borrow check を諦めることなくグラフ構造を作ることができます．

(`i` と `i+1` 番目のノードを同時に mutable に参照したいとかは苦しいですが)

欠点としては単純に間接的な表現でめんどくさいというのもありますが，GC がないので参照されなくなったオブジェクトも `Arena` 上で生き続けてしまうことです．
そのため，動的に要素が生きたり死んだりするケースには使いにくいです．

ノードグラフの構築が終わったら `Arena` をリフレッシュするみたいなことをすると良いのかもしれません．
(構築中は `Vec` で `Arena` を表現して，構造が固まったら `HashMap` を使った `Arena` に切り替えて参照されている id だけを残すみたいな)

それでも構築中はオブジェクトがあまりまくるので辛いですね...

---

---

Rust でグラフ構造や木構造を作る

Rust の非同期 IO ライブラリのなかでももっとも低レベルなレイヤーを担っている [mio](https://github.com/carllerche/mio) を使って echo サーバを書いた。
echo サーバばっかり書いているような気がするけど，echo サーバやっておくと簡単な割にライブラリの使い方とかがちゃんと分かる気がするので好きです。

### コード

```
extern crate mio;

use std::io::prelude::*;
use std::collections::HashMap;

use mio::*;
use mio::tcp::{TcpListener, TcpStream};

#[derive(Debug)]
struct ClientsHolder {
 table: HashMap<Token, TcpStream>,
 free\_token: Vec<Token>,
 next\_max\_token: Token,
}

impl ClientsHolder {
 fn new\_from(start\_token: Token) -> Self {
 ClientsHolder {
 table: HashMap::new(),
 free\_token: Vec::new(),
 next\_max\_token: start\_token,
 }
 }

 fn next\_token(&mut self) -> Token {
 if let Some(tok) = self.free\_token.pop() {
 return tok;
 }
 let tok = self.next\_max\_token;
 self.next\_max\_token = Token(tok.0 + 1);
 tok
 }

 fn register(&mut self, tok: Token, client: TcpStream) {
 self.table.insert(tok, client);
 }

 fn get\_mut(&mut self, tok: Token) -> Option<&mut TcpStream> {
 self.table.get\_mut(&tok)
 }

 fn remove(&mut self, tok: Token) -> Option<TcpStream> {
 let result = self.table.remove(&tok);
 if result.is\_some() {
 self.free\_token.push(tok);
 }
 result
 }
}

// Setup some tokens to allow us to identify which event is
// for which socket.
const SERVER: Token = Token(0);

fn main() {

 let addr = "127.0.0.1:13265".parse().unwrap();

 // Setup the server socket
 let server = TcpListener::bind(&addr).unwrap();

 // Create an poll instance
 let poll = Poll::new().unwrap();

 // Start listening for incoming connections
 poll.register(&server, SERVER, Ready::readable(), PollOpt::edge())
 .unwrap();

 // Create storage for events
 let mut events = Events::with\_capacity(1024);
 let mut clients = ClientsHolder::new\_from(Token(1));

 loop {
 poll.poll(&mut events, None).unwrap();

 for event in events.iter() {
 match event.token() {
 SERVER => {
 // Accept and drop the socket immediately, this will close
 // the socket and notify the client of the EOF.
 let (stream, \_) = server.accept().unwrap();
 let tok = clients.next\_token();
 poll.register(&stream, tok, Ready::readable(), PollOpt::edge()).unwrap();
 clients.register(tok, stream);
 }
 tok => {
 let mut close = false;
 if let Some(mut stream) = clients.get\_mut(tok) {
 let mut buf = [0; 1024];
 let n = stream.read(&mut buf).unwrap();
 if n == 0 {
 poll.deregister(stream).unwrap();
 close = true;
 } else {
 stream.write(&buf[0..n]).unwrap();
 }
 }
 if close {
 clients.remove(tok);
 }
 }
 }
 }
 }
}

```

面倒だったので `unwrap` まみれですが。

## やったこと

`mio` の全体の流れとしては，`Poll` 型の値がイベントを監視する役割を担います．
`Poll` に監視対象を登録していき，`Poll::poll` でイベントの発火を待ちます．
発火したイベント一覧が `Events` 型の `Events::iter` で取れるので，対応していけばよいです．

`mio` では `Token` という型の値を使って監視対象を識別しています．
監視対象には `TcpListener` ，`TcpStream`，`Sender`，などなどいろんなものがあるので，統一的に扱うために `Poll` は `Token` だけを保持します．
`Token` と監視対象の紐付けはユーザ側の責任でやってくれという感じみたいです．

echo サーバではクライアントの数は不特定なので，「空いている `Token` を探す」と「`Token` に対応するクライアント (`TcpStream`) を探す」がうまくできる必要があります．
そこで，`ClientsHolder` を定義しました．
こいつが，空いている `Token` を返すのと `Token` をキーに `TcpStream` を返す仕事をします．
`remove` されたらその `Token` は再利用します．

## 気になるところ

`mio` はファイルに対する抽象化は提供しない方針のようです．
`STDIN` / `STDOUT` も同様です．

ファイル IO もノンブロッキングにしたい場合はどうしたらいいんでしょう？よくわかっていない．
`mio::unix` 以下に UNIX 限定の拡張がおいてあって，`EventedFd` という file descriptor を扱う実装はあるので，UNIX 限定なら力技でなんとかなるのかもしれない．

あと `mio` は関係ないんですが，実装の部分で，

```
let mut close = false;
if let Some(mut stream) = clients.get\_mut(tok) {
 let mut buf = [0; 1024];
 let n = stream.read(&mut buf).unwrap();
 if n == 0 {
 poll.deregister(stream).unwrap();
 close = true;
 } else {
 stream.write(&buf[0..n]).unwrap();
 }
}
if close {
 clients.remove(tok);
}

```

というのがあるんですが，これどうやったらスマートなんでしょう．
`close = true` としている部分で `clients.remove(tok);` をやるのが普通だと思うんですが，`if let Some(mut stream) = clients.get_mut(tok) {` のところで `clients` は borrow されているから mutable borrow はこれ以上作れないのです．

---

---

mio で echo サーバメモ

ちょっとはまったのでメモ

```
struct A {
 foo: Vec<i32>,
 bar: Vec<bool>,
}

```

こんな構造体があったとする。
普通、`A` の所有権を分解して `foo` と `bar` にしたいときは

```
fn xxx(x: A) -> (Vec<i32>, Vec<bool>) {
 let A { foo, bar } = x;
 (foo, bar)
}

```

とやれば良い（この例だともっと簡単に書ける気もするけど）

一方、`Box<A>` から `foo` と `bar` に分解したい場合は話が変わってくる。

```
fn error1(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
 (x.foo, x.bar)
}

fn error2(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
 let A { foo, bar } = *x;
 (foo, bar)
}
```

これらは両方共コンパイルできない。
人間から見ると，`Box<A>` は `A` の所有権を持っているのだから、`A` -> `foo/bar` に分解できるなら `Box<A>` も同様にできる気がする。

実際にはこのようにするとコンパイルが通る。

```
fn success(x: Box<A>) -> (Vec<i32>, Vec<bool>) {
 let x = *x;
 let A { foo, bar } = x;
 (foo, bar)
}
```

うーん、エラーになるケースだと `Deref` トレイトの機能を経由している感じになるのかな？
`Deref` 経由で `foo` の所有権をとるとその時点で `Box<A>` の所有権は奪われちゃうから `bar` の所有権が取れないということなのだと想像した。
`success` のようなコードが突然出てきたら混乱しそうだ。

---

---

Rust で Box に包まれた構造体の所有権分解

Rust には失敗するかもしれない値を表す `Result<T, E>` という型があります。
[std::result::Result](https://doc.rust-lang.org/std/result/enum.Result.html)

そして iterate できることを表す `Iterator` という trait があります。
[std::iter::Iterator](https://doc.rust-lang.org/std/iter/trait.Iterator.html)

また、`Iterator` trait は要素型を表す関連型を持ちます。~~例えば `String` は `Iterator<Item=char>` を `impl` しています。これは `char` 型を要素にもつ `Iterator` であることを意味します。~~
ここ間違っていました。`String` が直接 `Iterator` を `impl` しているのではありませんでした。

たまに `Iterator<Item=Result<T, E>>` のようになっている型を見かけます（T, E にはなにかしら具体的な型が入っていると思ってください）。
例えば、`std::io::stdin().bytes()` の返り値である [std::io::Bytes](https://doc.rust-lang.org/stable/std/io/struct.Bytes.html) は `Iterator<Item=Result<u8>>` を `impl` しています。
（ちょっとわかりにくいのですがここでの `Result` は `std::result::Result` ではなくて `std::io::Result` です。`std::io::Result` は `std::result::Result<T, std::io::Error>` のエイリアスです。）

さて、このような `Iterator` からすべての要素が `Ok(_)` であれば `Ok<Vec_>>` を、`Err(_)` があれば `Err<_>` を返すような処理を書きたいということは割りとよくあります。
で、これを一生懸命実装しようとしていたのですが、標準ライブラリの範囲内ですでに実装されていました。べんり。

```
let result = std::io::stdin().bytes().collect::<Result<Vec<\_>, \_>>();

```

これだけです。これで要件を満たす `Result<Vec<_>, _>` が返って来ます。すばらしい。

タネは簡単な話で `Result` が `FromIterator` trait を `impl` しているので `collect` で変換が可能であるというお話でした。
[std::iter::FromIterator](https://doc.rust-lang.org/stable/std/iter/trait.FromIterator.html)

---

---

Rust の Result と Iterator

Rust のパーサコンビネータライブラリの一つである [Marwes/combine: A parser combinator library for Rust](https://github.com/Marwes/combine) を使ってみています．

詳しい使い方はきちんとしたドキュメントがあるのでそちらを参照してください．

ざっくりいうと Haskell の [parsec: Monadic parser combinators | Hackage](https://hackage.haskell.org/package/parsec) の Rust 版という感じです．

(ちなみに私も combine を参考に C++ でパーサコンビネータを作ってみたりしました. )
[agtn.hatenablog.com](http://agtn.hatenablog.com/entry/2016/04/30/003009)

で、このライブラリ、とてもジェネリックなコードで書かれているので、かなりコンパイル時間が増加します… (Boost.Spirit 系に近いです． コンパイルエラーなどは遥かに読みやすいのであまり困ることはないですが)

パーサを書いている時にはテストは頻繁に行いたいので，ちょっとコンパイルがおそいのはつらい．

なにか解決策はないかなぁと思っていたら本家に issue がたっていました．

[Extremely long compile times · Issue #21 · Marwes/combine](https://github.com/Marwes/combine/issues/21)

今回この issue にかかれていた内容を検証してみたので，ここでまとめておこうと思います．

## 結論

パーサの定義を，ジェネリックな構造体のメソッドとして定義するとコンパイル時間が大幅に短くなる

## 方法

まずはじめに言われているのは，入力ストリーム型を`I: Stream<Item=char>` から `&str` にしてしまうという方法です．

> (It might be possible to specialize the parsers directly as well, say
> `fn expr(input: State<&str>) -> ParseResult<Expr, &str>`
> instead of
> `fn expr<I: Stream>(input: State) -> ParseResult<I, &str>`
> )

これは作ったパーサをジェネリックな入力に対して適用することができなくなりますが，ライブラリの利用者側としては，`char` のストリームといったらだいたい `&str` だと思うので，ぶっちゃけジェネリックじゃなくてもいいじゃんという感じです．

そしてもう一つが, ジェネリックな構造体を作って，パーサの定義をその中に閉じ込めるという方法です．

ちょっとこちらはコード例を実際に見たほうがわかりやすいと思うので後で説明します．

## 実験コード

というわけで，

1. ジェネリックなパーサ
2. &str のみを受理するパーサ
3. ジェネリックな構造体の中に定義されたジェネリックでないパーサ

の三種類について，コンパイル時間をはかってみます．

パーサ界のハローワールド，計算機で実験してみます．
まずはジェネリックなパーサです．

```
use combine::*;
use combine::primitives::Stream;

pub fn integer(input: State) -> ParseResult<i64, I>
 where I: Stream<Item = char>
{
 many1::<Vec<\_>, \_>(digit())
 .map(|is| is.into\_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64)))
 .parse\_state(input)
}

pub fn factor(input: State) -> ParseResult<i64, I>
 where I: Stream<Item = char>
{
 between(char('('), char(')'), parser(expr)).or(parser(integer)).parse\_state(input)
}

pub fn term(input: State) -> ParseResult<i64, I>
 where I: Stream<Item = char>
{
 let op = char('*').or(char('/')).map(|c| {
 move |lhs, rhs| match c {
 '*' => lhs * rhs,
 '/' => lhs / rhs,
 \_ => unreachable!(),
 }
 });
 chainl1(parser(factor), op).parse\_state(input)
}

pub fn expr(input: State) -> ParseResult<i64, I>
 where I: Stream<Item = char>
{
 let op = char('+').or(char('-')).map(|c| {
 move |lhs, rhs| match c {
 '+' => lhs + rhs,
 '-' => lhs - rhs,
 \_ => unreachable!(),
 }
 });
 chainl1(parser(term), op).parse\_state(input)
}

pub fn parse(input: I) -> Result<(i64, I), ParseError>
 where I: Stream<Item = char>
{
 parser(expr).parse(input)
}

```

それぞれの関数が一つのパーサの役割を担います．それぞれのパーサが独立していて，それぞれ別々に型変数を導入しています．

次に `&str` だけを受け取るパーサです．これは上記のジェネリックなパーサの，型変数を `&str` に置き換えるだけなのでとても簡単です．

一部だけ掲載します．

```
pub fn expr(input: State<&str>) -> ParseResult<i64, &str> {
 let op = char('+').or(char('-')).map(|c| {
 move |lhs, rhs| match c {
 '+' => lhs + rhs,
 '-' => lhs - rhs,
 \_ => unreachable!(),
 }
 });
 chainl1(parser(term), op).parse\_state(input)
}

pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> {
 parser(expr).parse(input)
}

```

最後が，ジェネリックな構造体のメソッド中に，ジェネリックでないパーサを定義して閉じ込める方法です．

```
use combine::*;
use combine::primitives::Stream;
use std::marker::PhantomData;

 truct P(PhantomData<fn(I) -> I>);

impl P where I: Stream<Item = char> {
 pub fn integer(input: State) -> ParseResult<i64, I> {
 many1::<Vec<\_>, \_>(digit())
 .map(|is| is.into\_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64)))
 .parse\_state(input)
 }

 pub fn factor(input: State) -> ParseResult<i64, I> {
 between(char('('), char(')'), parser(P::::expr))
 .or(parser(P::::integer))
 .parse\_state(input)
 }

 pub fn term(input: State) -> ParseResult<i64, I> {
 let op = char('*').or(char('/')).map(|c| {
 move |lhs, rhs| match c {
 '*' => lhs * rhs,
 '/' => lhs / rhs,
 \_ => unreachable!(),
 }
 });
 chainl1(parser(P::::factor), op).parse\_state(input)
 }

 pub fn expr(input: State) -> ParseResult<i64, I> {
 let op = char('+').or(char('-')).map(|c| {
 move |lhs, rhs| match c {
 '+' => lhs + rhs,
 '-' => lhs - rhs,
 \_ => unreachable!(),
 }
 });
 chainl1(parser(P::::term), op).parse\_state(input)
 }
}

pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> {
 parser(P::expr).parse(input)
}

```

言葉で説明すると難しいのですが，型変数を導入する部分を構造体の定義部分だけにしてあげることで，型変数をそれぞれのパーサが別々に導入する必要がなくなっています．

コードも割りとすっきりしますね．

## 結果

上記をコードを `cfg` を使ってコンパイル時に切り替えながらコンパイルしてみました．

本当はきちんと繰り返し計測すべきですが，ちょっとサボっています．まぁ何度実行してもだいたい同じくらいになったので許してください．

| 実装方法 | コンパイル時間 |
| -------------- | -------------- |
| ジェネリック | 2.666s |
| `&str` | 1.70s |
| 構造体内で定義 | 1.55s |

このような結果になりました．

つまり，先ほどの issue で述べられているコンパイル時間の短縮方法はかなり効き目があるということですね．

構造体の中に閉じ込める方法が，`&str` しか受理しないようにする方法よりもはやくコンパイルできるのは意外でした… 参照を引数にとると暗黙に lifetime 変数が導入されたと記憶しているので，その関係なのかな？

構造体内で定義する方法では，`&str` 以外の入力ストリーム型を受けつけることを可能にしつつもコンパイル時間を短縮できるということで，積極的にこの方式でパーサを定義するべきということがわかりました．

注意点として，構造体内で別のパーサを呼ぶときには，必ず `P::term` という形ではなく，`P::::term` という形で呼び出すようにする必要があるようです．

きちんと明示的に指定しないと，結局型推論するはめになって意味がないということのようです．

---

COMMENT:
AUTHOR: anevaden
EMAIL: pgbsajrq@gmail.com
URL: http://cialisvipsale.com
IP: 60.173.69.118
DATE: 03/24/2018 13:14:29

Regards. Quite a lot of posts.

tadalafil 20 mg [cialis tablets australia](http://cialisvipsale.com)
interactions for cialis [http://cialisvipsale.com](http://cialisvipsale.com)
cialis 5mg prix [cialis generico](http://cialisvipsale.com)
cialis dose 30mg

---

---

Rust のパーサコンビネータライブラリ combine を使う時の tips


- `if` 文が値を返す
- `return` 文を持つ

以上のような特徴を持つ言語はどういう感じでコンパイルされるのか知りたくて，Rust について調べてみました．

Rust では以下の様なことが出来ます．

```
fn f() {
  let x = if cond {
    return None;
  } else {
    1
  };
  ...
}

```

Scala とかもできると思います．`cond` が真だった場合は，`x` の値を返すのではなく，関数から抜けてしまうという意味です．

これを Rust ではどんな LLVM IR に落とし込んでいるのか．

# `return` 文がない場合

```
fn noreturn(x: isize) -> isize {
  x
}

```

最も単純な場合です．この場合，生成される LLVM IR は，

```
define internal i64 @\_ZN4hoge8noreturn17h811bf1a871f85432E(i64) unnamed\_addr #0 {
entry-block:
  %x = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  ret i64 %1
}
```

となります．
名前がマングルされていますが，上記の `noreturn` 関数です．
やっていることは単純で，第一引数を読み込んで返すだけです．

# `return` に相当する文が一つのみの場合

```
fn onereturn(x: isize) -> isize {
  let y = if x == 0 {
    1
  } else {
    x
  };
  return x;
}

```

実際に値を返す部分が一箇所しかない場合です．途中に分岐があっても最終的に一箇所になっていれば多分同じ結果になります．

```
define internal i64 @\_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed\_addr #0 {
entry-block:
  %x = alloca i64
  %y = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-18-, label %else-block

then-block-18-:                                   ; preds = %entry-block
  store i64 1, i64* %y
  br label %join

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %y
  br label %join

join:                                             ; preds = %else-block, %then-block-18-
  %4 = load i64, i64* %x
  br label %clean\_ast\_10\_

return:                                           ; preds = %clean\_ast\_10\_
  ret i64 %4

clean\_ast\_10\_:                                    ; preds = %join
  br label %return
}
```

`return` という BasicBlock ができています．これは `return` 文が現れると作られるよう？です．
で，その中では単純に `x` に該当する値を返しています．

最後の `return x;` 文を 単純に `x` に置き換えてみると，

```
define internal i64 @\_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed\_addr #0 {
entry-block:
  %x = alloca i64
  %y = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-18-, label %else-block

then-block-18-:                                   ; preds = %entry-block
  store i64 1, i64* %y
  br label %join

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %y
  br label %join

join:                                             ; preds = %else-block, %then-block-18-
  %4 = load i64, i64* %x
  ret i64 %4
}
```

となります． `return` ブロックが消えていますね．なので `return` 文があると `return` ブロックが作られる、で良さそう？

# 複数のパスから値を返す

```
fn multireturn(x: isize) -> isize {
  let y = if x == 0 {
    return -1;
  } else {
    x
  };
  y
}

```

さて，では最初に述べた，`if` の分岐内にある `return` についてです．
これは，

```
define internal i64 @\_ZN4hoge11multireturn17had379e8ce5a18f08E(i64) unnamed\_addr #0 {
entry-block:
  %sret\_slot = alloca i64
  %x = alloca i64
  %y = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-18-, label %else-block

then-block-18-:                                   ; preds = %entry-block
  store i64 -1, i64* %sret\_slot
  br label %return

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %y
  br label %join

join:                                             ; preds = %else-block
  %4 = load i64, i64* %y
  store i64 %4, i64* %sret\_slot
  br label %return

return:                                           ; preds = %join, %then-block-18-
  %5 = load i64, i64* %sret\_slot
  ret i64 %5
}
```

こうなりました．
まず，`return` 文があるため？，`return` ブロックが作られています．
しかし今回は，パスによって返すものが違います．(値が違うという意味ではなく，同じ変数ですらないという意味です...)

よく IR を読むと，関数の頭で `%sret_slot` という名前でスタック領域を確保していることがわかります．
そして，`return` ブロック内では，これを読んできて返しています．

さらに，`if` 文の then 節にあたる，`then-block-18-` というブロックでは，`%sret_slot` に値を格納して `return` ブロックへジャンプしています．
else 節のあとの部分 (`join` ブロック) でも同様に, `%sret_slot` に値を格納して `return` ブロックへジャンプしています．

# まとめ

というわけで，様々な Rust コードを LLVM IR に変換して見てみた結果，複数のパスから値を返す場合は，「ローカル変数として返り値を定義し，そこに返したい値を格納してから `return` に goto」という形になっていることがわかりました．

(ほとんど LLVM IR を乗っけるだけになってしまった...)

## ちなみに ...

# `if` 文の返す値をそのまま返す

```
fn ifreturn(x: isize) -> isize {
  if x == 0 {
    1
  } else {
    x
  }
}

```

Rust に慣れていないとちょっとわかりにくいですが，`x == 0` の場合は 1 を返し，そうでない場合は `x` を返す関数です．

これは，

```
define internal i64 @\_ZN4hoge8ifreturn17hcdaab6e376d6c95cE(i64) unnamed\_addr #0 {
entry-block:
  %sret\_slot = alloca i64
  %x = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-15-, label %else-block

then-block-15-:                                   ; preds = %entry-block
  store i64 1, i64* %sret\_slot
  br label %join

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %sret\_slot
  br label %join

join:                                             ; preds = %else-block, %then-block-15-
  %4 = load i64, i64* %sret\_slot
  ret i64 %4
}
```

こうなります．やっていることは上記の例たちとあまり変わりません．
しかし，`return` 文がないので？，`return` ブロックが作られていません．が, `%sret_slot` は定義されていますね...

これはどういうことなんでしょう．`rustc` のコードを読むべきなのかもしれませんが，イマイチ内部処理が想像しにくいです...

普通に翻訳していったら，

```
let x = if x == 0 { 1 } else { x };
x
```

と同じ感じになる気がするので，`%sret_slot` という名前が出てくる余地は無い気がするのですが...(実質同じ処理ではあります)
分岐が直接返戻値になる場合は特別扱いしているのかな？

---

---


↗ agatan blog ↗

#Rust