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個読む。
• !T は T の否定先読み。
• &T は T の肯定先読み。

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関数は、複数の翻訳単位が実体を提供してもよい。このあたりはリンカが頑張る。そのため、 inline と extern 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は以下の意味がある。

• #[lang = "fn_once"] 言語処理系が、 fn_once という名前でこのtraitを発見できるようにする。
• #[rustc_paren_sugar] ←重要。後述
• #[fundamental] トレイト実装の一貫性に関するルールを一時的に緩める。

つまり、 #[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では特定の記法しか利用できない。

C言語における空白文字

C言語における空白文字は、文字列の一部分としてと、トークンを明示的に区切る (long long と longlong は違う) こと以外には基本的に無意味というように思える。しかしプリプロセッサレベルでは、以下の場面で意味がある。

includeの中身

通常 <stdio.h> のようなコード断片は < stdio . h > に分解されるが、includeディレクティブ(または一部のpragma)の中でのみ特別に <stdio.h> という1つのトークンとして認識される (C11/§6.4.7)。このトークンに \, //, /*, ', " を含めた場合の挙動は未定義だが、空白を入れることは許されている (C11/§6.4.7)。したがって、

#include <a  b   c>

においては(規格書を読む限りは)空白文字が意味を持つ。

ただし、Cの規格では、includeのファイル名の解釈自体が処理系定義であり (C11/§6.10.2)、規格で規定されているヘッダ名に空白はない (C11/§7.1.2)。

defineの直後

以下の2つは異なる意味を持つ。

#define f(x, y) (y, x)
#define f (x, y) (y, x)

試しに以下のように実行してみるとわかる。

$ gcc -E -
#define f(x, y) (y, x)
#define g (x, y) (y, x)
f(1, 2)
g(1, 2)
# 1 "<stdin>"
# 1 "<built-in>"
# 1 "<command-line>"
# 31 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<command-line>" 2
# 1 "<stdin>"


(2, 1)
(x, y) (y, x)(1, 2)

このように、Cの規格では「マクロ関数定義の場合は、マクロ名と括弧の間に空白を入れない」と明確に規定する (C11/§6.10) ことで、関数マクロと通常のマクロを区別している。

文字列化

マクロの # で文字列化したときには、空白の存在/非存在が保たれる。(C11/§6.10.3.2)

$ gcc -E -
#define str2(x) #x
#define str(x) str2(x)
str(1+1)
str(1 + 1)
str(1  +  1)
str(1 /* hoge */ + /* fuga */ 1)
# 1 "<stdin>"
# 1 "<built-in>"
# 1 "<command-line>"
# 31 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<command-line>" 2
# 1 "<stdin>"


"1+1"
"1 + 1"
"1 + 1"
"1 + 1"

コメントを空白文字に置き換えることは、規格で明示されている (C11/§5.1.1.2) 。複数の空白を1つの空白文字にまとめるかどうかは、処理系定義である (C11/§5.1.1.2) 。 ただし、文字列化されるさいは、どの種類の空白も空白文字に置き換えられる (C11/§6.10.3.2)。

まとめ

C言語のコードは trigraph処理→改行処理→PP字句解析→プリプロセス→真正な字句への変換→構文解析→…… という流れで処理される (C11/§5.1.1.2)。ただでさえプリプロセスと構文解析の2段階の処理があってややこしいが、プリプロセスで使われる字句データと構文解析で使われる字句データに微妙に違いがある点も見落とせない。空白はその例のひとつで、構文解析では意味をもたないがプリプロセスでは意味をもつ。

C言語の型の読み方

C言語の型の読み方の解説は探すと色々出てくるが、改めて自分で説明してみることにした。

用語説明

C言語のポインタ記法に代わる記法として、ここでは次のような記法を導入する。もちろんこれはC言語にはない。

• 型 T へのポインタを ptr<T> と書く。
• 型 T が n 個並んだ配列を arr<T, n> と書く。
  • 可変長配列を arr<T, *> と書く。
  • サイズ指定のない配列を arr<T,> と書く。
