RustのFFIを使ってみた（libc ftsによるwalkdir実装）

# はじめに
BSDやLinuxのglibcにはftsという関数群があります。これはディレクトリ内の再帰的なファイル列挙を高速に行う関数で、`ls`や`find`などの実装に使われています。
Rustでこのようなファイル列挙を行う場合、`std::fs::readdir`で実装するか、既存の[`walkdir`](https://crates.io/crates/walkdir)(これも内部的には`readdir`を使っているようです)を使うことになりますが、ftsが速いらしいということで、FFIライブラリを作ってそれを使った`walkdir`相当の実装を行いました。
ちなみにglibcに依存するのでおそらくBSD(OSX含む)とLinux限定です。Windows対応が必要なら素直に`walkdir`を使いましょう。

# リンク
- [crates.io](https://crates.io/crates/fts)
- [ソースコード](https://github.com/dalance/fts-rs)
- [ドキュメント](http://dalance.github.io/fts-rs/fts/)

# 使い方

```Cargo.toml
[dependencies]
fts = "*"
```

`walkdir`と同様にイテレータ実装しているので`for`で回せます。

```rust
use std::path::Path;
use fts::walkdir::{WalkDir, WalkDirConf}

let path = Path::new( "." );
for p in WalkDir::new( WalkDirConf::new( path ) ) {
    println!( "{:?}", p.unwrap() );
}
```

フィルタも出来ます。

```rust
use std::path::Path;
use fts::walkdir::{WalkDir, WalkDirConf}

let path = Path::new( "." );
let iter = WalkDir::new( WalkDirConf::new( path ) ).into_iter().filter_map( |x| x.ok() );
for p in iter.filter( |x| x.file_type().is_file() ) {
    println!( "{:?}", p );
}
```

`WalkDirConf`はBuilderになっていて、以下のように設定できます。以下の`conf1`の場合、シンボリックリンクを辿り、かつリンク先が別デバイスであっても辿る設定になります。`conf2`は`metadata`を取得しないオプションで、その分高速になります。

```rust
se std::path::Path;
use fts::walkdir::{WalkDir, WalkDirConf}

let path = Path::new( "." );
let conf1 = WalkDirConf::new( path ).follow_symlink().cross_device();
let conf2 = WalkDirConf::new( path ).no_metadata();

for p in WalkDir::new( conf1 ) {
    println!( "{:?}", p.unwrap() );
}
for p in WalkDir::new( conf2 ) {
    println!( "{:?}", p.unwrap() );
}

```


# ベンチマーク
`cargo bench`の結果です。`test fts_walkdir`が今回実装したもの、`test readdir`が`readdir`を再帰で呼ぶだけの適当な実装、`test walkdir`が`walkdir`を使ったものになります。また、`_metadata`と付いているものは各ディレクトリエントリに対し、`DirEntry::metadata()`を呼んでいるバージョンになります。
`walkdir`比でだいたい２倍くらい速くなっています。

```
test fts_walkdir          ... bench: 315,114,126 ns/iter (+/- 8,478,709)
test fts_walkdir_metadata ... bench: 480,089,245 ns/iter (+/- 11,478,335)
test readdir              ... bench: 575,856,224 ns/iter (+/- 15,021,486)
test readdir_metadata     ... bench: 790,838,218 ns/iter (+/- 12,780,010)
test walkdir              ... bench: 688,884,058 ns/iter (+/- 8,023,838)
test walkdir_metadata     ... bench: 904,379,691 ns/iter (+/- 10,212,776)
```

# 解説
FFI関連の実装詳細を多少解説します。
基本は[ここ](http://rust-lang-ja.github.io/the-rust-programming-language-ja/1.6/book/ffi.html)に書いてあるので、それ以外の細かいところを。

## 値型
`int`など基本的なもの以外でもlibcクレートに大抵あるので[ここ](https://doc.rust-lang.org/libc/x86_64-unknown-linux-gnu/libc/#types)で調べるとよいと思います。`ino_t`とか`dev_t`もあります。`vold*`は`c_void`です。

とはいえ、まれにlibcの型定義でうまくいかないことがあります。例えばOSXにおける`ino_t`はlibc的には64bitなのですが、ftsが期待する`ino_t`は32bitのようでした。（このあたり詳しい事情は分かりませんし、そもそもOSX環境が手元にないので、Travis-CIのOSXビルドではそうだった、というだけですが…）

### 2016/3/19追記
OSXの`ino_t`ですが、以下のように`link_name`を指定することで、libc定義通り64bitの`ino_t`を得ることが出来ました。
（rustのlibstd実装見て気づきました。よく見ると[Appleのドキュメント](https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man2/stat.2.html)にも`$INODE64`付きのシンボル名で64bit版になると書いてあります）

```rust
#[cfg_attr(target_os = "macos", link_name = "fts_read$INODE64")]
pub fn fts_read( ftsp: *mut FTS ) -> *const FTSENT;
```

## `null`ポインタ
`null`ポインタそのものは`std::ptr::null()`で得られます。例えば`fts_open`は引数に「`null`ポインタで終端された文字列ポインタ配列へのポインタ」を渡すので以下のようになります。また、`null`ポインタチェックは`is_null()`が使えます。

```rust
let path_ptr = std::ffi::CString::new( "." ).unwrap().as_ptr();
let path_ptrs = vec![path_ptr, std::ptr::null()];
let fts = fts_open( path_ptrs.as_ptr(), 0, None );
assert!( !fts.is_null() );
```

## 定数定義
Cで`#define`されているような定数についてです。

ビットフラグの場合は[`bitflags`](https://crates.io/crates/bitflags)が使えます。ちゃんと型指定できて、ビット演算も普通に出来ます。Cに渡すときは`bits()`で整数型に変換して渡します。下の例だとフラグの型は`Flags`ですが、定義した値は`Flags::A`とはならず単に`A`になってしまうので`mod`でくるんで`option::A`になるようにしています。

```rust
pub mod option {
    bitflags! {
        pub flags Flags: u32 {
            const A = 0x0001,
            const B = 0x0002,
            const C = 0x0004,
        }
    }
}

let opt = option::A | option::B;
assert_eq!( opt.bits(), 0x3 );
```

ビットフラグでない場合、基本的には`enum`で良いのですが、Cからの戻り値を`enum`に変換するのが面倒です。[`enum_primitive`](https://crates.io/crates/enum_primitive)を使えば各種`from_`を自動実装してくれます。

```rust
enum_from_primitive! {
    #[derive(Clone,Debug,PartialEq)]
    pub enum Info {
        A = 0,
        B = 1,
        C = 2,
    }
}

assert_rq!( Info::A, Info::from_isize( 0 ) );
assert_rq!( Info::B, Info::from_isize( 1 ) );
```


## `errno`
エラーがいわゆる`errno`で返ってくる場合、自分でデコードする必要はなくて、`std::io::Error::from_raw_os_error()`で変換出来ます。

```rust
let errno = 13;
let err = std::io::Error::from_raw_os_error( errno );
assert_eq!( err.kind(), std::io::ErrorKind::PermissionDenied );
```

## `transmute`
`std::mem::transmute()`で無理矢理キャストしたい場合があります。
今回は2ヶ所で使っていて、1つ目は`metadata`です。Cから返ってくる`libc::stat`とRustで使いたい`std::fs::Metadata`はUnixではおそらく同一のメモリレイアウトなので`transmute`で変換しています。この辺りドキュメントに記載されているわけではないので、プラットホームやバージョンで変わる可能性はあります。
(とはいえ`MetadataExt::as_raw_stat()`で`libc::stat`ポインタが返ってくる以上、メモリレイアウトが異なるというのも考えにくいです。本当は`from_raw_stat()`があってくれればいいのですが)

```rust
let stat = ...
let metadata = std::mem::transmute::<*const libc::stat, *const std::fs::Metadata>( stat );
```

2つ目はC側が少し不思議なことになっていて、`fts_open()`の戻り値である構造体定義は以下のようになっています。

```c
typedef struct _ftsent {
    ....
    char fts_name[1];
} FTSENT;
```

ここで最後の要素の`fts_name`は`char`の要素数１の配列と定義されていますが、実際にはそのあとも文字列は続いています。つまり`struct`の定義から実体がはみ出している状態です。(glibc自体の実装を見ると、`struct`の`alloc`時に`MAX_PATH_LEN`だけ余計にメモリ確保しているようです)
この状態を適切に表せる型があればいいのですが、多分なさそうなのでRust側も要素数1の配列として宣言して、アクセスするときに`transmute`でキャストしています。

```
#[repr(C)]
#[derive(Debug)]
pub struct FTSENT {
    ...
    pub fts_name   : [c_char;1]   ,
}

let ent: *const FTSENT = ...
let ptr  = unsafe { mem::transmute::<&[c_char;1], *mut u8>( &(*ent).fts_name ) };
```