Rustで使わない変数名をつけるのとアンダースコアの微妙な違い

変数はブロックの末尾まで生存するが、アンダースコアは変数ではないためその文の中でのみ生存する。どうせ使わないからほぼ同じだが、Dropの順番が異なる。

struct A(&'static str);

impl Drop for A {
    fn drop(&mut self) {
        println!("dropped: {}", self.0);
    }
}
fn main() {
    let _ = A("x");
    let y = A("y");
    let z = A("z");
}
dropped: x
dropped: z
dropped: y

ちなみに、変数名をアンダースコアから始めると、その変数が未使用でも警告が出ない。

Rustのstd::mem::forgetがunsafeでない理由

Rustのstd::mem::forgetはunsafeではない。このことはAPIドキュメントに説明されている。Rustのオブジェクトは二重dropしてはいけないが、dropをせずに放置する分には(少なくともメモリ保護の観点からは)安全であり、 Drop を実装する側は drop が呼ばれなくても安全であるようにしなければならない。

これは、同じくドキュメントで説明されているように、容易に正当化できる。以下のように Rc で循環参照を作ると、 forget を模倣することができる。(std::mem::forget とは異なり、より多くのメモリリークを生じるという違いはある)

pub fn my_forget<T>(x: T) {
    use std::rc::Rc;
    use std::cell::RefCell;
    struct Cyc<T> {
        x: T,
        cyc: RefCell<Option<Rc<Cyc<T>>>>,
    }
    let c = Rc::new(Cyc {
        x: x,
        cyc: RefCell::new(None)
    });
    *c.cyc.borrow_mut() = Some(c.clone());
}

struct A<'a> {
    s: &'a str,
}

impl<'a> A<'a> {
    pub fn new(s: &'a str) -> Self {
        A { s: s, }
    }
}

impl<'a> Drop for A<'a> {
    fn drop(&mut self) {
        println!("dropped: {}", self.s);
    }
}

fn main() {
    let data1 = [49];
    let obj1 = A::new(std::str::from_utf8(&data1).unwrap());
    
    let data2 = [50];
    let obj2 = A::new(std::str::from_utf8(&data2).unwrap());
    std::mem::forget(obj2);
    
    let data3 = [51];
    let obj3 = A::new(std::str::from_utf8(&data3).unwrap());
    my_forget(obj3);
}

やや直感に反する点として、 forget<T>T: 'static を要求していないという点がある。例えば上の例でも、スタック上の文字列へのポインタが、循環参照の中に放置されたまま、プログラムが終了してしまっている。これはRustでは許されているようだ。

Rustのasm!マクロが生成するもの

Rustのasm!インラインアセンブリを挿入するための組み込みマクロである。さて、このマクロは何を生成しているのか。

実は、RustのASTには、対応する具象構文を持たない特殊な抽象構文 InlineAsm が定義されている。

pub enum ExprKind {
    Box(P<Expr>),
    ...

    /// Output of the `asm!()` macro
    InlineAsm(P<InlineAsm>),

    ...
}

asm! の実装である expand_asm の末尾 でこれが生成されているのがわかる。

具象構文を持たない抽象構文をマクロが生成できるのはなぜか。これは expand_asm の戻り値 MacEager と戻り値型 MacResult を調べるとわかる。

まず MacResult は以下のように複数のメソッドを持っている。

pub trait MacResult {
    /// Create an expression.
    fn make_expr(self: Box<Self>) -> Option<P<ast::Expr>> {
        None
    }
    /// Create zero or more items.
    fn make_items(self: Box<Self>) -> Option<SmallVector<P<ast::Item>>> {
        None
    }

    ...
}

つまり、 MacResult は文脈に応じて異なる種類のASTにキャストできる値ということになる。

MacResult を実装しているのは、 (DummyResult を除くと) ParserAnyMacroMacEager のみである。

通常の macro_rules! マクロは ParserAnyMacro を返す。 ParserAnyMacro のメンバは以下のようになっている。

pub struct ParserAnyMacro<'a> {
    parser: Parser<'a>,
    ...
}

つまりパーサーの状態そのものを持っている。このパーサーは以下のように生成されている。

...
        match TokenTree::parse(cx, lhs_tt, arg) {
            Success(named_matches) => {
                ...
                let tts = transcribe(&cx.parse_sess.span_diagnostic, Some(named_matches), rhs);
                ...
                let mut p = Parser::new(cx.parse_sess(), tts, Some(directory), false);
                ...
                return Box::new(ParserAnyMacro {
                    parser: p,
                    ...
                })
            }
            ...
        }

つまり、マクロ実引数が規則にマッチしたら、マッチ結果からトークン列を生成する。このトークン列を初期状態としてパーサーを生成している。

ParserAnyMacroMacResult以下のように実装している。

