Rust でグラフ構造や木構造を作る
プログラムを書いていると何かしら木構造っぽいものやグラフっぽいものを作りたい場面が多々あると思います．
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だけを残すみたいな)
それでも構築中はオブジェクトがあまりまくるので辛いですね...
mio で echo サーバメモ
Rust の非同期 IO ライブラリのなかでももっとも低レベルなレイヤーを担っている 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 はこれ以上作れないのです．
NCurses の Crystal binding を作った
この記事は、 Crystal Advent Calendar 2016 の８日目の記事です。 qiita.com
ncurses という CUI を作るためにスクリーンやキー入力を扱う有名なライブラリの Crystal binding を作りました。
ほとんど C の ncurses と同じ感じで使えるようになっていると思います． Ruby や Python の curses ライブラリを参考にしつつ，なるべく使用感がかわらないようにしています．
examples
require “ncurses” NCurses.open do NCurses.cbreak NCurses.noecho NCurses.move(x: 30, y: 20) NCurses.addstr(“Hello, world!”) NCurses.refresh NCurses.notimeout(true) NCurses.getch end
NCurses.addstr とか NCurses.move とかは ncurses で言う addstr や move に当たる関数で，stdscr に対して waddstr とか wmove するやつです．
w = NCurses::Window.new(height: height, width: width) とすることで subwindow が作れます．
w.addstr や w.move という形で w prefix な関数たちが呼べるようになっています．
pad や attron / attroff などなども使えます．
詳細な例は example/ 以下のにおいてあります
なぜ作ったのか
実は ncurses bindings for Crystal はすでにあります．(https://github.com/jreinert/ncurses-crystal)
curses が Crystal の標準ライブラリから外されることが決まったときの CHANGELOG を見ると，今後はそっちを使ってねと書いてあったりします．
じゃあなんでわざわざ別で作ったのかという話ですが，API が足りない & 提供する API の形を変えたいと思ったからです．
単純に bind されている API が少なくてやりたいことができなかったので，最初は追加して PR を出そうと思っていたのですが，すでに提供されている API が割と高級になっていて 1 : 1 で C API と対応していない感じでした． 個人的には C library の wrapper にはなるべく薄くなっていてもらって基本的な API は覚え直さないでも使えるようになっていてほしいというふうに思ったので，C API と 1 : 1 で対応した形の API を提供する wrapper を作ってみようという経緯で新しく作ることにしました．
おまけ
C bindings を書くときに，wrapper API として LibC::Int が登場しちゃうのがなんとなく嫌で，LibC::Int を C が要求してくる関数を呼ぶ wrapper 関数には型指定をあえてしないという選択をしたんですがどうなんでしょう．
lib LibNCurses fun wmove(w : Window, y : LibC::Int, x : LibC::Int) : Result end
class Window def move(y, x) LibNCurses.wmove(@win, y, x) end end
みたいな感じです．（多少簡略化しています）
これどうなんですかね．なるべく外に見せる API には型を明記するようにしたかったのですが，LibC:Int 系は環境によって異なるのでそういうわけにも行かず…
y : LibC::Int, x : LibC::Int とかは別に良いんですが，ncurses は文字と属性をくっつけた chtype なる型を持っていてこれが結構厄介というか混乱を招くのではと思っています．
chtype は char ではなく unsigned int で，文字と属性を bitor でくっつけたものになっています．addch のように char をとることを連想させる関数の引数が実は chtype = unsigned int でしかも Crystal の文字型 Char は 32bit なのでものすごく混乱します…
C は型変換を勝手にやってくれるので，unsigned int を返す関数から受け取った値を short を受け取る関数に渡すみたいなことをよくやっていて，Crystal のような型変換を暗黙にやらない言語から使おうとすると難しいんだなぁと思いました．
なにか良い方法があればぜひ知りたいです．
Rust で Box に包まれた構造体の所有権分解
ちょっとはまったのでメモ
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 のようなコードが突然出てきたら混乱しそうだ。
日本語の改行を適当にいい感じにするツールを作りました
必要に迫られて、HTML ページ内の改行位置をいい感じにするツールを作ってみました。
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。
しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。
最も有名な問題として、今すぐダウンロー
ド問題が挙げられます。
japawrap を使うと、それっぽく日本語を解釈して <span> でくくるみたいなことができます。inline-block を適用すれば改行がそれっぽく入るようにできます。
Install
go get github.com/agatan/japawrap/...
で japawrap コマンドが使えるようになります。
Usage
CLI
ファイル名を指定するか標準入力から流し込みます。
$ echo "今日も元気です" | japawrap <span class="wordwrap">今日も</span><span class="wordwrap">元気です</span>
このように適宜いい感じに wrap してくれます。
オプションとして -open string と -close string をサポートしているので、
$ echo "今日も元気です" | japawrap -open '<span style="display: inline-block;">' -close "</span>" <span style="display: inline-block;">今日も</span><span style="display: inline-block;">元気です</span>
みたいなことができます。
Library
一応 japawrap はライブラリとしても使用できるようになっています。
w := japawrap.New(open, close) s := "今日も元気です" fmt.Println("%s => %s", s, w.Do(s))
これだけです。
Example
では実際に使った結果を下に記したいと思います。 文章は、上の方に自分で書いた文章をそのまま使います。
before
HTMLに長文を書くと、親DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
after
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
こんな感じになります。猛烈に効果がわかりにくくて驚いていますが、一応効果はちゃんと出ているのではないでしょうか？ HTMLを直接見ていただければどうなっているかはわかると思います。
次に青空文庫から夏目漱石「こころ」の序文を抜粋してみたのが下の画像たちです。
レスポンシブ！それなりになっている気がします。
あとがき
この問題へのアプローチとして、https://github.com/google/budou が有名だと思います。
budou は Cloud Natural Language API を内部で使っていて、しっかり日本語の文章を構文解析しているようです。
なので非常に精度は高いと思うのですが、今僕の GCP アカウントがごにょごにょしていてぱぱっと試せる状況ではなかったので自作しました。
budou と違ってしっかり構文解析などはしていなくて、形態素解析した後、それっぽく分割しているだけです。なので精度は落ちると思います。
一方、budou は GCP の credentails が必要だったりと準備が必要になるので、お手軽に試せるというのは悪くないかなと思っています。
Rust の Result と Iterator
Rust には失敗するかもしれない値を表す Result<T, E> という型があります。
std::result::Result
そして iterate できることを表す Iterator という trait があります。
std::iter::Iterator
また、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 は 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
値と参照について
「値」と「参照」という言葉があります。 このへんの言葉について、今の理解をまとめておこうと思います。 言葉の定義や理解が誤っている部分があればご指摘ください。
まず、前提として以下では、「値」ベースの言語として C, C++, Rust などを、「参照」ベースの言語として Java, C#, Ruby などを想定しています。 （もちろん言語によってはハイブリッドなものもあります: Crystal, Go, D, ...）
そもそも「値」「参照」とは
「値」は「実体」、「参照」は「実体へのポインタ」です。
int の配列みたいなものを考えてみます。
[1, 2, 3] をメモリ上にどう表現できるでしょうか。
配列ですから、単純にメモリ上のどこかに以下のような領域を作ればよさそうです。
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
これが「値」であり配列の実体です。 そして、実体の配置されたメモリ領域へのポインタが「参照」です。
スタック上の表現
さて、プログラム上ではこの配列のようなオブジェクトを、ローカル変数としてスタック上で表現したり、関数に引数として渡したりします。 では、スタック上での配列の表現はどうなっているのか考えてみます。
ここで、「値」と「参照」という言葉が重要になります。
「値」ベースな言語では、スタック上に
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
をそのままべたっと配置します。
一方で、「参照」ベースな言語では、ヒープ上に
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
を配置し、スタック上では実体へのポインタという表現になります。 （必ずしもヒープに置くとは限らない？処理系や最適化によってはスタックに置くこともありえる？とにかくローカル変数などの表現としては実体へのポインタという形をとるということ）
値渡し・参照渡し
値渡しとか参照渡しという言葉があります。
以下に擬似コードを一つ書いてみます。（C 風に書いていますが C ではないと思ってください）
void inc_age(Person p) { p.age++; } Person john = Person { "john", 20 }; inc_age(john); print(john.age); // => ??
このコード、処理系が「値」ベースか「参照」ベースかで結果が異なります。
「値」ベースの場合
値ベースの言語の場合、inc_age の引数に john を渡した時には、inc_age 内のローカル変数（引数） p のために、john のコピーが作られます。
inc_age 内で p.age++ としていますが、p は john のコピーであって john ではありませんから、inc_age から戻ってきて john.age を参照しても 20 のまま変化が無いはずです。
したがって結果として 20 が出力されます。
「参照」ベースの場合
参照ベースの言語の場合、john 変数のメモリ上での表現は、ヒープに置かれた Person { "john", 20 } というオブジェクトへのポインタになります。
inc_age にこれを引数として渡すと、ポインタの値がコピーされますから、p と john は同じオブジェクトを参照しているポインタになります。
p.age++ とすると p が参照するオブジェクトが変更されます。これは john が参照するオブジェクトと同一ですから、john.age も 21 に変化します。
したがって結果として 21 が出力されます。
C の場合
C の場合、ポインタが直接表現できますから、参照渡しの挙動を模倣することができます。
void inc_age(Person *p) { p->age++; } Person john = Person { "john", 20 }; inc_age(&john); print(john.age); // => 21
p が Person* 型であること、そして inc_age に john のアドレスを渡していることに注目してください。
この場合、p は john を参照するポインタですから、結果は 21 になります。
C++ の場合
C++ の場合、言語機能として「参照渡し」という機能があります。
void inc_age(Person& p) { p.age++; } Person john = Person { "john", 20 }; inc_age(john); print(john.age); // => 21
p が Person& 型であること、inc_age には john をそのまま渡しているように見えることに注目してください。
これは C++ の提供する機能で、コンパイルすると、Person& は実質 Person* と同じ表現になります。
p->age ではなく p.age と書けること、&john ではなく john のままで参照渡しが実現できるようになっています。
単純なポインタを使っても同じことが出来ますが、ポインタと違って nullptr になることがないという特徴があります。
参照のハマりやすい点
個人的に参照ベースの言語でハマりやすいなと感じるのは以下のようなコードです。
void some_function(Person p) { p.age++; p = new Person("bob", 30); } Person p = new Person("john", 20); some_function(p); println(p.name); // => john println(p.age); // => 21
p.age++ の部分は呼び出し元のオブジェクトに反映されるのに、p = new Person(...) の部分はなんで反映されないの！ってなります。（なりません？）
本質的にポインタの値渡しにすぎないんだということを理解していればまぁ納得なのですが...
（ちなみに C++ や D の参照渡しだと p = new Person(...) 的なコードも呼び出し元に反映されます。）
値のハマりやすい点
ハマりやすいというか、気がつかないままパフォーマンスが悪くなりやすいのが値ベースの言語の弱点でしょう。
void print_object(HugeObject obj) { printf("%s\n", obj.name); } HugeObject obj = ...; print_object(obj);
このようなコードを書くと、ただ名前を表示するだけの関数が激重になる可能性があります。 値ベースの言語では、引数として値を渡すとまるっとそのコピーをつくりますから、不要にもかかわらず巨大な値のコピーを作ってしまいます。
まとめ
「ムーブセマンティクス」とか「immutable と参照」とかについてまとめようと思ったのですが、前提として「値」「参照」についてまとめていないと書きにくいなと思ったのでまとめておきました。
内部表現を知ることでハマりやすい点の回避にもつながると思うので、この辺はきちんと理解しておきたいです。