• 関数を fun<int(int, int)> のように書く。
  • ノンプロトタイプ関数を fun<int(*)> のように書く。

変数名について

C言語の型は、構文上は変数名とセットで扱われる。対応する変数がない場所では、単に変数名部分が省略されたものとして扱われる。

前処理1: K&R関数定義の場合

関数定義 ({} が後続する) で以下の条件に当てはまるときは、次のような処理をする。

• 引数部分が () の場合、ここに void を入れる。
• 引数部分が (x, y) のように変数名のみの場合、その直後に int x, y; のような宣言があるのでこれを処理する必要がある。(詳しい説明は省略)

ステップ1: 宣言指定子と宣言初期化子に分離する

以下に挙げるものが宣言指定子 (declaration specifier)である。

• 分類A: typedef extern static _Thread_local/thread_local auto register inline _Noreturn/noreturn _Alignas/alignas
• 分類B: const restrict volatile _Atomic/atomic
• 分類C: void char short int long float double signed unsigned _Bool/bool _Complex/complex struct union enum _Atomic()/atomic(), typedef名 (int32_t など)

これらを左から順に取り除いていって、残った部分 (変数名、ポインタ、配列、関数、初期化など) が宣言初期化子 (declarator-initializer)である。宣言初期化子はカンマ区切りで複数あるかもしれない。

例えば、

long const unsigned static long * volatile x[30] = {0}, (*y)[20];

の場合、以下のように分けられる。

• 分類Aの宣言指定子: static のみ
• 分類Bの宣言指定子: const のみ
• 分類Cの宣言指定子: unsigned, long, long
• 宣言初期化子その1 : * volatile x[30] = {0}
• 宣言初期化子その2 : (*y)[20]

宣言を分割する

1つの宣言に、複数の宣言初期化子がカンマで区切られている場合は、宣言を分割する。例えば、上の例の場合、

long const unsigned static long * volatile x[30] = {0};
long const unsigned static long (*y)[20];

と分割する。

ステップ2: 宣言指定子を並び替える

宣言指定子は3種類に分けられるので、分類する。

static const unsigned long long * volatile x[30] = {0};
static const unsigned long long (*y)[20];

ここで、「unsigned long long」という3つのキーワード(順不同だが重複は数える)の並びが、1つの型をあらわしている。わかりやすさのために、以降はアンダースコアで結ぶことにする。

static const unsigned_long_long * volatile x[30] = {0};
static const unsigned_long_long (*y)[20];

ステップ3: 宣言子を分解する

宣言子を以下のルールで分解する。

• T * q d → q ptr<T> d
• T d[q n] → q arr<T, n> d (nは特別な記号 * の場合や、何も書かれていない場合もある)
• T d(A x, B y) → fun<T (A x, B y)> d など
  • 例外1: T d() → fun<T (*)> d
  • 例外2: T d(void) → fun<T ()> d
• T (d) → T d

ただし、

• T は分類Aを除く宣言指定子部分である。
• d は宣言子である。
• q は分類Bの宣言指定子と同じもの。配列の場合はstaticも指定できるが今回は説明しない。

分類Aの宣言指定子と初期化子は変換に巻き込まない。複数のルールが適用可能なら上のほうのルールを優先する。

上記のルールは適用できなくなるまで繰り返す。宣言子についている皮を剥いでいって、剥いだ順に宣言指定子側に被せていく感じになる。つまり順番が逆になる。

例えば以下のように変形する。

static const unsigned_long_long * volatile x[30] = {0};
static volatile ptr<const unsigned_long_long> x[30] = {0};
static arr<ptr<const unsigned_long_long>, 30> x = {0};

static const unsigned_long_long (*y)[20];
static arr<const unsigned_long_long, 20> (*y);
static arr<const unsigned_long_long, 20> *y;
static ptr<arr<const unsigned_long_long, 20>> y;

ステップ4: 関数の引数を処理する

もし関数の型が含まれていたら、その引数もまた宣言である。そこでこの処理を再帰的に繰り返す。

関数の引数の変数名は無視できるので、削除する。

ステップ5: 配列型を変換する