macro_rules! expansions {
    ($($kind:ident: $ty:ty [$($vec:ident, $ty_elt:ty)*], $kind_name:expr, .$make:ident,
            $(.$fold:ident)*  $(lift .$fold_elt:ident)*,
            $(.$visit:ident)*  $(lift .$visit_elt:ident)*;)*) => {
        ...
        impl<'a> MacResult for ::ext::tt::macro_rules::ParserAnyMacro<'a> {
            $(fn $make(self: Box<::ext::tt::macro_rules::ParserAnyMacro<'a>>) -> Option<$ty> {
                Some(self.make(ExpansionKind::$kind).$make())
            })*
        }
    }
}

expansions! {
    Expr: P<ast::Expr> [], "expression", .make_expr, .fold_expr, .visit_expr;
    Pat: P<ast::Pat>   [], "pattern",    .make_pat,  .fold_pat,  .visit_pat;
    ...
}

つまり、 ParserAnyMacro は、 make_* が呼び出された時点ではじめてトークン列を構文解析し、ASTを返す。

一方、 MacEager以下のように定義されている。

macro_rules! make_MacEager {
    ( $( $fld:ident: $t:ty, )* ) => {
        ...
        pub struct MacEager {
            $(
                pub $fld: Option<$t>,
            )*
        }
        ...
    }
}

make_MacEager! {
    expr: P<ast::Expr>,
    pat: P<ast::Pat>,
    ...
}

つまり、 MacEagerトークン列をもたず、構文解析済みのASTをそのまま持っている。

ここで expand_asm に戻ると、これは InlineAsm をのせた MacEager を生成しているため、具象構文を経由せずに直接 InlineAsm を生成できていることになる。

    ...
    MacEager::expr(P(ast::Expr {
        id: ast::DUMMY_NODE_ID,
        node: ast::ExprKind::InlineAsm(P(ast::InlineAsm {
            asm: asm,
            asm_str_style: asm_str_style.unwrap(),
            outputs: outputs,
            inputs: inputs,
            clobbers: clobs,
            volatile: volatile,
            alignstack: alignstack,
            dialect: dialect,
            expn_id: expn_id,
        })),
        span: sp,
        attrs: ast::ThinVec::new(),
    }))

なお、 InlineAsm を含む構文木stringify! したときは、 pprust内の処理asm!(...) の形に復元される。

extern "rust-call" とは何か

extern "rust-call" は(Rust 1.16.0時点では) Fn, FnMut, FnOnce の宣言に出現する。この意味について Rust issue 41058: Get rid of the “rust-call” hack の説明がわかりやすい。

Currently, we fake variadics by defining functions with the rust-call ABI. These functions receive a tuple as parameter (of arbitrary arity and types), but in their ABI the tuple is expanded.

つまり、 rust-call は、可変長な型多相性をタプルで代用するにあたって、ABIを展開後の引数リストに合わせるためのハック的な仕組みということになる。

rust-callが処理されるまで

extern "rust-call"AbiDatas により abi::Abi::RustCall に変換される。(なお 単に extern とすると Abi::C になり、何も指定しないと Abi::Rust になる。)

rust-call のつけられた関数の受け取り側では、construct_fn 内で spread_arg というマークがつけられる。 さらに arg_local_refs で引数の取り出し処理を生成する際に特殊な処理が行われる。これは、バラバラに渡された末尾引数をタプルに戻す処理を書いている。

一方、 rust-call 関数を呼び出す側では、trans_block の関数呼び出しに対する処理で、末尾のタプルを分解して渡すようになっている。

rust-callの生成

手動で生成するほかに、以下の位置で rust-call な関数が生成されている。

実験

#![feature(unboxed_closures)]

pub fn f(x: (u8, u8, u8, u8, u8, u8, u8, u8)) {
}
pub extern "rust-call" fn g(x: (u8, u8, u8, u8, u8, u8, u8, u8)) {
}

fn main() {
    f((10, 11, 12, 13, 14, 15, 16, 17));
    g((10, 11, 12, 13, 14, 15, 16, 17));
}

これをデバッグモードでLLVM IRまでコンパイルすると以下のようになる。

; ModuleID = 'rust_out.cgu-0.rs'
source_filename = "rust_out.cgu-0.rs"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@__rustc_debug_gdb_scripts_section__ = internal unnamed_addr constant [34 x i8] c"\01gdb_load_rust_pretty_printers.py\00", section ".debug_gdb_scripts", align 1

