安定化間近！Rustのimpl Traitを今こそ理解する

概要: impl Trait が安定化間近である。これはトレイトオブジェクトと似た用途を持つが、静的ディスパッチされSizedのまま使えるため効率的である。

impl Trait が安定化間近

Rustでは新規の機能はまずnightlyバージョンに「不安定機能 (unstable feature)」として取り入れられます。そこでの実験を経て、プログラミング言語Rustに半恒久的に導入してもよいと合意されたものだけが「安定化 (stabilize)」され、betaやstableバージョンのコンパイラでも使用できるようになります。

さて、現在 「impl Trait」と呼ばれる機能の安定化のめどがたったというアナウンスがありました。この機能は2016年夏ごろに実装され、長い間待ち望まれてきた目玉機能のひとつでしたが、ここにきてようやっと、という感じです。そこで、 impl Trait について今一度このブログで解説してみたいと思います。

impl Trait が使えると何が嬉しいのか

impl Trait は、戻り値型を隠蔽する(トレイトオブジェクトに代わる)手段を提供します。特に、クロージャやイテレータ、パーサコンビネータなど、型が煩雑になりがちなものを返したいときに有効です。 impl Trait を使うことで、

• クロージャのようにトレイトオブジェクトにより隠蔽するしかなかったケースでは、より効率的なコードを書ける可能性があります。
• イテレータやパーサコンビネータのように隠蔽せず型を書き下しているケースでは、煩雑な型を明示しなくてよくなる可能性があります。

impl Trait を今すぐ試すには

Rust Playgroundを使う場合は、以下の手順で試すことができます。

1. Rust Playgroundの右上にある "Nightly" を選択する。
2. コードの先頭に #![feature(conservative_impl_trait, universal_impl_trait)] を挿入する。
3. 以下にあるような例を書いて試す。

手元のRustで試す場合は、以下の手順が必要です。

1. rustup install nightly でnightlyをインストールする。
2. 以下のどちらかの方法でnightlyを有効にする。
   • cargo +nightly build のように、コマンドに毎回 +nightly をつけることで、一時的にnightlyを有効にできます。
   • 特定のディレクトリで rustup override set nightly を実行することで、そのディレクトリ内で半恒久的にnightlyを有効にできます。
3. コードの先頭に #![feature(conservative_impl_trait, universal_impl_trait)] を挿入する。
4. 以下にあるような例を書いて試す。

例1: クロージャを返す

与えられたクロージャを二回適用する別のクロージャを返すプログラムは、トレイトオブジェクトを使って例えば以下のように書けます。(Box<dyn Trait> は Box<Trait> の新しい記法です)

#![feature(dyn_trait)]