関数の引数部分については、配列をポインタに降格させる。例えば、

fun<int (int, arr<arr<int, 20>, 10>)>

のような型の場合は、 arr<arr<int, 20>, 10> が関数の引数なのでこれをポインタに降格させて、

fun<int (int, ptr<arr<int, 20>>)>

とおく。この処理は上のように、配列が関数の引数の内部に間接的に出現する場合は関係ない。

※この処理は、配列がtypedefされた型に対しても行う。

また、関数の引数に間接的に出てくる配列の大きさが定数ではない場合は、これを * に置き換える。

ステップ6: 完成

おわり

まとめ

C言語の型の構文は、意味を素直に表現していないので混乱のもとである。しかし、「宣言子から皮を剥がしていく作業」の影響範囲をきちんと理解すれば特に怖いものではない。

Feedly用ブックマークレット

以前から使っていたものが微妙だったので作り直した。

Subscribe it with Feedly

JavaScript部分は以下のようになっている。

void(feedtag=document.evaluate('//link[@rel="alternate"][@type="application/atom+xml" or @type="application/rss+xml"]', document, null, XPathResult.ANY_UNORDERED_NODE_TYPE).singleNodeValue);
if(feedtag) {
  location.href='https://feedly.com/i/subscription/feed/'+encodeURIComponent(feedtag.href);
} else {
  window.alert('No feed found');
};

RustのSizedとfatポインタ

概要: RustにはSizedというトレイトがあり、一部の例外を除いて暗黙のうちに実装されている。Sizedが実装されていない型はDynamically Sized Typeと呼ばれ、これらのデータはfatポインタを経由してアクセスする。この仕組みを説明する。

Sizedの使い方はAPIリファレンス、The Bookの該当部分とその日本語訳、Rustonomiconの該当部分をまず読むとよい。

この記事では、コンパイラがSizedをどう実装しているかという観点からまとめ直してみた。

Sizedとは何か

Sizedは標準ライブラリで定義されているトレイトである。

pub trait Sized {}

Sizedトレイトは次の2つの意味をもつようだ。

• Sizedを実装する型は、全て同じバイト数である。C言語のsizeofに相当するstd::mem::size_of が使える。(Sizedでない場合は値によって異なるため、std::mem::size_of_valを使う)
• Sizedを実装する型は、データ本体以外の余計な情報を持たない。(逆に、Sizedでない場合は、余計な情報が必要になる。それらの余計な情報を持つためにfat pointerが採用される)

Sizedは実装を持たない「マーカートレイト」の一種であり、言語処理系によって特別扱いされている。

特別扱いその1: 暗黙の制約と暗黙の実装

プログラマが明示しなくても、型変数は Sized を実装していることが仮定される。例えば、

pub struct Foo<X>(PhantomData(X));

と書いた場合、 X:Sized が仮定される。例外は以下の3つである。

• トレイト宣言におけるトレイト自身は、 Sized を仮定しない。 (トレイトの型引数や関連型はこの限りではない)
• X: ?Sized という専用構文を使って、 Sized を仮定しないことを明示した場合。
• 組み込みのポインタ型と参照型。

また、 enum や struct でユーザーが定義した型は、全ての要素が Sized ならば、自動的に Sized の実装が与えられる。逆に、ユーザーが手動で Sized の実装を追加したり削除したりすることはできない。

特別扱いその2: プログラム中での要請

以下の状況で Sized が要請される。

• let やパターンマッチで束縛できる変数の型は Sized でなければならない。
• 関数の引数と戻り値の型は Sized でなければならない。
• structの最後を除く全ての要素と、enumの全ての要素は、 Sized でなければならない。

例えば、

fn f(a: [u8]);

という関数は書けない ([u8] はSizedではないため) が、

fn f(a: &[u8]);

という関数は書ける (&[u8] はSizedであるため) 。

特別扱いその3: ポインタの大きさ

Sized を実装しない型へのポインタは、通常fat pointerで実装される。