; Function Attrs: uwtable
define internal void @_ZN8rust_out1f17h77fb50884e4b9292E(i64) unnamed_addr #0 !dbg !5 {
entry-block:
  %x = alloca { i8, i8, i8, i8, i8, i8, i8, i8 }
  %_0 = alloca {}
  %abi_cast = alloca i64
  %arg0 = alloca { i8, i8, i8, i8, i8, i8, i8, i8 }
  store i64 %0, i64* %abi_cast
  %1 = bitcast { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0 to i8*
  %2 = bitcast i64* %abi_cast to i8*
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %1, i8* %2, i64 8, i32 1, i1 false)
  call void @llvm.dbg.declare(metadata { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, metadata !22, metadata !23), !dbg !24
  call void @llvm.dbg.declare(metadata { i8, i8, i8, i8, i8, i8, i8, i8 }* %x, metadata !25, metadata !23), !dbg !27
  br label %start, !dbg !27

start:                                            ; preds = %entry-block
  %3 = bitcast { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0 to i8*, !dbg !28
  %4 = bitcast { i8, i8, i8, i8, i8, i8, i8, i8 }* %x to i8*, !dbg !28
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %3, i64 8, i32 1, i1 false), !dbg !28
  ret void, !dbg !29
}

; Function Attrs: uwtable
define internal void @_ZN8rust_out1g17h976fe88719539209E(i8, i8, i8, i8, i8, i8, i8, i8) unnamed_addr #0 !dbg !30 {
entry-block:
  %x = alloca { i8, i8, i8, i8, i8, i8, i8, i8 }
  %_0 = alloca {}
  %arg0 = alloca { i8, i8, i8, i8, i8, i8, i8, i8 }
  %8 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 0
  store i8 %0, i8* %8
  %9 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 1
  store i8 %1, i8* %9
  %10 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 2
  store i8 %2, i8* %10
  %11 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 3
  store i8 %3, i8* %11
  %12 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 4
  store i8 %4, i8* %12
  %13 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 5
  store i8 %5, i8* %13
  %14 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 6
  store i8 %6, i8* %14
  %15 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, i32 0, i32 7
  store i8 %7, i8* %15
  call void @llvm.dbg.declare(metadata { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0, metadata !33, metadata !23), !dbg !34
  call void @llvm.dbg.declare(metadata { i8, i8, i8, i8, i8, i8, i8, i8 }* %x, metadata !35, metadata !23), !dbg !37
  br label %start, !dbg !37

start:                                            ; preds = %entry-block
  %16 = bitcast { i8, i8, i8, i8, i8, i8, i8, i8 }* %arg0 to i8*, !dbg !38
  %17 = bitcast { i8, i8, i8, i8, i8, i8, i8, i8 }* %x to i8*, !dbg !38
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %17, i8* %16, i64 8, i32 1, i1 false), !dbg !38
  ret void, !dbg !39
}

; Function Attrs: uwtable
define internal void @_ZN8rust_out4main17h6d608a6572dc79f7E() unnamed_addr #0 !dbg !40 {
entry-block:
  %_4 = alloca { i8, i8, i8, i8, i8, i8, i8, i8 }
  %_2 = alloca { i8, i8, i8, i8, i8, i8, i8, i8 }
  %_0 = alloca {}
  br label %start

start:                                            ; preds = %entry-block
  %0 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 0, !dbg !43
  store i8 10, i8* %0, !dbg !43
  %1 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 1, !dbg !43
  store i8 11, i8* %1, !dbg !43
  %2 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 2, !dbg !43
  store i8 12, i8* %2, !dbg !43
  %3 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 3, !dbg !43
  store i8 13, i8* %3, !dbg !43
  %4 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 4, !dbg !43
  store i8 14, i8* %4, !dbg !43
  %5 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 5, !dbg !43
  store i8 15, i8* %5, !dbg !43
  %6 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 6, !dbg !43
  store i8 16, i8* %6, !dbg !43
  %7 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2, i32 0, i32 7, !dbg !43
  store i8 17, i8* %7, !dbg !43
  %8 = bitcast { i8, i8, i8, i8, i8, i8, i8, i8 }* %_2 to i64*, !dbg !43
  %9 = load i64, i64* %8, align 1, !dbg !43
  call void @_ZN8rust_out1f17h77fb50884e4b9292E(i64 %9), !dbg !43
  br label %bb1, !dbg !43

