Rustのクエスチョンマーク

Rustに出現するクエスチョンマーク

let f = File::open("input.txt")?;

Rust 1.13で導入された機能で、ほぼ try! の構文糖衣である。

「ほぼ」というのは、 ? が将来的にはより汎用的に使えるように設計されているためで、 Result に限らない一般の std::ops:Carrier に対して動作する。

構文的には、 ? はメソッドチェーンと同じ優先度で解釈される。 (syntax::parse::parser 2495行目)

let j = a??.x?.f????().g().y??;
let j = ((((((((((((((a?)?).x)?).f)?))?)?)?)()).g()).y)?)?;

わかりやすく言うと ?try! の構文糖衣のようなものである。 try! の定義は以下の通り。(core::macros 309行目)

macro_rules! try {
    ($expr:expr) => (match $expr {
        $crate::result::Result::Ok(val) => val,
        $crate::result::Result::Err(err) => {
            return $crate::result::Result::Err($crate::convert::From::from(err))
        }
    })
}

ただし、 ? は Carrier による一般化を考慮に入れた実装になっている。 (rustc::hir::lowering 1762行目)

変換は処理系が行っている(AST→HIR変換時)が、同じものをマクロで書くなら以下の通り:

macro_rules! try {
    ($expr:expr) => (match $crate::ops::Carrier::translate($expr) {
        $crate::result::Result::Ok(val) => val,
        $crate::result::Result::Err(err) => {
            return $crate::ops::Carrier::from_error($crate::convert::From::from(err))
        }
    })
}

実質的には Carrier::translateT=Result<Self::Success, Self::Error> に対してのみ使われていて、一度 Result に変換して try! してまた Carrier に戻している動作に他ならない。

用途としては、効率化のために Result とは異なる構造を採用しているライブラリ(本当に効率化するのかは不明だが……)が Carrier を実装することで ? をサポートする、というのが考えられる。combine::ConsumedResult とか。

ただし、 Carrier による一般化は1.15.1時点では不安定機能に分類されている。

Rustのsize_of_valはどこで実装されているか

概要: std::mem::size_of_val はRustでもCでも実装できない。どこで実装されているかを調べた。

size_of_val が特殊な理由

std::mem::size_of_valstd::mem::size_of の親戚である。 size_of はCのsizeofと似たようなものだと言ってよい。 RustはCとは異なり、値によってバイト数が異なるような型 ([T], str, trait objects, dynamically sized structures) があり、これらの型に対して一般化されたsizeofが size_of_val である。

Rustの標準ライブラリの関数の多くは、通常のRustのコードとして実装されている。そうでなくても、ほとんどはunsafe Rustや、 extern "C" を用いた外部関数として与えられている。

size_of_val はRustのプリミティブであるからRust/unsafe Rustでは書けないし、多相だからCの外部関数としては書けない。

size_of_val のライブラリ定義

std::memcore::mem の別名である。 (std 375行目)

#[stable(feature = "rust1", since = "1.0.0")]
pub use core::mem;

core::mem::size_of_valcore::intrinsics::size_of_val をsafeに言い換える薄いラッパーである。 (core::mem 217行目)

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn size_of_val<T: ?Sized>(val: &T) -> usize {
    unsafe { intrinsics::size_of_val(val) }
}

そして、 core:intrinsics::size_of_valextern "rust-intrinsic" で定義されている。 (core::intrinsics 622行目)

extern "rust-intrinsic" {
    ...
    pub fn size_of_val<T: ?Sized>(_: &T) -> usize;
    ...
}

extern "rust-intrinsic" はどこで処理されているのか

"rust-intrinsic" という文字列は syntax::abi 90行目 で解釈され、 syntax::abi::Abi::RustIntrinsic になる。

#[allow(non_upper_case_globals)]
const AbiDatas: &'static [AbiData] = &[
    ...
    AbiData {abi: Abi::RustIntrinsic, name: "rust-intrinsic", generic: true },
    ...
];

HIRからMIRへの変換で関数呼び出し構文を処理する際に、 rustc_trans::callee::CalleeData::Intrinsic というマークがつけられる。 rustc_trans::callee 102行目

    pub fn def<'a>(ccx: &CrateContext<'a, 'tcx>,
                   def_id: DefId,
                   substs: &'tcx Substs<'tcx>)
                   -> Callee<'tcx> {
        ...
        if let ty::TyFnDef(.., f) = fn_ty.sty {
            if f.abi == Abi::RustIntrinsic || f.abi == Abi::PlatformIntrinsic {
                return Callee {
                    data: Intrinsic,
                    ty: fn_ty
                };
            }
        }
        ...
    }