例えば、x86-64環境なら、 *const T, *mut T, &'a T, &mut 'a T, Box<T> などのポインタ自身の大きさは通常8byteだが、TがSizedでないときは16byteになる。

fat pointerは何を保持しているのか

Sizedでない型は限られる。具体的には:

• [i64] などのスライス。
• str 文字列スライス。
• Read や Fn(i32) -> i32 などのトレイトオブジェクト。
• Sizedでない要素を末尾にもつstruct。

これらの値へのポインタは16byteになる。最初の8byteにはデータの先頭番地が入っている。続く8byteには、以下の内容が入っている。

• &[i64] の場合: スライスの要素数。
• &str の場合: バイト数。
• &Read の場合: vtableへのポインタ。
• これらを末尾要素にもつstruct: 末尾要素のfat pointerの内容を継承する。

このことは以下のような実験で確かめられる。

use std::ops::Deref;

// xの中身をバイト列として見るための関数
fn as_raw_bytes<'a, T:?Sized>(x: &'a T) -> &'a [u8] {
    unsafe {
        std::slice::from_raw_parts(
            x as *const T as *const u8,
            std::mem::size_of_val(x))
    }
}

pub struct S<T:?Sized> {
    pub x: u8,
    pub y: T,
}

fn main() {
    let arr : [u16; 3] = [1, 2, 3];
    let arrref = &arr;
    let arrptr = &arr as *const [u16; 3];
    let arrslice = &arr[..];
    let arrsliceptr = &arr[..] as *const [u16];
    let strslice = "ほげ";
    let clos = |x, y| x + y;
    let closref : &Fn(u8, u8) -> u8 = &clos;
    let mut a = 0;
    let clos2 = |x| {a += x; a};
    let clos2ref : &FnMut(u8) -> u8 = &clos2;
    let sarr : Box<S<[u16; 3]>> = Box::new(S { x: 3, y: [1, 2, 3] });
    let sarrref = sarr.deref();
    let sslice : Box<S<[u16]>> = Box::new(S { x: 3, y: [1, 2, 3] });
    let ssliceref = sslice.deref();
    println!("arrref = {:?}", as_raw_bytes(arrref));
    println!("&arrref = {:?}", as_raw_bytes(&arrref));
    println!("&arrptr = {:?}", as_raw_bytes(&arrptr));
    println!("arrslice = {:?}", as_raw_bytes(arrslice));
    println!("&arrslice = {:?}", as_raw_bytes(&arrslice));
    println!("&arrsliceptr = {:?}", as_raw_bytes(&arrsliceptr));
    println!("strslice = {:?}", as_raw_bytes(strslice));
    println!("&strslice = {:?}", as_raw_bytes(&strslice));
    println!("closref = {:?}", as_raw_bytes(closref));
    println!("&closref = {:?}", as_raw_bytes(&closref));
    println!("clos2ref = {:?}", as_raw_bytes(clos2ref));
    println!("&clos2ref = {:?}", as_raw_bytes(&clos2ref));
    println!("sarrref = {:?}", as_raw_bytes(sarrref));
    println!("&sarrref = {:?}", as_raw_bytes(&sarrref));
    println!("ssliceref = {:?}", as_raw_bytes(ssliceref));
    println!("&ssliceref = {:?}", as_raw_bytes(&ssliceref));
}