bb1:                                              ; preds = %start
  %10 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 0, !dbg !44
  store i8 10, i8* %10, !dbg !44
  %11 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 1, !dbg !44
  store i8 11, i8* %11, !dbg !44
  %12 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 2, !dbg !44
  store i8 12, i8* %12, !dbg !44
  %13 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 3, !dbg !44
  store i8 13, i8* %13, !dbg !44
  %14 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 4, !dbg !44
  store i8 14, i8* %14, !dbg !44
  %15 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 5, !dbg !44
  store i8 15, i8* %15, !dbg !44
  %16 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 6, !dbg !44
  store i8 16, i8* %16, !dbg !44
  %17 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 7, !dbg !44
  store i8 17, i8* %17, !dbg !44
  %18 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 0, !dbg !44
  %19 = load i8, i8* %18, !dbg !44
  %20 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 1, !dbg !44
  %21 = load i8, i8* %20, !dbg !44
  %22 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 2, !dbg !44
  %23 = load i8, i8* %22, !dbg !44
  %24 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 3, !dbg !44
  %25 = load i8, i8* %24, !dbg !44
  %26 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 4, !dbg !44
  %27 = load i8, i8* %26, !dbg !44
  %28 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 5, !dbg !44
  %29 = load i8, i8* %28, !dbg !44
  %30 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 6, !dbg !44
  %31 = load i8, i8* %30, !dbg !44
  %32 = getelementptr inbounds { i8, i8, i8, i8, i8, i8, i8, i8 }, { i8, i8, i8, i8, i8, i8, i8, i8 }* %_4, i32 0, i32 7, !dbg !44
  %33 = load i8, i8* %32, !dbg !44
  call void @_ZN8rust_out1g17h976fe88719539209E(i8 %19, i8 %21, i8 %23, i8 %25, i8 %27, i8 %29, i8 %31, i8 %33), !dbg !44
  br label %bb2, !dbg !44

bb2:                                              ; preds = %bb1
  ret void, !dbg !45
}

; Function Attrs: argmemonly nounwind
declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1) #1

; Function Attrs: nounwind readnone
declare void @llvm.dbg.declare(metadata, metadata, metadata) #2

define i64 @main(i64, i8**) unnamed_addr #3 {
top:
  %2 = load volatile i8, i8* getelementptr inbounds ([34 x i8], [34 x i8]* @__rustc_debug_gdb_scripts_section__, i32 0, i32 0), align 1
  %3 = call i64 @_ZN3std2rt10lang_start17ha5350a26f8f175abE(i8* bitcast (void ()* @_ZN8rust_out4main17h6d608a6572dc79f7E to i8*), i64 %0, i8** %1)
  ret i64 %3
}

declare i64 @_ZN3std2rt10lang_start17ha5350a26f8f175abE(i8*, i64, i8**) unnamed_addr #3

attributes #0 = { uwtable "no-frame-pointer-elim"="true" }
attributes #1 = { argmemonly nounwind }
attributes #2 = { nounwind readnone }
attributes #3 = { "no-frame-pointer-elim"="true" }

!llvm.module.flags = !{!0, !1}
!llvm.dbg.cu = !{!2}