Intrinsic のついた関数呼び出しは rustc_trans::mir::blockMirContext::trans_block という関数内で2つに分けて処理されている。

move_val_inittransmuterustc_trans::mir::block 432行目 で処理されている。

残りのintrinsicsは rustc_trans::mir::block 528行目 で処理され、コード生成は rustc_trans::intrinsic::trans_intrinsic_call に移譲されている。

ここに様々なintrinsic関数のコード生成処理が直書きされているが、今回の目当ての size_of_valrustc_trans::intrinsic 161行目 にある。

        (_, "size_of_val") => {
            let tp_ty = substs.type_at(0);
            if !type_is_sized(tcx, tp_ty) {
                let (llsize, _) =
                    glue::size_and_align_of_dst(&bcx.build(), tp_ty, llargs[1]);
                llsize
            } else {
                let lltp_ty = type_of::type_of(ccx, tp_ty);
                C_uint(ccx, machine::llsize_of_alloc(ccx, lltp_ty))
            }
        }

型に Sized がついている場合は size_of と同じ処理をしている。つまり、sizeofをコンパイル時に計算し、定数を入れるだけのLLVMコードを生成する。

Sized でない場合は、 rustc_trans::glue::size_and_align_of_dst を呼ぶ。この関数はなぜかDrop glue関連コードと一緒になっている。 (Drop glueからも利用されるからだと思われる)