pub fn twice<'a, T: 'a>(f: Box<dyn Fn(T) -> T + 'a>) -> Box<dyn Fn(T) -> T + 'a> {
    Box::new(move |x| f(f(x)))
}

// もう少し使いやすいバージョン
pub fn twice<'a, T: 'a, F: Fn(T) -> T + 'a>(f: F) -> Box<dyn Fn(T) -> T + 'a> {
    Box::new(move |x| f(f(x)))
}

これは、 impl Traitを使うと以下のように書けます。

#![feature(conservative_impl_trait, universal_impl_trait)]

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

これで無駄な Box とおさらばすることができます。

例2: イテレータを返す

イテレータを返す関数も、以下のように簡単に書くことができます。

#![feature(conservative_impl_trait, universal_impl_trait)]

// 奇数を列挙するイテレータ
fn odds() -> impl Iterator<Item=i32> {
    (0..).map(|x| x * 2 + 1)
}

fn main() {
    println!("{:?}", odds().take(10).collect::<Vec<_>>())
}

例3: パーサーコンビネータを返す

以前の記事でも紹介したパーサーコンビネーターライブラリcombineの場合、以下のようにBoxやparser!を使わずに部品化することは以前から(場合によっては)可能でしたが、コンビネーターの構造が関数のシグネチャに反映されてしまうという問題がありました。

extern crate combine;
use combine::{Parser, Stream, many1};
use combine::char::{letter, spaces, Letter, Spaces};
use combine::combinator::{Many1, Skip};

fn word<I: Stream<Item = char>>() -> Skip<Many1<String, Letter<I>>, Spaces<I>> {
    many1(letter()).skip(spaces())
}

fn main() {
    println!("{:?}", word().parse("foo bar baz"));
    println!("{:?}", word().parse("012 foo bar baz"));
}

これは以下のように impl Trait を使うとすっきり抽象化することができます。

#![feature(conservative_impl_trait, universal_impl_trait)]

extern crate combine;
use combine::{Parser, Stream, many1};
use combine::char::{letter, spaces};

pub fn word<I: Stream<Item = char>>() -> impl Parser<Input = I, Output = String> {
    many1(letter()).skip(spaces())
}

fn main() {
    println!("{:?}", word().parse("foo bar baz"));
    println!("{:?}", word().parse("012 foo bar baz"));
}

impl Trait とは何か

以下、 impl Trait について詳しく説明していきます

型とトレイトは本来別物

Rustのトレイトは、C++のコンセプトやHaskellの型クラスに近いものです。型が値を分類するのに対し、トレイトは型自体を分類します。この点でJavaのインターフェースとは少し違います。(DefaultやEqなどがその例です。)

しかし、トレイトから型を作る構文が2つあります。それが dyn Trait と impl Trait です。(dyn Trait の dyn は省略可能) これらはどちらも、具体的な型を隠蔽して、実装しているトレイトにだけ注目するときに使いますが、dyn Traitは動的に、impl Traitは静的に解決されるという違いがあります。

dyn Trait の仕組みとデメリット

まずは見慣れた dyn Trait から説明します。 dyn Trait なんて見たことない、と思われるかもしれませんがそれもそのはず、この構文はRFC2113で変更されたばかりでまだ安定化されていません。Box<Trait>とか、トレイトオブジェクトといえば通じると思います。型とトレイトは本来別物なのに、構文からそれが見えないことが混乱のもとになっていたため、トレイトオブジェクトであることを明示するために dyn が導入されました。そのため、本記事では dyn Trait 構文を一貫して使うことにします。

dyn Trait の仕組みは、仮想関数テーブルを用いた動的ディスパッチです。 Box<T> を Box<dyn Trait> に変換するとき、元の型は忘れられてしまいますが、かわりにこのポインタがfatポインタになります。つまり、 T 自体へのポインタに加えて T の仮想関数テーブルへのポインタを保持するようになります。x86-64環境なら、 Box<T> は8byteなのに対して、 Box<dyn Trait> は16byteです。データ本体に仮想関数テーブルへのポインタを置くC++とは異なり、Rustではこのようにfatポインタ内仮想関数テーブルへのポインタを置きます。

この仕組みのため、dyn Traitにはいくつかのデメリットが存在します。まず、使えるトレイトが限定されます。 dyn Trait ではfatポインタから元の型由来の情報を復元するため、&self 引数が1個もなかったり、逆に複数ある場合には呼び出せなくなってしまいます。またfatポインタを使う都合上、selfのムーブ渡しはできません。これらの条件をオブジェクト安全性といいます。

また、必ずポインタ経由になるのと、間接コール命令になるため、実行効率が悪くなる可能性があります。

impl Trait の仕組みとデメリット

dyn Trait が dyn Trait という1つの型であったのに対して、 impl Trait は実はそういう型があるわけではありません。これらは匿名の型を表すためのシンタックスシュガーで、 impl Trait と書くたびに別の型に翻訳されます。そのため、構文上の使える場所が限られます。

実は、この impl Trait は、場所によって2通りに翻訳されます。

引数で使われた場合 (RFC 1591)

引数位置の impl Trait は、匿名の型引数に翻訳されます。頻出例は以下のようにコールバック関数を使う場合です。例えば、

#![feature(conservative_impl_trait, universal_impl_trait)]

// コールバックに42を渡すだけの関数
fn give_42_to_callback(callback: impl Fn(i32)) {
    callback(42)
}

という関数があった場合、これは以下のように翻訳されます。

// コールバックに42を渡すだけの関数
fn give_42_to_callback<F: Fn(i32)>(callback: F) {
    callback(42)
}

このように、 impl Trait が引数で使われた場合は、 Trait を実装する匿名の型引数に置き換えられます。したがって、引数位置の impl Trait は単なるシンタックスシュガーですが、これは戻り値位置の impl Trait を理解する上でも重要な点を含んでいます。つまり、

• 引数位置の impl Trait の型は、呼び出し側によって静的に決定される

ということです。

戻り値で使われた場合 (RFC 1522)

上に書いたことを戻り値で置き換えたものがそのまま成り立ちます。つまり、

• 戻り値位置の impl Trait の型は、呼び出された側によって静的に決定される

ということです。この「呼び出された側によって決まる型」は存在型といいますが、このための構文はまだRustには実装されていません。ここでは、将来実装されるであろうRFC2071から記法を借用することとすると、

#![feature(conservative_impl_trait, universal_impl_trait)]

// 42を返すクロージャを返す
fn defer_42() -> (impl Fn() -> i32) {
    || 42
}

は、以下のように匿名の存在型に置き換えられると考えることができます。

#![feature(???)]

// 42を返すクロージャを返す
fn defer_42() -> Anon1 {
    || 42
}
existential type Anon1: Fn() -> i32;

Fn() -> i32 を実装する特定の型だが、その中身が何なのかは明かされないのがポイントです。このexistential typeはnewtypeパターンとも似ていますが、クロージャのような特殊な型も含められることと、手動で Fn() -> i32 を実装しなくてもよいところが特徴です。

デメリット

されこの impl Trait ですが、まず使える場所が限られるのが一つ目のデメリットです。いくつか拡張案がありますが、今回安定化される conservative_impl_trait と universal_impl_trait では、関数/メソッドでしか使うことができません。また、トレイトメソッドの戻り値には使用できません。

もう一つのデメリットとして、あくまで元の型を型システム上隠蔽しているだけなので、動的に内容を切り替えることはできません。例えば、以下のように条件に応じて異なる型のイテレータを返すコードは、 impl Trait では実現できません。

#![feature(conservative_impl_trait, universal_impl_trait)]

use std::iter;

// nの倍数を列挙 (コンパイルエラー)
fn multiples_of(n: i32) -> impl Iterator<Item=i32> {
    if n == 0 { //~ERROR if and else have incompatible types
        iter::once(0)
    } else {
        (0..).map(move |m| n * m)
    }
}

ifを動かすなどして型を揃えるか、あきらめて dyn Trait を使うのが正解です。

#![feature(dyn_trait)]

use std::iter;

// nの倍数を列挙
fn multiples_of(n: i32) -> Box<dyn Iterator<Item=i32>> {
    if n == 0 {
        Box::new(iter::once(0))
    } else {
        Box::new((0..).map(move |m| n * m))
    }
}

ただし、上の例のような単純なケースであればeitherクレイトで解決できる場合もあります。(EitherはIteratorを透過する実装になっているため)

#![feature(conservative_impl_trait, universal_impl_trait)]

extern crate either;

use std::iter;
use either::{Left, Right};

// nの倍数を列挙
fn multiples_of(n: i32) -> impl Iterator<Item=i32> {
    if n == 0 {
        Left(iter::once(0))
    } else {
        Right((0..).map(move |m| n * m))
    }
}

より詳しい比較

ここから先は、 dyn Trait と impl Trait について、より詳しく比較しながら説明していきます。

書ける場所

dyn Trait は普通の型なので、型の出現する場所ならどこでも使えます。 (ただし、 Sized でないために限定される)

impl Trait は、今回安定化される範囲内では、以下の位置に出現できます。

• 関数(通常の関数、固有実装のメソッド、トレイトのメソッド、トレイト実装のメソッド) の引数と境界の中。 (#![feature(universal_impl_trait)])
• 関数のうち、「通常の関数」と「固有実装のメソッド」の戻り値。 (#![feature(conservative_impl_trait)])

ただし、丸括弧記法 (Fn(T) -> U の T と U の位置) には出現できません。また、 impl Trait の中に impl Trait をネストさせることもできません。

括弧の位置

dyn Trait と impl Trait の括弧の位置について、mini-RFC 2250 で議論中です。 &(x + y) や &(Trait + Send) との一貫性を保ちつつ、使いやすく間違いにくい構文が望まれていますが、残念ながら万能な方法はなさそうです。細かい論点があって整理するのが大変ですが、結論としては以下のような妥協点で落ち着きそうです。

• + は & より弱い。つまり、 + を使うときは &(dyn Error + Send) のように括弧を入れる必要がある。
• 同様に、 fn foo() -> impl Fn() -> (dyn Error + Send) のように Fn() -> の直後で + を使う場合も括弧が必要。
• 上との一貫性を保つため、 fn foo() -> (impl Error + Send) の位置にも(+を使う場合は)括弧が必要。

いずれにせよ、 dyn Trait と impl Trait はどちらも新規構文で、特に構文を分ける必要はないため、この2つの間の差異はなさそうです。

トレイト境界とライフタイム境界

dyn Trait と impl Trait では、書ける境界の種類が異なります。

• dyn Trait に書けるもの
  • ちょうど1個の主トレイト。object-safeでなければならない。必ず最初に書く。
  • 0個以上の追加トレイト。auto traitでなければならない。
  • 高々1個のライフタイム。0個の場合は省略されたとみなされる(推論方法は後述)。
• impl Trait に書けるもの
  • 1個以上のトレイト。順番に意味はないが、最初はトレイトでなければならない。
  • 0個以上のライフタイム。

トレイトがobject-safeであるとは、以下の条件を満たしていることをいいます。

• 直接的または間接的な出力が全て埋められている (e.g. dyn Iterator<Item=char> はOK, dyn Iterator はダメ)
• 直接的または間接的に Self: Sized を含意していない。 (e.g. dyn Default はダメ)
• 祖先トレイトを含む全てのメソッドがobject-safeである。メソッドがobject-safeであるとは、そのメソッドが Self: Sized を含意しているか、または以下の条件を満たしていることをいう。
  • 型パラメーターを持たない。
  • 第一引数が &self, &mut self, self: Box<Self> のいずれかである。
  • 他に Self が出現しない。 (Self::Item とかはOK)

auto trait は、名前通り auto trait で宣言されているトレイトで、 Send, Sync, UnwindSafe, RefUnwindSafe などがそれに当たります。

dyn Trait のライフタイムは大まかにいうと次のように推論されます。

1. 明示されているときはそれが使われる。
2. そうでないとき、 Trait に適切な Self: 'a 境界があればそれが使われる。例えば、 Box<dyn Any> は Box<dyn Any + 'static> である。 (RFC 0192)
3. そうでないとき、 dyn Trait が構文上参照で囲まれていればそれが使われる。例えば、 &'a dyn Fn() は &'a (dyn Fn() + 'a) である。 (RFC 0599)
4. そうでないとき、関数内の場合は匿名のライフタイムが割り当てられ、関数外のときは 'static が採用される。例えば、 Box<Fn()> を返す関数の戻り値は Box<Fn() + 'static> である。 (RFC 1156)

ライフタイムに関する仮定

dyn Trait と impl Trait では、ライフタイムに対する仮定は大きく異なります。

• dyn Trait の値は全く未知の型に由来する可能性があり、ライフタイムについては書かれている境界からしか推測できません。ライフタイムを省略した場合に上記のように推論されるのはそのためです。(0個=どのような生存期間も仮定できない、となってしまうため)
• impl Trait は「関数の型引数」と「関数のライフタイム引数のうち、impl Trait内に構文的に出現するもの」でパラメーター化されたnewtypeに過ぎないため、これらのパラメーターが生きていれば生きていることがわかります。

後者はわかりにくいので補足します。例えば、

fn foo<T, U>() -> impl Fn() { .. }

というシグネチャの場合、 impl Fn() にはライフタイム境界がついていません(dyn Traitと異なり、推論されているわけでもありません)。しかし、 dyn Trait とは異なり、この場合は impl Fn(): 'a となる十分条件が残されています。それは、 T: 'a, U: 'a となることです。(impl Fn() の中身は Anon1<T, U> のような型であるため)

同一性

上述のように、 dyn Trait は構文的に同じなら全て同じ型なのに対し、 impl Trait は出現ごとに全く異なる型になります。つまり、

fn foo1() -> Box<dyn Trait> { .. }
fn foo2() -> Box<dyn Trait> { .. }
fn foo3() -> impl Trait { .. }
fn foo4() -> impl Trait { .. }

に対して、 if true { foo1() } else { foo2() } は通りますが、 if true { foo3() } else { foo4() } はコンパイルエラーになります。

impl Trait の実際の型は位置だけではなくて、その関数のジェネリクス引数にも依存します。具体的には以下のジェネリクス引数に依存します。

• その関数の全ての型引数。
• その関数のライフタイム引数のうち、 impl Trait の境界部分に構文的に出現するもの。

以下の例を参照してください。

#![feature(conservative_impl_trait, universal_impl_trait)]

use std::fmt;

// T に依存したものは常に返せる
fn foo1<T: fmt::Debug>(x: T) -> impl fmt::Debug {
    x
}

// 'a に依存したものは返せない
fn foo2<'a>(x: &'a i32) -> impl fmt::Debug {
    x // ERROR
}
// 'a は明示的に含まれるため、 'a に依存したものも返せる
fn foo3<'a>(x: &'a i32) -> (impl fmt::Debug + 'a) {
    x
}

トレイトの透過性

dyn Trait も impl Trait も、基本的にその境界に書かれているトレイトのみを仮定できます。しかしたとえば以下のような例外があります。

• dyn Trait: !Sized である。 impl Trait: Sized である。
• dyn Trait: Drop である。 impl Trait: !Drop である。
• dyn Trait は、境界に書かれていない限り、auto trait (SendやSyncなど)を自動で導出することはない。一方、 impl Trait は、もとの型のauto traitを継承する。

まとめ

以下の内容を説明しました。

• impl Trait が安定化されると何が嬉しいのか？→クロージャなど特殊な型を使うコードが効率的・簡潔に書けるようになる。それがstableバージョンのコンパイラで使えるようになる
• impl Trait の試しかた
• dyn Trait と impl Trait の違い: どちらも型の素性を隠して「特定のトレイトを実装している」という風に抽象化するが、 dyn Trait は動的、 impl Trait は静的な抽象化をするため、使える場面に違いがある。
• より詳しい挙動の説明

追記 (2018/02/04): eitherクレイトを使った方法について説明しました。

Rust libstd内での特殊化の使用例 (1.23.0時点)

概要: Rust libstd内では既に特殊化が使用されているので、特定の条件を満たすことでより効率なコードが生成される。

PartialEq<[T]>

• 最適化される処理: スライスの比較処理
  • 間接的に最適化される処理: Vec<T>, str, String の比較など
• 条件: 内部トレイト BytewiseEquality が実装されている場合。具体的には要素型が u8, i8, u16, i16, u32, i32, u64, i64, usize, isize, char, bool の場合
• 理由: memcmpで効率的に比較できるため。
• ディスパッチ用トレイト: 内部トレイト SlicePartialEq

Vec<T>::from_iter, Vec<T>::extend (ムーブ)

• 最適化される処理: TのイテレータからのVec<T>の生成と延長
  • 間接的に最適化される処理: iter.collect::<Vec<_>>() など
• 条件1: unstableかつunsafeなトレイト TrustedLen が実装されている場合。これは size_hint が正確な長さを与えることをunsafeレベルで保証するトレイトである。 (ExactSizeIteratorはsafeであり、契約の内容も微妙に異なる)
  • [T], Option<T>, Result<T, E> 由来のイテレータと str.bytes(), iter::empty(), iter::once(), (n..m), (n..=m) は TrustedLen である。
  • rev(), cloned(), chain(), zip(), map(), enumerate() は TrustedLen を保つ。
• 理由1: 通常の生成/延長処理では、容量を気にしながら適宜再確保をする必要があるが、イテレータの長さが判明している場合は、最初に再確保したあとはループの各ステップでは容量チェックを省略できるから。
• 条件2: イテレータが vec.into_iter() 自体だった場合
• 理由2: 当該イテレータが一度も消費されていない場合、単にもとの vec を復元するだけでよいから。
• ディスパッチ用トレイト: 内部トレイト SpecExtend

Vec<T>::from_iter, Vec<T>::extend (参照)

• 最適化される処理: &TのイテレータからのVec<T>の延長 (T: Copy のとき可能)
• 条件: スライスの slice.iter() に由来するとき
• 理由: memcpy で効率よくコピー可能で、再確保も高々1回でよく、パニックガードが要らないから。
• ディスパッチ用トレイト: 内部トレイト SpecExtend (上と同じ)

BinaryHeap<T>::extend, LinkedList<T>::extend

• 最適化される処理: イテレータからのBinaryHeap<T>の延長とLinkedList<T>の延長
  • 間接的に最適化される処理: iter.collect::<LinkedList<_>>() など
• 条件1: BinaryHeap<T> を BinaryHeap<T> で延長する場合
• 理由1: swapして逆向きに追加したほうが速い場合や、ヒープの再ビルドをしたほうが速い場合がある。
• 条件2: LinkedList<T> を LinkedList<T> で延長する場合
• 理由2: 単に連結すればよい。
• ディスパッチ用トレイト: 内部トレイト SpecExtend

vec![x; n]

• 最適化される処理: vec![x; n] (内部的には隠し関数 alloc::vec::from_elem)
• 条件1: 要素型が u8
• 理由1: memset で効率的に塗れるため。
• 条件2: 要素型が u8, i8, u16, i16, u32, i32, u64, i64, u128, i128, usize, isize, f32, f64 で値が0のとき
• 理由2: memset で効率的に塗れるため。
• ディスパッチ用トレイト: 内部トレイト SpecFromElem

ToString

• 最適化される処理: to_stringによる文字列化 (一般には Display に対して実装される)
• 条件: str, Cow<'a, str>, String のいずれかの場合
• 理由: 文字列をコピーするだけだから。
• ディスパッチ用トレイト: なし (ToString を直接特殊化)

iter.zip

• 最適化される処理: iter.zip() で得られるイテレータの実装
• 条件: 内部トレイト TrustedRandomAccess が実装されている場合。これは名前の通りインデックスを引数としてアクセスする処理を実装し、それが本来のイテレータの動作と一致することを保証する。ただし、実際にランダムアクセスのために使われることはない。
  • slice.iter(), slice.iter_mut(), str.bytes() は TrustedRandomAccess である。
  • cloned(), zip(), map(), enumerate(), fuse() は TrustedRandomAccess を保つ。
• 理由: この特殊化により、slice1.iter().zip(slice2.iter()) のような場合に単一のインデックス変数でループするコードが生成され、効率が良くなるらしい。
• ディスパッチ用トレイト: 内部トレイト ZipImpl

iter.fuse

• 最適化される処理: iter.fuse() で得られるイテレータの実装
• 条件: unstableなトレイト FusedIterator が実装されている場合。つまり、元のイテレータが既に、「Noneを出力したら以降はずっとNone」という性質を満たしているとき。
• 理由: 既にfusedなので、self.doneフラグをチェックする必要がなくなる。
• ディスパッチ用トレイト: なし (Iterator, DoubleEndedIterator を直接特殊化)

Arc<[T]>::from, Rc<[T]>::from

• 最適化される処理: &[T] から Arc<[T]>, Rc<[T]> を作る処理 (一般には T: Clone なら使える)
• 条件: T: Copy のとき
• 理由: memcpy で効率的に複製できるし、 clone と違ってpanicしないのでパニックガードが要らない。
• ディスパッチ用トレイト: ArcFromSlice, RcFromSlice

PhantomDataまとめ

概要: PhantomData<T> には3つの異なる役割があり、多くの場合は PhantomData<fn() -> T> の形で使うのが無難である。

はじめに

PhantomData<T>は特殊な型で、中身を持たないにもかかわらず、型システム上は中身を持つかのように振る舞います。幽霊型 (phantom type) と関係はありますが、幽霊型そのものではないので注意が必要です。

PhantomData の基本的な使い方

幽霊型を使う場合や、何らかの理由で構造体の外部にある型を指定する必要がある場合を考えます。例えば、幽霊型で単位を区別する

// U は Meter や Miles のような型が入るとする
struct UnitFloat<U: Unit> {
    inner: f64,
}

や、外部にあるデータを参照する

struct ExtVec<T> {
    // 中身はなし
}

のような型を考えます。

これらの定義は型引数を使っていないので、以下のようにコンパイルエラーになります。

error[E0392]: parameter `U` is never used
 --> src/main.rs:2:18
  |
2 | struct UnitFloat<U: Unit> {
  |                  ^ unused type parameter
  |
  = help: consider removing `U` or using a marker such as `std::marker::PhantomData`

error[E0392]: parameter `T` is never used
 --> src/main.rs:5:15
  |
5 | struct ExtVec<T> {
  |               ^ unused type parameter
  |
  = help: consider removing `T` or using a marker such as `std::marker::PhantomData`

そのため、PhantomData と呼ばれる特殊な型を用いて、強制的に型引数を消費します。

use std::marker::PhantomData;
trait Unit {}
struct UnitFloat<U: Unit> {
    inner: f64,
    _marker: PhantomData<fn() -> U>,
}
struct ExtVec<T> {
    _marker: PhantomData<fn() -> T>,
}

ところで、この PhantomData<fn() -> U> を PhantomData<U> に置き換えてもコンパイルは通ります。しかし、この2つは微妙に動作が異なります。そこで以下に挙げるように、 PhantomData の動作を理解し、適切な型を選択するのが望ましいでしょう。(特に、 unsafe と組み合わせる場合)

PhantomData の3つの役割

PhantomData には3つの役割があります:

• 変性 (variance)
• 所有 (owns relation)
• 自動トレイトの制御 (auto trait opt-out)

変性 (variance)

前述のようにRustでは未使用の型引数・ライフタイム引数がコンパイルエラーになりますが、これは正確には、「双変な型引数・ライフタイム引数はコンパイルエラーになる」というように変性 (variance) を用いて説明されます。

Rustはライフタイムに関する限定的な部分型付けを採用しています。例えば、 'a : 'b ならば &'a T を &'b T と自然にみなすことができます (これを &'a T <: &'b T と書く)。この部分型関係が伝搬されるとき共変 (covariant)、逆向きに伝搬されるとき反変 (contravariant)** といいます。より正確には、

• 'a : 'b ならば T<'a> <: T<'b> のとき、 T は (そのライフタイム引数について) 共変 (covariant) である
• 'a : 'b ならば T<'b> <: T<'a> のとき、 T は (そのライフタイム引数について) 反変 (contravariant) である
• X <: Y ならば T<X> <: T<Y> のとき、 T は (その型引数について) 共変 (covariant) である
• X <: Y ならば T<Y> <: T<X> のとき、 T は (その型引数について) 反変 (contravariant) である

といいます。共変性と反変性は直交するので、実際には4通りのパターンがあります。4通りで区別する場合は、共変かつ反変であるとき双変 (bivariant) といい、共変でも反変でもないとき非変 (invariant) といいます。

多くの型は共変ですが、 &mut T は T について非変、 fn(T) は T について反変になります。

use std::marker::PhantomData;
// check_subtyping(T, U) : TがUの部分型のときだけコンパイルが通る
macro_rules! check_subtyping {
    ($a:ty, $b:ty) => {
        // coercionによる意図しない変換を防ぐため&&をつける
        |x: &&$a| -> &&$b { x };
    }
}

fn foo<'a: 'b, 'b>() {
    // &'a _ は共変
    check_subtyping!(&'a (), &'b ());
    // check_subtyping!(&'b (), &'a ());

    // &'a mut _ は共変
    check_subtyping!(&'a mut (), &'b mut ());
    // check_subtyping!(&'b mut (), &'a mut ());

    // &T は共変
    check_subtyping!(&&'a (), &&'b ());
    // check_subtyping!(&&'b (), &&'a ());

    // &mut T は非変
    // check_subtyping!(&mut &'a (), &mut &'b ());
    // check_subtyping!(&mut &'b (), &mut &'a ());

    // PhantomData<T> は共変
    check_subtyping!(PhantomData<&'a ()>, PhantomData<&'b ()>);
    // check_subtyping!(PhantomData<&'b ()>, PhantomData<&'a ()>);
}

fn main() {}

所有 (owns relation)

所有の概念はdrop checkerで使われます。drop checkerとは、「相互参照するデータがdropされたとき、後からdropされたデータのDrop::drop()が、既にdropされたほうのデータを参照できてしまう問題」に対処するための仕組みで、特定の条件下でライフタイムに真の包含関係を強制することで、これを回避します。

drop checkerの詳しい規則については他の資料 (Rustonomiconの説明や以前の記事) を参照してもらうとして、ここでは以下のことがわかっていれば十分です。

• 基本的には、所有している型が少ないほうがよい。 (所有している型が多いと、そのぶんdrop checkerが厳しくなってしまうので)
• ただし、unsafeな Drop 実装を持っているときは、所有関係が少なすぎると未定義動作になる可能性がある。

つまり、特にunsafeを使っていない場合は、所有している型をできるだけ少なく保つのが原則です。

ここで重要なのは、 PhantomData<T> は例外的に T を所有しているとみなされることです(これは[T; 0]についても同様です)。特に所有を明示する必要がなければ、 PhantomData<T> を直接使うのは避けたほうがよいでしょう。

自動トレイトの制御 (auto trait opt-out)

自動トレイトとは Send, Sync, UnwindSafe, RefUnwindSafe, Freeze (※コンパイラ内部トレイト) のように、型の構造に対して再帰的に自動適用されるトレイトのことです。これの適用規則は大雑把にいうと次のような感じです。

• 明示的な実装にマッチした場合は、それが採用される。
• 明示的な実装にマッチしなかった場合は、全てのフィールドが当該トレイトを実装していたら、全体もそれを実装しているとみなす。

ここでも PhantomData<T> は例外的に T をフィールドとして持っているとみなされることに注意が必要です。

継承リスト

以下に挙げるのは add_constraints_from_ty, dtorck_constraint_for_ty, constituent_types_for_ty から収集した変性・所有・自動トレイトの継承関係のリストです。

型	変性
&'a _	共変
&'a mut _	共変
Adt<'a>	Adtの変性による
dyn Trait + 'a	共変
dyn Trait<'a>	非変
Trait<'a>::Proj	非変

型	変性	所有	自動トレイトの継承
&T	共変	×	○
&mut T	非変	×	○
*const T	共変	×	○
*mut T	非変	×	○
fn(T) -> _	反変	×	×
fn() -> T	共変	×	×
[T; n]	共変	○	○
[T]	共変	○	○
(T, _)	共変	○	○
PhantomData<T>	共変	○	○
Adt<T>	Adtの変性による	フィールド次第	フィールド次第
<T as Trait>::Proj	非変	※1	※2
impl Trait<T>	非変	※1	※3
dyn Trait<T>	非変	○	※2

• ※1 未解決の射影型と匿名型は型仮引数と同じ扱い
• ※2 射影型と動的型は、明示されていない限り自動トレイトは推論されない
• ※3 匿名型の自動トレイトは、匿名型の実際の中身に依存して決まる
• ※ [T; n] は、 [T; 0] であっても同じように扱われる。
• ※ ライフタイムの変性は、コンパイラ中では上記とは正反対の記述になっている。これは 'a: 'b の向きをどう解釈するかの違いにすぎない。

上の表からわかるように、単に共変であることをいいたいときは PhantomData<fn() -> T> が適切です。

PhantomData<T> と [T; 0] の違い

PhantomData<T> と [T; 0] は似ていますが、以下の違いがあります。

• PhantomData<T> は T: Sized でなくてもよい。
• [T; 0] は構造体のサイズ計算に関与するため、 struct Foo([Foo; 0]); はエラーになる。 (ただしこの仕様は確定ではない)

まとめ

PhantomData<T> を使いたいときは、単に T に対して共変であることを示したいことがほとんどです。その場合、上の表からわかるように、 PhantomData<fn() -> T> を使うのが適当であるといえます。そうすることで余計な所有関係や自動トレイトの継承制約などが追加されることを防ぐことができます。

Vecと参照を同時に返す

概要: Rustでは Vec<T> とその要素への参照を同時に返すことはできないが、これを部分的に可能にするcrateはある。

やりたいこと

以下のように、 Vec<T> とその要素への参照を同時に返したい。(あるいは、こういった組を構造体に格納したい。)

fn foo() -> (Vec<i32>, &[i32]) {
    let v = vec![1, 2, 3];
    let s = &v[1..2];
    (v, s)
}

なぜできないか

Rustのライフタイムの枠組みでは、上のように(もし仮にコンパイルが通った場合に)実際に動作するパターンと、以下のように未定義動作になるパターンを体系的に区別することができない。

fn foo_invalid1() -> (Vec<i32>, &[i32]) {
    let mut v = vec![1, 2, 3];
    let s = &v[1..2];
    v.push(10); // pushによってリアロケーションが発生するとsが壊れる
    (v, s)
}

fn foo_invalid2() -> ([i32; 3], &[i32]) {
    let v = [1, 2, 3];
    let s = &v[1..2]; // vがムーブされるだけでsが壊れる
    (v, s)
}

つまり、親のムーブに対して不変な領域であることと、リアロケーションが発生しないことを保証する必要がある。

ライブラリレベルでのサポート

トレイトで上記の条件を保証することで、この需要に部分的に答えるライブラリがある。著名なものとしてowning_refとrentalがある。

owning_ref

[dependencies]
owning_ref = "0.3.3"

extern crate owning_ref;

use owning_ref::OwningRef;

fn foo() -> OwningRef<Vec<i32>, [i32]> {
    let v = vec![1, 2, 3];
    OwningRef::new(v).map(|v| {
        &v[1..2]
    })
}

このcrateで中心的な役割を果たしているのはowning_ref::StableAddressである (stable_deref_trait::StableDerefの別名であることに注意)。これは deref/deref_mut が常に同じポインタを返すという契約のもと unsafe になっている。より具体的には、これ自体がムーブされた場合と、 deref/deref_mut 先のオブジェクトに変更が加えられた場合に、ポインタが変化しないことが要求されている。

例えば、

• Vec<T>, Box<T>, Rc<T>, &T は StableAddress を実装している。 (アロケートされたポインタは不変のため)
• Cell<T>, RefCell<T> は StableAddress を実装していない。 (ムーブによりアドレスが変化してしまうため)
• 標準ライブラリにはないが、 deref_mut がポインタを変更するような型の場合は StableAddress を実装してはいけない。

StableAddress の前提のもと、例えば

• (Vec<T>, &[T]) と書きたかった部分は OwnedRef<Vec<T>, [T]> と書くことができる。
• 同様に (Rc<T>, &mut U) と書きたければ OwnedRefMut<Rc<T>, U> と書くことができる。

その他、 StableAddress だけではカバーできないユースケースのために ToHandle, ToHandleMut, CloneStableAddress が用意されている。

• ToHandle, ToHandleMut を実装している型に対しては OwnedHandle が使用できる。
• CloneStableAddress を実装している型に対しては OwnedRef がcloneできる。

rental

rental の安全性保証はowning_refと同じく、 StableDeref (StableAddress) に基づいている。こちらはユーザー定義の構造体に所有者と参照を同時に入れるためのマクロを提供する。

#[macro_use]
extern crate rental;

rental! {
    // rental! の直下はmodである必要がある
    pub mod foo_struct {
        // rental! の対象となる構造体には #[rental] か #[rental_mut] をつける
        #[rental]
        pub struct VecAndSlice<T: 'static> { // T: 'static が必要
            v: Vec<T>,
            s: &'v [T], // この 'v というライフタイム名は上の v というフィールド名と一致させる
        }
        // 生成されるメソッド
        // VecAndSlice::new(Vec<T>, f: F)
        //   fにはvをDerefしたものが渡される
        // VecAndSlice::try_new(Vec<T>, f)
        //   fがResultを返すときに使う (TryNewResultが返ってくる)
        // VecAndSlice::try_new_or_drop(Vec<T>, f)
        //   try_newと似ているが、fがErrを返したらVecは解放される。
        // unsafe VecAndSlice::borrow(&self)
        // unsafe VecAndSlice::borrow_mut(&mut self)
        //   危険を承知で、ポインタを直接取得する。
        // VecAndSlice::rent(&self, f: F)
        //   fは参照を受け取る。
        // VecAndSlice::rent_mut(&self, f: F)
        //   fはmutableな参照を受け取る。
        // VecAndSlice::ref_rent(&self, f: F)
        // VecAndSlice::ref_rent_mut(&self, f: F)
        //   rent, rent_mutに似ているが、当該の参照を返したいときに使う。
        // VecAndSlice::maybe_ref_rent(&self, f: F)
        // VecAndSlice::try_ref_rent(&self, f: F)
        // VecAndSlice::maybe_ref_rent_mut(&self, f: F)
        // VecAndSlice::try_ref_rent_mut(&self, f: F)
        //   ref_rent, ref_rent_mutに似ているが、OptionやResultが返される。
        // VecAndSlice::into_head(self)
        //   参照を捨てて、Vecだけを返す。
        //
        // また、 VecAndSliceはDerefとAsRefを実装する。
    }
}

use foo_struct::VecAndSlice;

fn foo() -> VecAndSlice<i32> {
    let v = vec![1, 2, 3];
    VecAndSlice::new(v, |v| {
        &v[1..2]
    })
}

rental!マクロが生成するメソッドの一覧はここには書いていないが、例を見るのが早い。

まとめ

Rustでは Vec<T> とその要素への参照を同時に返すことはできないが、これを部分的に可能にするcrateはある。

• owning_ref は、ヒープへの所有権とその借用を同時に持つための一般的な構造体を提供する。
• rental は、ヒープへの所有権とその借用を同時に持つ構造体を安全に定義するためのマクロを提供する。
• stable_deref_trait は、上記2つの安全性の基礎となる特徴づけを提供する。

Drop Checkerの規則をちゃんと理解する

概要: Drop CheckerはRustのボローチェッカに付属する追加の検査器で、コンパイラが自動で挿入するdrop処理の安全性を保証するためのものである。これの詳細な規則とその正当性を理解したかったので自分なりに整理した。

dropckの概要についてはRustonomiconの説明とか以前の記事とかを参照。

注意: 本記事の内容はコンパイラの実装との対応をとっていないので実際の実装とは異なる可能性がある。

規格

• RFC 0769: Sound Generic Drop
• RFC 1238: Nonparametric Dropck
• RFC 1327: Dropck Param Eyepatch

用語

• Drop::drop(): ユーザー定義のデストラクタ自体
• mem::drop_in_place(): 値をデストラクトするために Drop::drop() を再帰的に呼び出す一連の手続き

mem::drop_in_place() の実装は型ごとにコンパイラが生成するが、大雑把に言うと以下のようになる:

struct Foo {
    bar: Bar,
    baz: Baz,
}

fn drop_in_place<T>(foo: &mut T) where T == Foo {
    // Drop::drop() を呼ぶ (存在すれば)
    <Foo as Drop>::drop(foo);
    // 各メンバについて再帰的に呼ぶ
    drop_in_place(&mut foo.bar);
    drop_in_place(&mut foo.baz);
}

問題

mem::drop_in_place() の呼び出しを挿入するとライフタイム条件が壊れる

    {
+------ let x = ..;
| +---- :
| | 'in :
| +---- :
| 'out  << mem::drop_in_place(&mut x); >> // コンパイラが挿入するdrop
+------
    }

このとき、

• xの型自体に 'in が全く使えないのは困る。これは相互参照するデータを作るために必要。
• しかし、 drop_in_placeの途中で 'in は使えなくなるから、 drop_in_place が 'in に関してフルアクセスできる保証はない

解決方法

mem::drop_in_place の中では、 x に関係するライフタイム全てが有効であるとは限らないことにする。例えば、 x: Foo<'a> を使う関数は、通常 'a がまだ有効であることを仮定してよいが、 mem::drop_in_place に関してはこれを仮定できない場合がある。そのかわり、以下のルールに従って、一部のライフタイムに関してだけは、その有効性を仮定してよい。

コンパイラは、それらのライフタイムが上記の 'out まで生存すること (つまり 'in よりも真に長く生存すること) をチェックする。

drop_lifetimes 収集の流れ

mem::drop_in_place<T> で有効性を仮定してよいライフタイムの一覧を drop_lifetimes(T) と呼ぶことにする。 mem::drop_in_place<T> は以下の手順で定義される。

1. Drop::drop() が触れうるライフタイムを列挙する。
2. mem::drop_in_place() がどのように再帰的に呼ばれうるかを調べる。
3. 1の情報を2の構造に沿って再帰的に収集する。

Drop::drop() が触れうるライフタイムの列挙

例として、 Foo<'a, 'b, T, U> という型を考える。この Drop::drop() が触れうるライフタイムの一覧を、以下のように保守的に列挙する。

Foo が Drop を実装していない場合

Drop で何もしないことがはっきりわかるので、どのライフタイムも必要ではない。

user_drop_lifetimes(Foo<'a, 'b, T, U>) = {}

Foo が Drop を実装している場合

保守的に、全てのパラメーターのライフタイムを仮定する。

user_drop_lifetimes(Foo<'a, 'b, T, U>) = {'a, 'b} ∪ {Tの全てのライフタイム} ∪ {Uの全てのライフタイム}

Foo の Drop 実装が #[may_dangle] を持っている場合

unsafe と #[may_dangle] を組み合わせることで、ユーザーの責任で「このライフタイムしか使わない」と宣言することができる。例えば、

unsafe impl<'a, #[may_dangle] 'b, T, #[may_dangle] U> Drop for Foo<'a, 'b, T, U> { .. }

の場合、

user_drop_lifetimes(Foo<'a, 'b, T, U>) = {'a} ∪ {Tの全てのライフタイム}

となる。

mem::drop_in_place() の再帰的呼び出し構造

この再帰呼び出し構造のことを、単に「型Tが型Uを所有する」ともいう。これは、「mem::drop_in_place<T>() の中で mem::drop_in_place<U>() が呼び出されうる」という関係を近似したものである。例えば、 struct や enum の drop_in_place 内では、全てのメンバの drop_in_place が呼び出されうる。

実際にコンパイラで検査をするさいは、循環的な所有関係があることに注意する必要がある。

この規則はほぼ上の説明通りだが、以下の2点に注意が必要である。

• PhantomData<T> は T を所有する。
• [T; 0] は T を所有する。

user_drop_lifetimes を再帰的に収集する

結局、 drop_lifetimes は以下のように定義される。

drop_lifetimes(T) = { 'a | T は U を所有し、 'a ∈ user_drop_lifetimes(U) である }

最終的な規約

• <T as Drop>::drop() 内では、 drop_lifetimes(T) (user_drop_lifetimes(T) ではないことに注意) の有効性のみを仮定できる。
  • #[may_dangle] を使わない限りは、自動的に保証される。
• 上記の規約により、 mem::drop_in_place<T>() も、 drop_lifetimes(T) の有効性のみを仮定すれば安全であることが保証される。
• 逆に、利用する側では、以下の条件がチェックされる: 型 T の値がdropされるとき、 drop_lifetimes(T) のライフタイムはその値よりも真に長く生存する必要がある。

最後に Rc で復習

Rc は以下のように定義されている。

struct Rc<T: ?Sized> {
    ポインタ,
    _marker: PhantomData<T>,
}

unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
    fn drop(&mut self) {
        ...
        mem::drop_in_place::<T>(ポインタ);
        ...
    }
}

ポイントとして、 Rc の Drop 実装は T に #[may_dangle] がついている。これは mem::drop_in_place::<T> を呼んでいるから、一見おかしいように見える。しかし実は問題ない。確かに、 #[may_dangle] の効果により

user_drop_lifetimes(Rc<T>) = {}

となるが、 PhantomData<T> があるので

drop_lifetimes(Rc<T>) = drop_lifetimes(T)

となる。

上の規約で

• <T as Drop>::drop() 内では、 drop_lifetimes(T) の有効性のみを仮定できる。

を

• <T as Drop>::drop() 内では、 user_drop_lifetimes(T) の有効性のみを仮定できる。

と書かなかったのはそのためである。

なお、 Rc で PhantomData<T> と #[may_dangle] をやめて

struct Rc<T: ?Sized> {
    ポインタ,
}

impl<T: ?Sized> Drop for Rc<T> {
    fn drop(&mut self) {
        ...
        mem::drop_in_place::<T>(ポインタ);
        ...
    }
}

としても安全だと思われる。しかし、この場合は

drop_lifetimes(Rc<T>) = drop_lifetimes(T)

ではなく

drop_lifetimes(Rc<T>) = lifetimes(T) (T の全てのライフタイム)

となってしまう。つまり、この状態だとdropckはより厳しい挙動をしてしまう。つまり、この2つの違いは、

• T の drop_in_place を呼ぶだけなら、 PhantomData<T> を使って #[may_dangle] T とすることで、 drop_lifetimes(T) の保証のみを得ることができる。
• T に対してより一般的な処理をするなら、何もしないことで lifetimes(T) の保証を得ることができる。 (そのぶんdropckが厳しくなる)

といえる。

RFC1238時代はどう違ったか

RFC1238とRFC1327の違いは、単に #[may_dangle] の粒度の違いだけである。

例えば、RFC1238では

impl<'a, 'b, T, U> Drop for Foo<'a, 'b, T, U> {
    #[unsafe_destructor_blind_to_params]
    fn drop(&mut self) { .. }
}

と書くと、今でいう

unsafe impl<#[may_dangle] 'a, #[may_dangle] 'b, #[may_dangle] T, #[may_dangle] U> Drop for Foo<'a, 'b, T, U> { .. }

と同じ意味になる。このように #[may_dangle] を一括で適用するしかないので、

unsafe impl<'a, #[may_dangle] 'b, T, #[may_dangle] U> Drop for Foo<'a, 'b, T, U> { .. }

と同等の記述はできない。

RFC0769時代はどう違ったか

RFC0769の時点ではパラメトリシティを用いて、より積極的に安全性を推論していた。パラメトリシティとは、例えば

fn foo<T: Sync>(x: T) { .. }

のような関数があったときに、 foo が x に対してできることは限られている (具体的には drop するか forget するくらいしかない) という仮定である。

この仮定が成立する理由は、 foo が x に関して、 Sized + Sync であるという限定的な情報しか持っていないからである。 x: T: Sync だとわかっても、 Sync は何もメソッドを持たないので、特にできることがないということになる。

しかし、現在はこのパラメトリシティという仮定は崩れている。特殊化を用いると、

fn foo<T: Sync>(x: T) {
    // 何もしない
}
fn foo<T: Sync + Foo>(x: T) {
    // TがFooを実装していたときは、何かをする
    x.foo();
}

のように、 T があるトレイトを実装しているときだけ実装を切り替えるということができる。(実際にはトレイト実装か固有実装を経由しないと特殊化できないので、もう少しコードを書く必要がある)

RFC0769時点では、このパラメトリシティを用いて「マーカートレイトのみを持つ型パラメーター」には自動的に #[may_dangle] が仮定される仕様だった。

RFC0769より前はどうだったか

RFC0769より前は、drop checkerはなかった。つまり現在でいうところの user_drop_lifetimes(T) = {} が仮定されていた。

これを保証するため、ジェネリクスパラメーターを持つ Drop は全てunsafeで、 #[unsafe_destructor] が必要だった。これがRFC0769の "Sound Generic Drop" という名称の由来である。

まとめ

Drop Checkerの規則について、 #[may_dangle] の意味を含めてまとめてみた。Drop で変な処理をするunsafeなコードを書くときはこの点を理解しておくとunsoundnessを踏み抜きにくくなると思われる。

SSHのホスト鍵設定

ホスト鍵とは

SSHの鍵はデジタル署名用の秘密鍵であり、本人確認に使われる。いわゆるid_rsaは、ユーザー側の本人確認のために使われる。

一方、SSHサーバー側も専用の秘密鍵を所有している。これは /etc/ssh/ssh_host_{dsa,ecdsa,ed25519,rsa}_key のような場所に保管されている。SSH接続の際には、これを使った公開鍵認証も行われる。クライアント側の .ssh/known_hosts と照らし合わせてチェックする。

ホスト鍵がないと何が問題か

もし悪意ある第三者が通信を盗聴・改竄できる場合、偽のサーバーと通信させることができてしまう。すると、適切な暗号を用いて全くの別人と会話しているという本末転倒な状態になる。偽のサーバー上と気付かずにsudoパスワードを入れたら困ったことになるかもしれない。

HashKnownHostsをオフにする

筆者は、ホスト鍵を安全に運用するために、HashKnownHostsをオフにするべきだと考えている。

そもそも HashKnownHosts とは、 .ssh/known_hosts においてホスト名をハッシュ化して保存するオプションである。ハッシュ化をしない場合、 known_hosts の各行は以下のようになっている。

example.com ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHayNTYAAAAIbmlzdHAyNTYAAABBBAHOh5LY0tU5hZGZn4iFvUQ9EJSGW7n9KbTXj5WK5AEIQNB5ShhNPwJcXqtc5hxwEmBX2VSdjUFkIT6U2Otur7w=

HashKnownHosts を使うと、「ホスト名またはIPアドレス」「署名方式」「公開鍵」のうち、「ホスト名またはIPアドレス」の部分がハッシュ化され、

|1|tbdGjw+HE9Clw2hC7ezBLOMGFGI=|xOtpgqDyfDlT/PB7cYm442R1+zY= ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHayNTYAAAAIbmlzdHAyNTYAAABBBAHOh5LY0tU5hZGZn4iFvUQ9EJSGW7n9KbTXj5WK5AEIQNB5ShhNPwJcXqtc5hxwEmBX2VSdjUFkIT6U2Otur7w=

のようになる(|1|ソルト|ハッシュ|)。ハッシュ化することで、

• 特定のホスト名が、この行に該当するかどうかは判定できる。
• しかし、この行だけ見て、ホスト名を復元することは困難である。

となる。つまり、

• HashKnownHosts のメリット: known_hosts が漏洩しても、接続先ホストの情報が復元できない。
• HashKnownHosts のデメリット: known_hosts の管理が困難になる。どのホストを信任しているかわからないため、偽のホストを信頼してしまう危険性が増える。

と考えられる。接続先ホストの情報は仮に漏れても大きな影響はなさそうだし、むしろ known_hosts が漏洩するような状況では秘密鍵など他の重要な情報も漏れている状況だから、メリットがデメリットに釣り合わないと思う。

known_hosts を管理する

ここでは、ホスト名のハッシュ化を止めた上で、 known_hosts をきちんと管理することを考えたい。前述のとおり、 known_hosts の基本フォーマットは

ホスト名またはIPアドレス 署名方式 公開鍵 (コメント)

である。また、 # で始まる行もコメントである。

「ホスト名またはIPアドレス」の部分の詳細なフォーマットは以下の通り。

• 基本的には、 gitlab.com とか 52.167.219.168 のようにホスト名またはIPアドレスがそのまま使える。
• 22番以外のポートのときは、 [example.com]:60022 とか [192.0.2.23]:60022 のように[]づけで表記する。
• , で複数のホスト名またはIPアドレスを並べることができる。ホスト名とIPアドレスを並べてもよい。 (ハッシュ化していないときのみ)
• * は0文字以上のワイルドカードとして使える。 (ハッシュ化していないときのみ)
• ? は1文字のワイルドカードとして使える。 (ハッシュ化していないときのみ)

例えば、GitHubとGitLabのための known_hosts は以下のように書ける。

# GitHub -- marked CheckHostIP no
github.com ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEAq2A7hRGmdnm9tUDbO9IDSwBK6TbQa+PXYPCPy6rbTrTtw7PHkccKrpp0yVhp5HdEIcKr6pLlVDBfOLX9QUsyCOV0wzfjIJNlGEYsdlLJizHhbn2mUjvSAHQqZETYP81eFzLQNnPHt4EVVUh7VfDESU84KezmD5QlWpXLmvU31/yMf+Se8xhHTvKSCZIFImWwoG6mbUoWf9nzpIoaSjB+weqqUUmpaaasXVal72J+UX2B+2RPW3RcT0eOzQgqlJL3RKrTJvdsjE3JEAvGq3lGHSZXy28G3skua2SmVi/w4yCE6gbODqnTWlg7+wC604ydGXA8VJiS5ap43JXiUFFAaQ==

# GitLab
gitlab.com,52.167.219.168 ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBFSMqzJeV9rUzU4kWitGjeR4PWSa29SPqJ1fVkhtj3Hw9xjLVXVYrU9QlYWrOLXBpQ6KWjbjTDTdDkoohFzgbEY=
gitlab.com,52.167.219.168 ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCsj2bNKTBSpIYDEGk9KxsGh3mySTRgMtXL583qmBpzeQ+jqCMRgBqB98u3z++J1sKlXHWfM9dyhSevkMwSbhoR8XIq/U0tCNyokEi/ueaBMCvbcTHhO7FcwzY92WK4Yt0aGROY5qX2UKSeOvuP4D6TPqKF1onrSzH9bx9XUf2lEdWT/ia1NEKjunUqu1xOB/StKDHMoX4/OKyIzuS0q/T1zOATthvasJFoPrAjkohTyaDUz2LN5JoH839hViyEG82yB+MjcFV5MU3N1l1QL3cVUCh93xSaua1N85qivl+siMkPGbO5xR/En4iEY6K2XPASUEMaieWVNTRCtJ4S8H+9
gitlab.com,52.167.219.168 ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIAfuCHKVTjquxvt6CM6tdG4SLp1Btn/nOeHHE5UOzRdf

CheckHostIP をオフにする

ホスト鍵は基本的に、接続しようとしたDNS名と照合される。しかし、 CheckHostIP が有効の場合、IPアドレスに対しても照合が行われる。

普通、DNSの対応付けが変わっていても、接続先のサーバーが想定通りのホスト鍵を返せば信頼してもよいはずなので、 CheckHostIP は予防的な意味合いが強いと思われる。特に、GitHubのようにDNSラウンドロビンを使っている場合は面倒なので、上記のワイルドカードを使うか、そもそも CheckHostIP を外してしまうのがよいと思う。 (GitHubのIPアドレス一覧)

StrictHostKeyChecking の有効化

想定していないホスト鍵が送られてきたとき、SSHは以下のように振る舞う。

• 別のホスト鍵を既に知っている場合、問答無用で接続拒否になる。オレオレ詐欺で言うところの「母ちゃん俺だよ、携帯番号変えたからさ」というやつである。どうしても接続するならknown_hostsを手動かコマンドでいじる必要がある。
• 未知のホストの場合
  • StrictHostKeyChecking yes の場合: 接続拒否する。
  • StrictHostKeyChecking no の場合: known_hostsに追加して続行する。
  • StrictHostKeyChecking ask の場合(デフォルト): ユーザーの答えに応じて上のどちらかの処理をする。

.ssh/config に入っているホストにしか接続しないような生活であれば、どれもそれほど変わらないと思う。筆者は StrictHostKeyChecking yes にしておき、新規ホストを追加したとき、そのホストに対して一時的に StrictHostKeyChecking ask を付与している。

EC2への対処

EC2のように、同じIPアドレスのマシンを消したりまた立ち上げたりしていると、既知のホスト鍵との衝突でどうしても接続拒否になってしまう。せっかく known_hosts をちゃんと管理しているので、テキストエディタで消してしまうとよいと思うが、ホスト鍵のチェックを強制的に省略する方法もあるにはある。

UpdateHostKeys の有効化

UpdateHostKeys ask とすると、ホスト鍵が更新されたときに、新しいホスト鍵を known_hosts に追加することができる。(以前のホスト鍵で認証したあとで送られてくるので、問題はない。) サーバー側をうまく設定すれば、キーローテーションをすることもできる。

まとめと宣伝

known_hosts はちゃんと管理することもできる。ちなみに known_hosts と authorized_keys を正しくハイライトするVimプラグインを作ったのでぜひ。

再帰的余代数について

最近、再帰的余代数という概念について少し勉強したので、証明をまとめてPDFにした。

github.com

動機など細かいところには触れられていないが、以下のことが証明されている。

• 終再帰的余代数 = 始代数
• Setでは、再帰的ならば整礎