!0 = !{i32 1, !"PIE Level", i32 2}
!1 = !{i32 2, !"Debug Info Version", i32 3}
!2 = distinct !DICompileUnit(language: DW_LANG_Rust, file: !3, producer: "rustc version 1.18.0-nightly (ad36c2f55 2017-04-09)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4)
!3 = !DIFile(filename: "rust_out", directory: "/tmp")
!4 = !{}
!5 = distinct !DISubprogram(name: "f", linkageName: "_ZN8rust_out1fE", scope: !7, file: !6, line: 3, type: !8, isLocal: true, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, unit: !2, templateParams: !4, variables: !4)
!6 = !DIFile(filename: "<anon>", directory: "/tmp")
!7 = !DINamespace(name: "rust_out", scope: null, file: !6, line: 1)
!8 = !DISubroutineType(types: !9)
!9 = !{null, !10}
!10 = !DICompositeType(tag: DW_TAG_structure_type, name: "(u8, u8, u8, u8, u8, u8, u8, u8)", file: !11, size: 64, align: 8, elements: !12, identifier: "489a633ed2a79c313b5e1834133e88ec27884aa2")
!11 = !DIFile(filename: "<unknown>", directory: "")
!12 = !{!13, !15, !16, !17, !18, !19, !20, !21}
!13 = !DIDerivedType(tag: DW_TAG_member, name: "__0", scope: !10, file: !11, baseType: !14, size: 8, align: 8)
!14 = !DIBasicType(name: "u8", size: 8, align: 8, encoding: DW_ATE_unsigned)
!15 = !DIDerivedType(tag: DW_TAG_member, name: "__1", scope: !10, file: !11, baseType: !14, size: 8, align: 8, offset: 8)
!16 = !DIDerivedType(tag: DW_TAG_member, name: "__2", scope: !10, file: !11, baseType: !14, size: 8, align: 8, offset: 16)
!17 = !DIDerivedType(tag: DW_TAG_member, name: "__3", scope: !10, file: !11, baseType: !14, size: 8, align: 8, offset: 24)
!18 = !DIDerivedType(tag: DW_TAG_member, name: "__4", scope: !10, file: !11, baseType: !14, size: 8, align: 8, offset: 32)
!19 = !DIDerivedType(tag: DW_TAG_member, name: "__5", scope: !10, file: !11, baseType: !14, size: 8, align: 8, offset: 40)
!20 = !DIDerivedType(tag: DW_TAG_member, name: "__6", scope: !10, file: !11, baseType: !14, size: 8, align: 8, offset: 48)
!21 = !DIDerivedType(tag: DW_TAG_member, name: "__7", scope: !10, file: !11, baseType: !14, size: 8, align: 8, offset: 56)
!22 = !DILocalVariable(name: "x", arg: 1, scope: !5, file: !6, line: 1, type: !10)
!23 = !DIExpression()
!24 = !DILocation(line: 1, scope: !5)
!25 = !DILocalVariable(name: "x", scope: !26, file: !6, line: 3, type: !10)
!26 = distinct !DILexicalBlock(scope: !5, file: !6, line: 3, column: 46)
!27 = !DILocation(line: 3, scope: !26)
!28 = !DILocation(line: 3, scope: !5)
!29 = !DILocation(line: 4, scope: !26)
!30 = distinct !DISubprogram(name: "g", linkageName: "_ZN8rust_out1gE", scope: !7, file: !6, line: 5, type: !31, isLocal: false, isDefinition: true, scopeLine: 5, flags: DIFlagPrototyped, isOptimized: false, unit: !2, templateParams: !4, variables: !4)
!31 = !DISubroutineType(types: !32)
!32 = !{null, !14, !14, !14, !14, !14, !14, !14, !14}
!33 = !DILocalVariable(name: "x", arg: 1, scope: !30, file: !6, line: 1, type: !10)
!34 = !DILocation(line: 1, scope: !30)
!35 = !DILocalVariable(name: "x", scope: !36, file: !6, line: 5, type: !10)
!36 = distinct !DILexicalBlock(scope: !30, file: !6, line: 5, column: 65)
!37 = !DILocation(line: 5, scope: !36)
!38 = !DILocation(line: 5, scope: !30)
!39 = !DILocation(line: 6, scope: !36)
!40 = distinct !DISubprogram(name: "main", linkageName: "_ZN8rust_out4mainE", scope: !7, file: !6, line: 8, type: !41, isLocal: true, isDefinition: true, scopeLine: 8, flags: DIFlagPrototyped | DIFlagMainSubprogram, isOptimized: false, unit: !2, templateParams: !4, variables: !4)
!41 = !DISubroutineType(types: !42)
!42 = !{null}
!43 = !DILocation(line: 9, scope: !40)
!44 = !DILocation(line: 10, scope: !40)
!45 = !DILocation(line: 11, scope: !46)
!46 = !DILexicalBlockFile(scope: !40, file: !6, discriminator: 0)

例えば g の呼び出しでは、まずタプルを生成したあとに、そのタプルから再び値を取り出す処理が入っていることがわかる。(これらの無駄は最適化で除去されることが期待される。)

Rustの多相性にかかわる構文

概要: Rustの型多相性の詳しい挙動を調べる前に、まず構文を調べる。

型仮引数

型仮引数のフォーマットは以下の通りである。 (parse_generics)

  • <> で囲った部分に、型仮引数の名前をカンマ区切りで指定する。
  • 末尾のカンマは省略可能である。
  • 型仮引数は0個でもよいが、0個の場合は < > 自体省略できる。
type A = ();
type A<> = ();
type A<X> = ();
type A<X,> = ();
type A<X, Y> = ();
type A<X, Y,> = ();

型仮引数が指定できるのは以下の位置である。

関数とメソッド

fn f<X>() {}
trait Foo {
    fn f<X>() {}
}
impl A {
    fn f<X>() {}
}
impl Foo for A {
    fn f<X>() {}
}

トレイト

trait Foo<X> {}

実装

impl<X> A {}
impl<X> Foo for A {}

型定義(構造体/列挙体/共用体/型別名)

struct A<X> {}
struct A<X>();
enum A<X> {}
union A<X> {}
type A<X> = ();
// 関連型も型別名と似た構文を持つが、こちらは単相であり型引数をとらない。
trait Foo { type B; }
impl Foo for A { type B = (); }

実装と型定義については、型仮引数が使用されていないとエラーになる。具体的には以下の制約がある。

生存期間仮引数

生存期間仮引数のフォーマットは型仮引数と同じ位置に指定する。ただし以下の違いがある。 (parse_generics)

  • 生存期間のため ' のついた識別子を指定する。
  • 生存期間仮引数は、型仮引数よりも前に書く。
type A<'a, X> = ();

生存期間仮引数は、上記の型仮引数と同様、関数・メソッド・トレイト・実装・型定義のいずれの位置にも書くことができる。それに加えて、以下の3つの位置にも書くことができる。 (parse_late_bound_lifetime_defs) 特に最初の2つは高階トレイト境界(HRTB)と呼ばれている。

where節の述語の量化

fn f<F>(f: F) where for<'a> F: Fn(&'a [u8]) -> &'a u8 {}