pub fn size_and_align_of_dst<'blk, 'tcx>(bcx: &BlockAndBuilder<'blk, 'tcx>,
                                         t: Ty<'tcx>, info: ValueRef)
                                         -> (ValueRef, ValueRef) {
    ...
    match t.sty {
        ty::TyAdt(def, substs) => {
            ...
            let (unsized_size, unsized_align) = size_and_align_of_dst(bcx, field_ty, info);
            ...

            (size, align)
        }
        ty::TyDynamic(..) => {
            ...
            (bcx.load(size_ptr), bcx.load(align_ptr))
        }
        ty::TySlice(_) | ty::TyStr => {
            ...
            (bcx.mul(info, C_uint(bcx.ccx(), unit_size)),
             C_uint(bcx.ccx(), unit_align))
        }
        _ => bug!("Unexpected unsized type, found {}", t)
    }
}

確かに、Sizedでない型の成り立ちに応じて場合分けをしていることがわかる。

まとめ

size_of_val など、Rustの型システムに依存する一部のプリミティブはcompiler intrinsicsとして扱われ、その実装はコンパイラ自身が動的に生成している。

クロージャを boxせずに 返したい: Rustのconservative_impl_traitとimplementation leak

概要: 「クロージャを boxせずに 返したい」という欲求は人類の四大欲求のひとつと言われている。 conservative_impl_trait という機能を使うことでこれをスパッと解決できるが、これは単なる構文糖衣にとどまらずRustの型システムに食い込むこともあってかまだ安定版入りしていない。なぜこの機能が必要で、なぜこの機能が問題かを説明する。

クロージャをboxせずに返したい話

Rustではクロージャに異なる型がつく

OCamlHaskellのような言語では、外の環境を引き継ぐ無名関数 (クロージャ) を次のように作ることができるのであった。

let mult_curry x = fun y -> x * y

この関数は x を受け取り、「y を受けとってx * yを返す関数」を返す。この「y を受けとって x * y を返す関数」は、 y というデータを引き連れている。そして、この関数には int -> int という型がつく。

今度は恒等関数を考える。これはどのようなデータも引き連れていない。この関数にも int -> int という型がつく。つまり、OCamlでは、引き連れているデータに関係なく、引数・戻り値型が同じ関数には同じ型がつくことになる。これはHaskellでも同様である。

C++やRustではそのようにはならない。作成したクロージャごとに異なる型がつく。ただし、それらの型は Fn(...) -> ... というトレイトを通じて統一的に扱える、というわけである。

ここから先の話は、クロージャに限らず一般のトレイトに関しても正しい。わかりやすさのためにクロージャを中心に説明する。

Rustでクロージャに同じ型をつける方法

クロージャに同じ型をつけるには、trait objectの概念をつかう。trait objectは仮想関数テーブルを引き連れているので、元の型がわからなくても動的に正しい関数を呼び出すことができる。

例えば、関数fを受け取り、これを2回適用する別の関数を返すには、次のように書くことができる。

fn twice(f: Box<Fn(u32) -> u32>) -> Box<Fn(u32) -> u32> {
    Box::new(move |x| f(f(x)))
}

このように書いていけば、生存期間や所有権の問題は残るが、かなりOCamlHaskellに近い形で高階関数を書ける。ただし、trait objectはものによって大きさが異なるため、必ずポインタに包まなければならないし、動的ディスパッチになるため性能劣化が予想される。

静的ディスパッチでクロージャを受け取る

trait objectを使わずにクロージャを受け渡しする方法はあるが、引数と戻り値では方法が異なる。

クロージャを引数にする場合、次のように関数を多相にすればよい。

fn apply_twice<F: Fn(u32) -> u32>(f: F, x: u32) -> u32 {
  f(f(x))
}

こうすれば、クロージャの型に応じて、実際には別々の関数の実体を与えることができるため、呼び出し元がどのようなクロージャを用意しても正しく受け渡しができる。

静的ディスパッチでクロージャを返す

一方、クロージャを返すのは難しい。クロージャを受け取るときは、クロージャの型を決めるのは呼び出し元だから、全称型に相当する <> を使えばよかったが、クロージャを返すときは、クロージャの型を決めるのは自分自身だから、存在型に相当する機能が必要になる。

現在できる方法は、クロージャ型に名前をつけてしまうことである。例えば、先ほどの関数 twice を静的ディスパッチで実装すると次のようになる。

#![feature(unboxed_closures, fn_traits)]

struct Twice<F: Fn(u32) -> u32>(F);

impl<F: Fn(u32) -> u32> FnOnce<(u32,)> for Twice<F> {
    type Output = u32;
    extern "rust-call" fn call_once(self, args: (u32,)) -> Self::Output {
        self.call(args)
    }
}
impl<F: Fn(u32) -> u32> FnMut<(u32,)> for Twice<F> {
    extern "rust-call" fn call_mut(&mut self, args: (u32,)) -> Self::Output {
        self.call(args)
    }
}
impl<F: Fn(u32) -> u32> Fn<(u32,)> for Twice<F> {
    extern "rust-call" fn call(&self, args: (u32,)) -> Self::Output {
        self.0(self.0(args.0))
    }
}

fn twice<F: Fn(u32) -> u32>(f: F) -> Twice<F> {
    Twice(f)
}

この方法の問題点は2つある:

  • クロージャ用トレイトの内部仕様はまだ確定していないため、stableでは使えない。(この問題はクロージャ特有であり、一般のトレイトには関係ない)
  • 上のコードを見ればわかる通り、この方法で書こうとすると骨が折れる。

conservative_impl_trait はこの2つ目の問題を解決する。ついでに1つ目の問題も解決されるが、 conservative_impl_trait 自身もunstableなため現状ではこの恩恵はない。

conservative_impl_trait の利点

impl Trait と存在型

conservative_impl_traitimpl Trait とよばれる構文を提供することからこの名がついている。この構文は実質的に存在型といえる。例えば、

impl Iterator<Item=u32> == 「Iterator<Item=u32> を実装する型 T があり、その型 T

ということになる。

この構文は2014年から提案されているようだが、このような型の扱いはかなり難しい。というのもRustでは型に関する多相性はコンパイル時に全て展開し尽くさなければならない (ただし、trait objectや Any など、動的に判定されるものは例外である) からである。

conservative_impl_trait は、この impl Trait 構文を使ってよい位置に強い制限をかけることで、あまり問題の起きない範囲内で存在型を実現しようというものである。具体的には、「関数(trait内を除く)の戻り値型の一部としてのみ、 impl Trait 構文を許容する」という制約をつける。

conservative_impl_trait を使ってクロージャを返す

実際に先ほどの例を conservative_impl_trait を使って書き換えると次のようになる。

#![feature(conservative_impl_trait)]

fn twice<F: Fn(u32) -> u32>(f: F) -> impl Fn(u32) -> u32 {
    move |x| f(f(x))
}

先ほどのとにかく骨が折れる方法に比べるとかなりスッキリしていて、 Twice<F> のような余計な型が出てこないために意味も読み取りやすくなっている。

conservative_impl_trait の仕組み

impl Trait は以下のように動作する。Rust HIRに型をつける際に、以下の処理が発生する。

  • impl Trait を、その関数の生存期間・型引数全てで量化する。これは ∀x∃y を ∃f∀x に変換する処理に他ならないため、skolemizationと呼ばれる。
  • impl Trait に固有のIDを割り振る。

impl Trait の実際の型は、関数の実装のコンパイルが終わった段階で確定する。これを、その impl Trait を使っている各部分に代入することで、 impl Trait が除去される。

この動作により、要するに上に挙げた3つめの twice が2つめの twice に変換される。

conservative_impl_trait の何が問題か

conservative_impl_trait の問題点は、おそらく「関数からのimplementation leak」に集約されると思われる。 conservative_impl_trait を導入すると、2種類の意味で、implementation leakが発生する。

そもそもRustの関数の型について

Rustは(おそらくコンパイル速度やコードの見通しの良さのために)、何でもは推論しない立場を取っている。とりわけこの思想が顕著なのが関数の型である。

HaskellOCamlでは、

f x y = x + y / y

のように実装だけ書くと、関数の型が推論される。しかしRustでは、 fn で定義される関数の型は推論せず、全てを明記しなければならないようになっている。例えば、

fn f() -> _ {
  return 10u32 + 2;
}

のように書くことは許されない。

Lifetime elision、あるいはライフタイムの省略はこの制約に対する例外に見えるが、そうではない。lifetime elisionでは、lifetimeは関数宣言の型から補完されるのであり、関数の実装から推論されるわけではない。

そのため、Rustでは関数の実装を変更しても、他の部分のコンパイルには影響が及ばないようになっている。

conservative_impl_trait はこの性質を破る。このことをここではimplementation leak / 実装リークと呼ぶことにする。(一般的な用語ではない)

conservative_impl_trait による実装リークその1

その1は「同じ型宣言をもつ関数が異なる型を返す」というものである。これは impl Trait の本質であるから避けようはないし、これ自体は大きな問題にはならないと思われる。ただし、以下のような現象が発生する。

#![feature(conservative_impl_trait)]

fn f1() -> impl FnMut(u32) -> u32 {
    |x| x
}
fn f2() -> impl FnMut(u32) -> u32 {
    let mut y = 0;
    move |x| std::mem::replace(&mut y, x)
}

fn main() {
    let cl1 = f1();
    let cl2 = f2();
    println!("{}", std::mem::size_of_val(&cl1));
    println!("{}", std::mem::size_of_val(&cl2));
}
0
4

このように、 f1f2 は同じ型宣言を持つが、異なる大きさの値を返す。

conservative_impl_trait による実装リークその2

上記のように impl Trait は関数ごとに異なる型を割り当てるが、それ自体はあまり問題にはならない。その型についてわかっている情報が「 Trait を実装していること」に限定されているからである。

ところが、実際には impl TraitTrait 以外のトレイトを実装することがある。まず何も言わなければ Sized が自動的に仮定される。これはそれほど問題にはならない。

もう1つの問題は、 SendSync が自動的に実装されることである。そしてこれは何と、関数の実装に依存して決まる

以下がその例である。 RcArcimpl AsRef で抽象化して返す2つの関数がある。型宣言は同じだが、片方は g に渡せるのに対しもう一方は g に渡すことができない。

#![feature(conservative_impl_trait)]

use std::rc::Rc;
use std::sync::Arc;
use std::convert::AsRef;

fn f1() -> impl AsRef<u32> {
    Rc::new(0)
}
fn f2() -> impl AsRef<u32> {
    Arc::new(0)
}

fn g<T:Send>(t: T) {}

fn main() {
    // g(f1()); // compile error
    g(f2());
}

まとめ

conservative_impl_trait は現在のRustに必須のデザインパターンを補う非常に有用な機能であると同時に、重要なabstraction boundaryのひとつを壊すという懸念がある。

gitコマンドがgitリポジトリを探す順番

概要: 多くのgitコマンドは特定のgitリポジトリに対する操作であるから、現在位置から対応するリポジトリを発見する必要がある。環境変数コマンドラインオプションで指定された場合を除き、gitはまず ./.git ファイル、 ./.git/ ディレクトリ、 . の3つを試し、それでだめなら再帰的に親ディレクトリを検索する。

gitリポジトリの検索結果を表示する

git rev-parse --git-dir
git rev-parse --show-toplevel

gitコマンドがgitリポジトリを探す順番

gitが処理をするときはまず、gitdirとworktreeと呼ばれる2つのディレクトリの位置を同定する必要がある。

gitコマンドがgitリポジトリを探す処理は、 setup.c の中の setup_git_directorysetup_git_directory_gentlysetup_git_directory_gently_1に記述されている。

まず、環境変数 GIT_DIR が設定されている場合は、これがそのままgitdirとして使われる。 (git コマンド全体のオプションである --git-dir は単に GIT_DIR をその場で設定するオプションである。) この場合のworktreeの発見手順は複雑だが、例えば GIT_WORK_TREE が設定されているときはこれがそのまま採用される。

GIT_DIR が設定されていない場合はまず以下の順にチェックする。

  1. ./.git という通常ファイルがあり、内容が gitdir:で始まっている。また続く文字列は別のディレクトリへのパスになっており、そのディレクトリはgitdirにふさわしい構造を持っている。このとき、この時点での . がworktreeになる。
  2. ./.git/ というディレクトリがあり、そのディレクトリはgitdirにふさわしい構造を持っている。このとき、この時点での . がworktreeになる。
  3. . というディレクトリがあり、そのディレクトリはgitdirにふさわしい構造を持っている。このときこのリポジトリはbare扱いで、worktreeは設定されない。

以上のチェックをしてもgitdirが見つからない場合は、ひとつ上のディレクトリにcdして同じ探索を繰り返す。ただし、以下の条件で探索を打ち切る。

  • / または、 GIT_CEILING_DIRECTORIES で指定されたディレクトリまで到達した。
  • 異なるファイルシステムに到達したが、 GIT_DISCOVERY_ACROSS_FILESYSTEM が設定されていなかった。

ところで、gitdirにふさわしい構造かどうかは is_git_directoryで判定されている。これは次の3つ全てがあるときにgitdirと判定している。

  • 適切にフォーマットされた ./HEAD ファイル。ただし適切にフォーマットされているとは次のいずれかの条件を満たすことをいう
    • refs/ 以下へのシンボリックリンクである。 (参照先の存在はチェックされない)
    • ref:と任意個の空白から始まる通常ファイルで、その続きには refs/ 以下のファイルへのパスが書かれている。 (参照先の存在はチェックされない)
    • 40桁の16進数(SHA-1ハッシュ)が書かれた通常ファイルである。
  • ディレクトobjects/ が存在する。ただし、 GIT_OBJECT_DIRECTORY 環境変数が存在するなら、 objects/ のかわりにこの環境変数の中身が使われる。
  • ディレクトrefs/ が存在する。

まとめ

上の発見手順からわかるように、non-bareリポジトリ内でも、特に .git 内からコマンドを呼び出している場合はbareリポジトリに準ずる扱いを受ける。(worktreeの内部ではないと判定される。)

Rustの字句

以下はRust1.15.1の syntax::parse::lexer をもとに作成したPEG風の字句規則である。

IdentStart <- [a-zA-Z_]
            / # Any Unicode scalar value >= 0x80 with XID_Start property
IdentContinue <- [a-zA-Z0-9_]
               / # Any Unicode scalar value >= 0x80 wih XID_Continue property
Whitespace <- # Any Unicode scalar value with PATTERN_WHITE_SPACE property
Ascii <- # Unicode scalar value from 0 to 0x7f, inclusive
Eof <- !.

Underscore <- "_" !IdentContinue
As         <- "as"       !IdentContinue
Box        <- "box"      !IdentContinue
Continue   <- "continue" !IdentContinue
Crate      <- "crate"    !IdentContinue
Else       <- "else"     !IdentContinue
Enum       <- "enum"     !IdentContinue
Extern     <- "extern"   !IdentContinue
False      <- "false"    !IdentContinue
Fn         <- "fn"       !IdentContinue
If         <- "if"       !IdentContinue
Impl       <- "impl"     !IdentContinue
In         <- "in"       !IdentContinue
Let        <- "let"      !IdentContinue
Loop       <- "loop"     !IdentContinue
Match      <- "match"    !IdentContinue
Mod        <- "mod"      !IdentContinue
Move       <- "move"     !IdentContinue
Mut        <- "mut"      !IdentContinue
Pub        <- "pub"      !IdentContinue
Ref        <- "ref"      !IdentContinue
Return     <- "return"   !IdentContinue
SelfValue  <- "self"     !IdentContinue
SelfType   <- "Self"     !IdentContinue
Static     <- "static"   !IdentContinue
Struct     <- "struct"   !IdentContinue
Super      <- "super"    !IdentContinue
Trait      <- "trait"    !IdentContinue
True       <- "true"     !IdentContinue
Type       <- "type"     !IdentContinue
Unsafe     <- "unsafe"   !IdentContinue
Use        <- "use"      !IdentContinue
Where      <- "where"    !IdentContinue
While      <- "while"    !IdentContinue
Trait      <- "trait"    !IdentContinue
Reserved <- ("abstract" / "alignof" / "become" / "do" / "final" / "macro"
           / "offsetof" / "override" / "priv" / "proc" / "pure" / "sizeof"
           / "typeof" / "unsized" / "virtual" / "yield") !IdentContinue
Keywords <- Underscore / As / Box / Continue / Crate / Else / Enum / Extern
          / False / Fn / If / Impl / In / Let / Loop / Match / Mod / Move
          / Mut / Pub / Ref / Return / SelfValue / SelfType / Static / Struct
          / Super / Trait / True / Type / Unsafe / Use / Where / While
          / Reserved
Ident <- !("r\"" | "r#" | "b\"" | "b'" | "br\"" | "br#" | Keywords)
         IdentStart IdentContinue*
Lifetime <- "'" (!(Keywords) IdentStart IdentContinue*) !("'")
          / "'static" !("'")

# These are usually treated as an Ident or Lifetime,
# but considered to be a keyword in special contexts.
Default <- "default" !IdentContinue
StaticLifetime <- "'static" !IdentContinue
Union <- "union" !IdentContinue

FloatExponent <- [eE] [+-]? [0-9_]+

FloatValue <- [0-9_]+ "." !("." | IdentStart) [0-9_]* FloatExponent
            / !("0e" | "0E") # Why this? Maybe just a bug
              [0-9_]+ [eE] FloatExponent

IntegerValue <- "0b" [01_]+
              / "0o" [0-7_]+
              / "0x" [0-9a-fA-F_]+
              / [0-9_]+ !([.eE])

NumberValue <- FloatValue
             / IntegerValue

NumberLiteral <- NumberValue (IdentStart IdentContinue*)?

ByteEsc <- "\\n" / "\\r" / "\\t" / "\\\\" / "\\'" / "\\\"" / "\\0"
         / "\\x" [0-9a-fA-F][0-9a-fA-F]
         / (!['"\r\n\t\\] Ascii)
CharEsc <- "\\n" / "\\r" / "\\t" / "\\\\" / "\\'" / "\\\"" / "\\0"
         / "\\x" [0-7][0-9a-fA-F]
           # Constraint 1: up to 6 digits
           # Constraint 2: must represent a Unicode scalar value
         / "\\u{" [0-9a-fA-F]+ "}"
         / (!['"\r\n\t\\] .)
NewlineEsc <- ("\\\n" | "\\\r\n") Whitespace*


StringLike <- "'" (CharEsc / "\"") "'"
            / "b'" (ByteEsc / "\"") "'"
            / "\"" (CharEsc / NewlineEsc / "\r\n" / ['\n\t])* "\""
            / "b\"" (ByteEsc / NewlineEsc / "\r\n" / ['\n\t])* "\""
            / "r\"" (!"\"" ("\r\n" / [^\r]))* "\""
            / "r#\"" (!"\"#" ("\r\n" / [^\r]))* "\"#"
            / "r##\"" (!"\"##" ("\r\n" / [^\r]))* "\"##"
            / "r###\"" (!"\"###" ("\r\n" / [^\r]))* "\"###"
            / "r####\"" (!"\"####" ("\r\n" / [^\r]))* "\"####"
            / "r#####\"" (!"\"#####" ("\r\n" / [^\r]))* "\"#####"
              ... (for arbitrary number of #s)
              ...
            / "br\"" (!"\"" Ascii)* "\""
            / "br#\"" (!"\"#" Ascii)* "\"#"
            / "br##\"" (!"\"##" Ascii)* "\"##"
            / "br###\"" (!"\"###" Ascii)* "\"###"
            / "br####\"" (!"\"####" Ascii)* "\"####"
            / "br#####\"" (!"\"#####" Ascii)* "\"#####"
              ... (for arbitrary number of #s)
              ...
StringLikeLiteral <- StringLike (IdentStart IdentContinue*)?

TokenInner <- Ident
            / Lifetime
            / Keywords
            / NumberLiteral
            / StringLikeLiteral
            / ";" / "," / "(" / ")" / "{" / "}" / "[" / "]" / "@" / "#" / "~"
            / "?" / "$" / "+" / "*" / "/" / "^" / "%"
            / ".." / "."
            / "::" / ":"
            / "==" / "=>" / "="
            / "!=" / "!"
            / "<=" / "<<" / "<-" / "<"
            / ">=" / ">>" / ">"
            / "->" / "-"
            / "&&" / "&"
            / "||" / "|"

NestedDocComment <- "/*" (!"*/" (NestedDocComment / "\r\n" / [^\r])) "*/"
NestedComment <- "/*" (!"*/" (NestedComment / .)) "*/"
DocComment <- ("///" !"/" / "//!") [^\r\n]* &("\r\n" / "\n" / Eof)
            / ("/**" / "/*!") (!"*/" (NestedDocComment / "\r\n" / [^\r])) "*/"
NormalComment <- "//" !("/" / "!") [^\n]* &("\n" / Eof)
               / "////" [^\r\n]* &("\r\n" / "\n" / Eof)
               / "/*" ![*!] (!"*/" (NestedComment / .)) "*/"

WhitespaceOrComment <- DocComment / NormalComment / Whitespace+

ShebangComment <- "#!" !"[" [^\n]*

Source = ShebangComment? (WhitespaceOrComment / TokenInner)* Eof

凡例

  • ここで文字といった場合はUnicode scalar value (Unicodeで定義される0以上0x10FFFF以下のコードポイントのうち、サロゲートペアのための0xD800から0xDFFFまでのコードポイントを除いたもの)である。
  • <- は非終端記号を定義する。
  • ダブルクオートで囲まれている部分は、それが示す文字列自身にマッチする。
  • [] で囲まれている部分は、それが示す文字クラスのうちの文字1文字にマッチする。
  • . は任意の1文字にマッチする。
  • / は左を優先的に試し、失敗したら右を試す。ただし今回の文法でこの非対称性を使っている場面はあまり多くない。
  • T*T を貪欲に0個以上読む。
  • T+T を貪欲に1個以上読む。1つも読めなかったら失敗とみなす。
  • T?T を貪欲に0個か1個読む。
  • !TT の否定先読み。
  • &TT の肯定先読み。

C言語のinline

C/C++のinlineで間違いやすい3つのポイントがある。

1つは、GCCは3種類の異なるinline仕様を使い分けているという点である。3種類とは、「C++のinline」「C90用のGCC拡張inline」「C99以降のinline」である。

2つ目は、inlineを使っても、コンパイラが必ずインライン化を行うとは限らないという点である。

3つ目は、inlineを使うときは、プログラマは必ず、コンパイラがインライン化を行えるように特定の配慮をしなければいけないという点である。

つまり、inline関数は、「実体がどこにあるか」「inline化のための情報が足りているか」という2つの状態を同時に制御する必要がある。この細かい扱いの違いがバージョンにより異なるということになる。

以下バージョンごとの解説。おそらく歴史的な導入順序とは逆になっている。

C99以降のinline

C99以降のinlineでは、次の2つの条件を独立に満足させればよい。

  1. inlineに関係なく、実体がちょうど1つ存在する。
  2. inline関数が宣言されている全ての翻訳単位で、対応する「インライン化用の定義」が存在している。 (翻訳単位: 拡張子cのファイル1個につき翻訳単位1個と思っておけばほぼ問題ない)

これを判定するには次の表を用いればよい。

inline宣言の例 定義(条件2) 実体(条件1)
inline void f(void); × void f(void);
extern inline void f(void); × void f(void);
static inline void f(void); × static void f(void);
inline void f() {} void f(void);
extern inline void f() {} void f() {}
static inline void f() {} static void f() {}

ここで「定義」は、インライン化用の定義が存在するかどうか?の意味である。「実体」はインライン化しない場合のための実体が出力されるかどうか?の意味である。

気をつけるべき点は、関数定義で inline だけを指定した場合である。よく表を見て意味を確認してほしい。

C90のGNU拡張inline

extern がほぼ正反対の意味で使われているのが最も大きな違いである。つまり、 inline とだけ書くと外部リンクされる定義が与えられ、 extern inline だとインライン化専用になる。

C++のinline

C++のinline関数は、複数の翻訳単位が実体を提供してもよい。このあたりはリンカが頑張る。そのため、 inlineextern inline の区別はなく、いずれの場合も実体が生成される。その他、宣言していてもodr-usedでない場合の制限が緩い、inline関数がstatic変数を持っていてもよいなどいくつかの違いがある。

互換性を高めるためには

GCC拡張の説明にも、互換性を高める方法が書いてある。

内部リンケージするなら、単に static inline を常に使う。

外部リンケージするなら、 inline のついていない外部リンケージの宣言と、 inline のみついた定義を、この順に書く。

RustのFn* trait

Rustにおけるクロージャとは、 Fn, FnMut, または FnOnce を実装した値にすぎない。これらを追ってみた。

Fnはどこから来たか

まず、 Fn/FnMut/FnOnceはキーワード/予約語ではない。syntax::symbolの一覧にない。

fn main() {
  let Fn = 0;
}

そこで、広く使われている Fn(u8, u8) -> u8 という記法がどのように実現しているかを追う。まず core::opsによると

#[lang = "fn_once"]
#[stable(feature = "rust1", since = "1.0.0")]
#[rustc_paren_sugar]
#[fundamental] // so that regex can rely that `&str: !FnMut`
pub trait FnOnce<Args> {
    /// The returned type after the call operator is used.
    #[stable(feature = "fn_once_output", since = "1.12.0")]
    type Output;

    /// This is called when the call operator is used.
    #[unstable(feature = "fn_traits", issue = "29625")]
    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

ここで出てくるattributeは以下の意味がある。

つまり、 #[rustc_paren_sugar] というフラグを立てることで特殊な記法を有効化していることがわかる。実際に実験してみると以下のようになる。

// #![feature(unboxed_closures)]

// #[rustc_paren_sugar]
// trait MyFn<Args> {
//     type Output;
// }
trait MyFn2<Args> {
    type Output;
}

fn test1<F>(f: F) where F: Fn(u8,u8) -> u8 {}
// fn test2<F>(f: F) where F: Fn<(u8,u8), Output=u8> {}
// fn test3<F>(f: F) where F: MyFn(u8, u8) -> u8 {}
// fn test4<F>(f: F) where F: MyFn<(u8,u8), Output=u8> {}
// fn test5<F>(f: F) where F: MyFn2(u8, u8) -> u8 {}
fn test6<F>(f: F) where F: MyFn2<(u8,u8), Output=u8> {}

fn main() {
    println!("Hello, world!");
}

上のコードでコメントアウトした部分はunstableで弾かれる。そこで2017/03/08時点のnightlyを使うと上でコメントアウトした部分も含めて全てコンパイルが通る。以下、 Fn* 系traitの内部構造について述べることはunstableであり、今後変更される可能性がある。

括弧記法はどこから来たか

これで、名前に関係なく T(X, Y) -> Z という形のトレイトがパースされるという予測がたった。実際に探してみると、syntax::parse::parserの型名をパースする部分にこの記述があった。

これによると、パースの段階では Foo<u8, ()>::Bar(str)::Baz(str) -> [u8]::Quux のような謎の物体も型名(path)として解釈されるようだ。このうち括弧がついている部分は ast::PathParameters::Parenthesized という補助的な情報が付与される。

ASTをHIRに落とす処理により、これはhir::ParenthesizedParameters に変換される。構造はASTのときとほぼ変わらない。

HIRに型をつける段階で convert_parenthesized_parameters により () 型引数が <> 型引数に変換される。この時点で <> との区別はなくなり、以下同様に取り扱われる。

Fnでのみ括弧が使える理由

それではトレイトによって () 記法が使えたり使えなかったりするのはどこで実現されているか。 #[rustc_paren_sugar]rustc_typeck::collect::trait_def_of_itemで処理されている。これを見ると TraitDef に単純にフラグが立てられているだけだということがわかる。実際の rustc::ty::trait_def::TraitDef::paren_sugar を見ると、このフラグによる利用制限は一時的なもので、将来的には撤廃する予定と書いてある。

そこで paren_sugar の利用場面を調べると、rustc_typeck::astconvの型代入を生成する関数で、以下のことがチェックされていることがわかる。

  • paren_sugar が有効なトレイトは、() 記法でのみ利用されている。
  • paren_sugar が無効なトレイトは、<> 記法でのみ利用されている。

クロージャートレイトのオーバーロード

Fn トレイトの定義を復習すると、引数の型は型引数、戻り値の型は関連型として扱われていた。つまり、トレイトとしての制約のみ考えると、

  • 同じ引数型に対して、複数の戻り値型を割り当てることはできない。
  • ただし、複数の異なる引数型を割り当てることはできる。

となるはずである。そこで実験してみると以下のようになる。

fn foo<F: Fn(u8, u8) -> u8 + Fn(u32, u32) -> u32>(f: F) {
    let x = f(6000, 8000);
}

fn main() {
    println!("Hello, world!");
}
error: the type of this value must be known in this context
 --> src/main.rs:2:13
  |
2 |     let x = f(6000, 8000);
  |             ^^^^^^^^^^^^^

error[E0059]: cannot use call notation; the first type parameter for the function trait is neither a tuple nor unit
 --> src/main.rs:2:13
  |
2 |     let x = f(6000, 8000);
  |             ^^^^^^^^^^^^^

error: aborting due to 2 previous errors

error: Could not compile `fn-impl-test`.

このように E0059 が出てしまう。

理由は正確にはわからなかったが、おそらく引数の型を推論できなかったために「タプルでもユニットでもない」と判断されたということのようだ。

まとめ

Fn(X, Y) -> Z のような記法は、lifetime elisionが行われるなどやや機能的に強力である点を除くと、基本的にトレイトのパラメーター指定の構文糖衣である。ただし、2つの記法の相互互換性にはまだ未確定の仕様が含まれているため、stableでは特定の記法しか利用できない。