arrref = [1, 0, 2, 0, 3, 0]
&arrref = [82, 202, 147, 108, 255, 127, 0, 0]
&arrptr = [82, 202, 147, 108, 255, 127, 0, 0]
arrslice = [1, 0, 2, 0, 3, 0]
&arrslice = [82, 202, 147, 108, 255, 127, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]
&arrsliceptr = [82, 202, 147, 108, 255, 127, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]
strslice = [227, 129, 187, 227, 129, 146]
&strslice = [128, 149, 8, 159, 82, 86, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0]
closref = []
&closref = [248, 201, 147, 108, 255, 127, 0, 0, 240, 199, 41, 159, 82, 86, 0, 0]
clos2ref = [231, 201, 147, 108, 255, 127, 0, 0]
&clos2ref = [216, 201, 147, 108, 255, 127, 0, 0, 32, 200, 41, 159, 82, 86, 0, 0]
sarrref = [3, 0, 1, 0, 2, 0, 3, 0]
&sarrref = [8, 0, 98, 112, 68, 127, 0, 0]
ssliceref = [3, 0, 1, 0, 2, 0, 3, 0]
&ssliceref = [16, 0, 98, 112, 68, 127, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

Sizedでない参照を作る方法

Sizedでない値を直接作ることはまずない。通常は何らかのポインタの形で存在する。これらのポインタは、Sizedな値へのポインタを型強制によって変換することで作ることが多い。例えば、

fn curried_add(x: i32) -> Box<Fn(i32) -> i32> {
    Box::new(|y| x + y)
}

のような関数を書いたとき、この Box::new が返すのは Box<Fn(i32) -> i32> ではない。このBoxが返すのは Box<SomeClosure> のように具体的なクロージャの型が判明した状態のBoxである。(もちろんこのクロージャには実際にはユーザーから見える名前はついていない。) そもそも Box::new は T: Sized を仮定しているから、これが Box<Fn(i32) -> i32> を直接返すことはありえない。

つまり Box<SomeClosure> から Box<Fn(i32) -> i32> への型強制が行われていることになる。この部分の仕様はまだ確定はしていないようだが、現状では次のように実装されている。

型強制が可能になる条件はいくつかあるが、ここでは std::ops::CoerceUnsized というトレイトの実装があるかチェックされる。これも言語処理系により特別扱いされているマーカートレイトである。つまりここでは、

impl CoerceUnsized<Box<Fn(i32) -> i32>> for Box<SomeClosure> {}

が定義されているかが調べられる。ここでBoxは

impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Box<U>> for Box<T> {}

を実装しているため、実際に必要なのは

impl Unsize<Fn(i32) -> i32> for SomeClosure {}

ということになる。これは言語処理系によって自動的に実装される。

CoerceUnsized は他の参照やスマートポインタにも実装されている。例えば &[1; 2; 3] を &[i32] と見なせるのも同じ仕組みだと思われる。

内部の仕組み

Sized は core::marker::Sized で定義されている。

Sizedの定義を見ると、普通のtraitのようにも見えるが、#[lang = "sized"] という記述がある。この lang という属性は、このアイテムが処理系によって特殊な扱いを受けることを表している。langは rustc::middle::lang_item で処理される。 lang="sized"という属性は lang_items::SizedTraitLangItem という名前がつけられ、この属性のついたアイテムを lang_items.sized_trait() で取得できるようになる。

Sized は言語処理系の以下の場所で特殊な扱いを受ける。

• 条件を満たしたstructやenumに自動的にSizedが付与される。
  • rustc_tyoeck::collect Sizedを付与していいか決めている。この sized_by_default は基本的にYesだが、trait宣言のSelfに対してのみNoとなる
  • rustc_typeck::astconv Sizedを付与している
• 必要な場面で自動的にSized制約が追加される。
  • rustc_typeck::check Sizedを制約に加える (パターンマッチの変数束縛、代入の左辺、関数の引数、関数の戻り値、構造体リテラルのメンバ)
  • rustc::ty::wf Sizedを制約に加える (配列とスライスの要素)
  • rustc_typeck::check::wfcheck Sizedを制約に加える(structの最後以外の全ての要素と、enumの全ての要素)
  • rustc_typeeck::collect ?Sized により制約を明示的に削除する
• rustc::traits::select 必要な場面で自動的にSized実装が追加される。
• rustc_typeck::coherence::orphan 手動でのSized実装の追加/削除を禁止する。
• 必要な場面で自動的にSizedが実装されているか検査される。
  • rustc::traits::object_safety トレイトオブジェクト作成時のobject safetyチェック
  • rustc_typeck::check::cast キャストにおけるsizedチェック (unsizedへの変換は不可能。sized ptrからunsized ptrへの変換は不可能。function ptrからunsized ptrへの変換は不可能。unsized ptrからアドレスへの変換は不可能。アドレスからunsized ptrへの変換は不可能。)