トレイト境界の量化

fn f<F>(f: F) where F: for<'a> Fn(&'a [u8]) -> &'a u8 {}
fn f<F: for<'a> Fn(&'a [u8]) -> &'a u8>(f: F) {}

関数ポインタとトレイトオブジェクトの量化

// 高階の関数ポインタ型
let x : for<'a> fn(&'a [u8]) -> &'a u8;
// 高階のトレイトオブジェクト
let x : &for<'a> Fn(&'a [u8]) -> &'a u8;

型仮引数と同様、生存期間仮引数が使用されていないとエラーになる場合がある。具体的には以下の制約がある。

  • 構造体/列挙体/共用体が生存期間仮引数に対して双変である場合はエラーとなる。 (check_variances_for_type_defn)
  • 型別名で生存期間仮引数が使用されていなくても特にエラーにならない。 (1.16.0時点)
  • 実装で生存期間仮引数が使用されていなくても特にエラーにならない。 (1.16.0時点)
  • 高階量化で生存期間仮引数が使用されていなくても特にエラーにならない。 (1.16.0時点)

Self

Self は実装対象の型を示すキーワードであり、以下のように使われる。

  • トレイト宣言内では、型引数と似たような振舞いをする。
  • 実装内では、実装対象の型をあらわす省略記法のように振る舞う。

生存期間実引数と型実引数と型束縛

型実引数と生存期間実引数は、通常 ident<..> または ident::<..> の形で指定する。どちらになるかは文脈による。この形の構文は以下の通りである。 (parse_generic_args)

  • 生存期間実引数 'a, 型実引数 (e.g. Vec<u8>), 型束縛 (e.g. X=Vec<u8>) をカンマ区切りで指定する。
  • 末尾のカンマは省略可能である。
  • 実引数は0個でもよいが、0個の場合は ::<> または <> 自体省略できる。
  • 複数ある場合は、生存期間実引数→型実引数→型束縛 の順に書く。
A;
A<>;
A<'a, Vec<u8>, Y=&str>;
A<'a,>;

実引数の数は、仮引数の数と一致していなければならない。ただし、以下の条件では、実引数が丸ごと省略されたものとみなされる。

  • 指定された生存期間実引数が0個のときは、生存期間実引数が丸ごと省略されたものとみなされる。 (check)
  • 以下のような文脈において、指定された型実引数が0個のときは、型実引数が丸ごと省略されたものとみなされる。 (lowering, check)
    • 関数名
    • 構造体/列挙体/共用体の初期化 (構造体やバリアントの名前)
    • 構造体/列挙体のマッチング (構造体やバリアントの名前)

<>とは別に、丸括弧を使って型実引数と型束縛を指定する構文糖衣がある。これは現在の安定板では FnOnce, FnMut, Fn の3つのトレイトに対してのみ使える。詳しくは過去の記事を参照。

  • X(A, B, C) のように書くと、 X<(A, B, C), Output=()> として解釈される。
  • X(A, B, C) -> D のように書くと、 X<(A, B, C), Output=D> として解釈される。
  • ただし、生存期間が省略されている場合、この部分で局所的に解決されるという違いがある。

修飾パス

Self はトレイトにとっては暗黙の型引数のように振る舞う。これに対する実引数を指定するのが <SelfType as Trait> 記法である。

また同種の記法で、Self だけを指定してトレイト側を省略することもできる。 <SelfType> 記法がこれにあたる。これについては過去の記事を参照。

射影

多相なアイテムの中では型仮引数の関連型を参照することができる。これを射影といい、パスと同様に Trait::AssocType, <X as Trait>::AssocType, X::AssocType のように表記する。

関連型自身は単相であるが、これを含んでいるトレイトの型仮引数と Self に応じて変化する。したがて、射影は、トレイトの実引数と Self を受け取り、型を返す部分関数とみなせる。

型の境界指定

型に対して T: Trait + 'a のようにトレイトや生存期間による制約を加えることができる。この構文は以下の通りである。 (parse_ty_param_bounds)

  • 型のあとにコロンを指定し、その先に0個以上の(高階)トレイト境界または生存期間を + で繋いで指定する。末尾の + は省略できる。
  • (高階)トレイト境界には、 for による量化と ? による修飾を加えることができる。順番はこの順だが、同時に指定する意味はない。
  • for による量化は、前述のとおり生存期間のみ指定できる。
  • ?Sized のための特殊な構文である。 ?Sized と書くことで暗黙の Sized 指定を外すことができる。詳しくは過去の記事を参照。

型の境界指定は以下の場面で使うことができる。

型仮引数

fn f<X: Foo>() {}

where節

fn f<X>() where X: Foo {}

トレイト宣言 (スーパートレイト境界)

trait Foo : Bar {}

トレイトオブジェクト。ただし、「先頭はトレイトでなければならない」「先頭以外に指定できるトレイトは Send/Sync のみ」という制約がある。

fn f(_: &(Foo + Send)) {}

where節とスーパートレイト境界

where節は where の後にカンマ区切りで0個以上の型や生存期間の境界指定を書く。末尾のカンマは省略できる。1つも指定するものがないときは where ごと省略できる。

where が書けるのは以下の位置である。

関数とメソッド: 戻り値型の直後

fn f() -> () where {}
trait Foo {
    fn f() -> () where;
}
impl Foo for A {
    fn f() -> () where {}
}

トレイト: スーパートレイト境界の直後

trait Foo : Bar where {}

実装: トレイト名とSelf型の直後

impl A where {}
impl Foo for A where {}

タプル構造体: メンバ一覧の後

struct A where;
struct A(u32) where;

構造体(タプル構造体以外)/列挙体/共用体/型別名: 型仮引数リストの後

struct A where {}
enum A where {}
union A where {}
type A where = ();

前述のように、 where 節の各述語を for で量化できる。

fn f<F>(f: F) where for<'a> F: Fn(&'a [u8]) -> &'a u8 {}

型仮引数とスーパートレイト境界に指定されている型境界は where の構文糖衣とみなせる。

fn f<X: Foo>() {}
fn f<X>() where X: Foo {}
trait Foo : Bar {}
trait Foo where Self: Bar {}

生存期間の境界指定

型と同様に、生存期間にも境界指定がある。 'a: 'b + 'c のように、0個以上の生存期間を + で繋げて書く。末尾の + は省略できる。 (parse_lt_param_bounds)

fn f<'a, 'b: 'a>() {}
fn f<'a, 'b>() where 'b: 'a {}

1.16.0では末尾に + をつけられるが、その部分のコメントと矛盾しているためおそらくバグである。

生存期間の境界指定は、生存期間仮引数の位置か、 where 節に書くことができる。

等式述語

where 節には等式制約を書くための構文があるが、パーサーによる実装のみで他は全く未サポートである。2つの型を =/== で結べばよいが、 === のどちらが採用されるかも不明のため、現在のパーサーはいずれもサポートしている。

fn f<X: Foo>() where X::X = () {} // unsupported, but parsable
fn f<X: Foo>() where X::X == () {} // unsupported, but parsable

まとめ

Rustの多相性を正確に理解するにはさまざまな要素を把握する必要がある。今回はまず、「何が書かれうるか」を全体的に把握するために、関係する構文を洗い出してみた。

Rustで挿入ソート + 強制move outで高速化

挿入ソートは時間計算量  {O(n^{2})} のソートアルゴリズムであるが、特に入力  A の転倒数に対して  {O(\mathrm{inv}(A))} で抑えられること、また定数倍で高速なことから特定の場面で使われる場合がある。

Rustで挿入ソートを素朴に実装すると以下のようになる。

pub fn safe_insert_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while 0 < j && arr[j-1] > arr[j] {
            arr.swap(j-1, j);
            j -= 1;
        }
    }
}

しかし、 arr[i] をswapによっていちいち配列に書き戻していたり、配列の境界チェックをしていたりと、このコードには無駄がある。そこで unsafe を用いてより高速化することを考える。ここで参考になるのが std::mem::swap実装である。

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn swap<T>(x: &mut T, y: &mut T) {
    unsafe {
        // Give ourselves some scratch space to work with
        let mut t: T = uninitialized();

        // Perform the swap, `&mut` pointers never alias
        ptr::copy_nonoverlapping(&*x, &mut t, 1);
        ptr::copy_nonoverlapping(&*y, x, 1);
        ptr::copy_nonoverlapping(&t, y, 1);

        // y and t now point to the same thing, but we need to completely
        // forget `t` because we do not want to run the destructor for `T`
        // on its value, which is still owned somewhere outside this function.
        forget(t);
    }
}

Rustでは通常、borrowされているメモリ領域を未初期化状態にする処理はできない。そのような処理は必ずしもUB(未定義動作)ではないが、自分で安全性を確認した上で unsafe をつけて書く必要がある。

上記の swapソースコードには、これらを考慮した上で問題のないコードを書くのに必要な道具が揃っている。すなわち、

である。

これを使って、より効率的な挿入ソートを書いてみたものが以下である。

pub fn unsafe_insert_sort<T: Ord>(arr: &mut [T]) {
    let len = arr.len();
    let ptr = arr.as_mut_ptr();
    for i in 1..len {
        unsafe {
            let mut j = i;
            let mut t: T = std::mem::uninitialized();
            std::ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1);
            while 0 < j && *(ptr.offset((j-1) as isize)) > t {
                std::ptr::copy_nonoverlapping(ptr.offset((j-1) as isize), ptr.offset(j as isize), 1);
                j -= 1;
            }
            std::ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1);
            std::mem::forget(t);
        }
    }
}

これでだいたい3倍ほど速くなるようだ。(ベンチマーク結果は以下を参照)

コード全体とベンチマーク結果

#![cfg_attr(test, feature(test))]

#[cfg(test)]
extern crate test;
#[cfg(test)]
extern crate rand;

pub fn safe_insert_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while 0 < j && arr[j-1] > arr[j] {
            arr.swap(j-1, j);
            j -= 1;
        }
    }
}
pub fn unsafe_insert_sort<T: Ord>(arr: &mut [T]) {
    let len = arr.len();
    let ptr = arr.as_mut_ptr();
    for i in 1..len {
        unsafe {
            let mut j = i;
            let mut t: T = std::mem::uninitialized();
            std::ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1);
            while 0 < j && *(ptr.offset((j-1) as isize)) > t {
                std::ptr::copy_nonoverlapping(ptr.offset((j-1) as isize), ptr.offset(j as isize), 1);
                j -= 1;
            }
            std::ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1);
            std::mem::forget(t);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::fmt::Debug;
    use test::Bencher;
    use rand::{XorShiftRng, Rng, SeedableRng};
    fn test_sort<T: Ord + Clone + Debug>(arr: &[T]) {
        let mut arr1 = arr.to_vec();
        let mut arr2 = arr.to_vec();
        let mut arr3 = arr.to_vec();
        arr1.sort();
        safe_insert_sort(&mut arr2);
        unsafe_insert_sort(&mut arr3);
        assert_eq!(arr1, arr2);
        assert_eq!(arr1, arr3);
    }
    #[test]
    fn test_sorts() {
        test_sort(&[1, 2, 3, 4]);
        test_sort(&[4, 2, 3, 1]);
        test_sort(&[3, 2, 3, 0]);
        test_sort(&[3, 3, 6, 2, 1, 5, 7, 3, 1, 2]);
    }
    #[bench]
    fn bench_safe_insert_sort_by_worst(b: &mut Bencher) {
        let v : Vec<u32> = (0..1000).rev().collect();
        b.iter(|| {
            safe_insert_sort(&mut v.clone());
        })
    }
    #[bench]
    fn bench_unsafe_insert_sort_by_worst(b: &mut Bencher) {
        let v : Vec<u32> = (0..1000).rev().collect();
        b.iter(|| {
            unsafe_insert_sort(&mut v.clone());
        })
    }
    #[bench]
    fn bench_safe_insert_sort_by_uniform_random(b: &mut Bencher) {
        let mut v : Vec<u32> = (0..1000).collect();
        XorShiftRng::from_seed([189522394, 1694417663, 1363148323, 4087496301]).shuffle(&mut v);
        b.iter(|| {
            safe_insert_sort(&mut v.clone());
        })
    }
    #[bench]
    fn bench_unsafe_insert_sort_by_uniform_random(b: &mut Bencher) {
        let mut v : Vec<u32> = (0..1000).collect();
        XorShiftRng::from_seed([189522394, 1694417663, 1363148323, 4087496301]).shuffle(&mut v);
        b.iter(|| {
            unsafe_insert_sort(&mut v.clone());
        })
    }
}
[package]
name = "insert-sort"
version = "0.1.0"
authors = ["Masaki Hara <ackie.h.gmai@gmail.com>"]

[dependencies]
rand = "0.3"
$ cargo bench
   Compiling insert-sort v0.1.0 
    Finished release [optimized] target(s) in 1.75 secs
     Running target/release/deps/insert_sort-0526ddc8d41f2829

running 5 tests
test tests::test_sorts ... ignored
test tests::bench_safe_insert_sort_by_uniform_random   ... bench:     527,505 ns/iter (+/- 47,327)
test tests::bench_safe_insert_sort_by_worst            ... bench:     985,459 ns/iter (+/- 65,682)
test tests::bench_unsafe_insert_sort_by_uniform_random ... bench:     176,659 ns/iter (+/- 25,409)
test tests::bench_unsafe_insert_sort_by_worst          ... bench:     326,565 ns/iter (+/- 77,140)

test result: ok. 0 passed; 0 failed; 1 ignored; 4 measured

ベンチマーク環境は Rust nightly rustc 1.18.0-nightly (5309a3e31 2017-04-03), Ubuntu 16.04.1 over VirtualBox over Windows 10, Surface Pro 2

記事の更新頻度について

1日1回更新は一ヶ月続けることができた。ブログ駆動で色々調べる機会が得られたのはよかったが、さすがにこの頻度は大変なので、以降は2日に1回の更新にしようと思う。また、既存の記事の英訳をしてみるのもよいかもしれない。