Rustのlifetimeとvariance - happy developing

nomicon を読んでいてSubtyping and Variance の話がでてきたときにどうして継承の概念がないRustにvarianceの話がでてくるのかなと思っていました。
その後、Rustの動画をyoutubeに投稿されているJon GjengsetさんのCrust of Rust: Subtyping and Variance を見て自分なりにすこし理解が進んだのでブログに書くことにしました。

具体的にはnomiconに記載されているvarianceのテーブルのうち以下の理解を試みます。

	`'a`	`T`	`U`
`&'a T`	covariant	covariant
`&'a mut T`	covariant	invariant
`fn(T) -> U`		contravariant	covariant
`Cell<T>`		invariant

Subtypeの意味

形式的には２つの型があるときにあるかないかの関係。
メンタルモデルとしては、and moreとか、少なくとも同程度には役立つ(at least as useful as)と説明されています。
Cat is an Animal and more みたいな。

Lifetimeとsubtype

nomicon ではfairly arbitary constructと前置きをおきつつもlifetimeを型としてとらえることができると書かれています。
どういうことかというと、lifetimeはコードの領域(regions of code)のことで、コードの領域は含んでるか含んでないかの関係を考えることができる。あるコード領域('big)が別のコード領域('small)を含んでいるとき
'bigは'smallのsubtypeといえます。 subtypeの関係をand moreと考えると、'big is 'small and moreといえるので筋がとおっていますね。

こんなイメージ。

{ 
  let x: 'big = ...
  {
    let y: 'small = ...
    // ...
  }
}

'staticは他のlifetimeをoutlivesするので、全てのlifetimeのsubtypeと考えられます。

ただし、lifetimeそれ自体で単独の型になることはなく、かならず &'a u32やiterMut<'a, u32>のようにある型の一部として現れる。そこで、subtypeを組み合わせたときにどうなるのかの話になりvarianceがでてきます。

Variance

varianceとはtype constructorがもつ性質。Rustでいうtype constructorとは型TをうけとってVec<T>を返すVecだったり、&や&mutのこと。以後はnomiconの例にならってF<T>と書きます。
型Subが型Superのsubtypeとして、varianceはcovariant, contravariant, invariantの3種類に分類できます。
以下それぞれについて見ていきます。

covariant

F<Sub>がF<Super>のsubtypeならcovariant。
s: &'a str型に&'static strを渡せるのは、&がcovariantだからといえます。
('static subtype 'a) -> (&'static str subtype &'a str)
引数の型のsubtypeの関係が戻り値の型の関係にそのまま反映されるので素直で直感的な関係だと思います。

let s = String::new();
let x: &'static str = "hello world";
let mut y/* :&'y str */ = &*s;
let y = x;

contravariant

F<Super>がF<Sub>のsubtypeならcontravariant。
これだけみてもよくわからないので具体例をみていきます。

pub fn contravariant(f: fn(&'static str) -> ()) {
    f("hello")
}

この関数にfn(&'a str) -> ()な関数を渡せるということをいっています。 'aは'staticのsuper typeなのでFn(&'a str) -> ()はFn(&'static str)のsubtypeになります。
意味としては上記のcontravariant関数は渡された関数に'static lifetimeをもつ変数を渡してよびだしてくれると読めます。その関数に必ずしも永続する必要はなく渡した関数の実行中だけ有効な文字列で十分なclosureを渡せるという感じでしょうか。引数に対する制約を弱くした関数はつよい制約を要求する関数のsubtypeになると考えれば自然といえるのではないでしょうか。

invariant

もう一度variance表をみてみるとinvariantは以下のように定義されています。

	`'a`	`T`
`&'a mut T`	covariant	invariant

まずTについてinvariantからみていきます。Tについてinvariantなおかげで以下のようなコードのcompileがとおらないようになってくれます。

pub fn invariant_1<'a>(s: &mut &'a str, x: &'a str) {
    *s = x;
}

fn invariant_1_no_compile() {
    let mut x: &'static str = "hello";
    let z = String::new();

    // signature:  &mut &'a      str, &'a str
    // providing:  &mut &'static str, &'a str

    invariant_1(&mut x, &*z);

    drop(z);
    println!("{}", x);
}

もしcompileが通ってしまうと、'staticな参照のはずがdropされた領域を参照できてしまうことになってしまいます。
compile errorになってくれる理由は、&'a mut TがTについてinvariantなおかげで
&'a mut &'static strが&'a mut &'a strのsubtypeにならないからです。&'static strは&がcovariantなので&'a strのsubtypeですが、その関係は& mutで変換されると維持されません。

次に'aについてはcovariantについて。

fn test_mut_ref_covariant() {
    let mut y = true;
    let mut z /*&'y bool */ = &mut y;

    let x = Box::new(true);
    let x: &'static mut bool = Box::leak(x);

    z = x; // &'a mut bool <- &'static mut bool
}

Box::leak()でheapに確保した値の&'static mut参照を作れます。
&'a mut Tが'aについてはcovariantなおかげで、lifetimeがより長い場合には自然な代入が許可されますね。

`Cell<T>`

Cellについてはlifetime-variance-exampleに非常にわかりやすい例がのっています。 Cell<T>はTについてinvariantなのでCell<&'static str>はCell<&'a str>のsubtypeになれません。なので以下の関数はcompileできません。

fn cell_shortener<'a, 'b>(s: &'a Cell<&'static str>) -> &'a Cell<&'b str> {
    s
}

なんとなくですがCell<&'a str>型にCell<&'static str>をassignできても問題ないように思えます。しかし以下の例からそれは認められないことがわかります。

fn cell_counterexample() {
    let foo: Cell<&'static str> = Cell::new("foo");
    let owned_string: String = "non_static".to_owned();
  
    // If we pretend that cell_shortener works
    let shorter_foo = cell_shortener(&foo);
  
    // then shorter_foo and foo would be aliases of each other, which would mean that you could use
    // shorter_foo to replace foo's Cell with a non-static string:
    shorter_foo.replace(&owned_string);
  
    // now foo, which is an alias of shorter_foo, has a non-static string in it! Whoops.
}

https://github.com/sunshowers/lifetime-variance-example/blob/ac8fc6cbee7bfd9b70a8c58973a891ed8a5482a7/src/lib.rs#L62

たしかにCell<T>をcovariantにしてしまうと危険な操作が可能になってしまいます。
結局はinterior mutabilityを提供している型は実質的には&mutと同じことができることの帰結といえるんでしょうか。

具体例

`strtok`

ここではCrust of Rust: subtyping and Varianceでとりあげられていた例をみていきます。以下のような関数を考えます。

pub fn strtok<'a>(s: &'a mut &'a str, delimiter: char) -> &'a str {
    if let Some(i) = s.find(delimiter) {
        let prefix = &s[..i];
        let suffix = &s[(i + delimiter.len_utf8())..];
        *s = suffix;
        prefix
    } else {
        let prefix = *s;
        *s = "";
        prefix
    }
}

c++のstrtok という関数らしいです。処理内容自体は重要ではないのですが、引数の文字列sをdelimiterでsplitして最初のelementを返し、sを次のelementの先頭にセットします。連続してよぶことで、RustでいうところのsplitしてIteratorを取得する感じの関数です。

#[test]
fn test_strtok() {
    let mut x: &'static str = "hello world";

    strtok(&mut x, ' ');
}

strtokを上記のように呼び出すとcompile errorになります。

error[E0597]: `x` does not live long enough
   --> src/main.rs:115:16
    |
113 |         let mut x: &'static str = "hello world";
    |                    ------------ type annotation requires that `x` is borrowed for `'static`
114 |
115 |         strtok(&mut x, ' ');
    |                ^^^^^^ borrowed value does not live long enough
116 |     }

なにがおきているかというと

// 'aはgenericで 'xは具体的なlifetimeと思ってください。

// signature: <'a> &'a mut  &'a      str
// providing:      &'x mut  &'static str
               
// signature:      &'static &'static str
// providing:      &'x mut  &'static str

// signature:      &'static &'static str
// providing:      &'static mut  &'static str

変数xの'static lifetiemとstrtokのlifetimeの型からlifetime generic 'aが'staticと解釈され、最終的に
strtok(& /* 'static */ mut x)になってしまうが、xはstack変数なのでstaticではなく "does not live long enough"になってしまう。(という理解です)

そこでどうすればよいかというと、問題はstrtokのlifetime genericがひとつしかないために&mut x自体のlifetimeもひきづられて'satticになってしまうことだったので以下のように修正します。

pub fn strtok_2<'a, 'b>(s: &'a mut &'b str, delimiter: char) -> &'b str {/* */}

こうするとこでcompileがとおるようになりはれてテストも書けるようになりました。

// signature: <'a, 'b> &'a mut &'b      str
// providing:          &'x mut &'static str

// signature:          &'x mut &'static str
// providing:          &'x mut &'static str

#[test]
fn test_strtok() {
    let mut x: &'static str = "hello world";

    let hello = strtok_2(&mut x, ' ');
    
    assert_eq!(hello, "hello");
    assert_eq!(x, "world");
}

ちなみにこうでもOK
pub fn strtok<'s>(s: &'_ mut &'s str, delimiter: char) -> &'s str {/* */}

`evil_feeder`

次にnomiconの例をみてみます。

fn evil_feeder<T>(input: &mut T, val: T) {
    *input = val;
}

fn main() {
    let mut mr_snuggles: &'static str = "meow! :3";  // mr. snuggles forever!!
    {
        let spike = String::from("bark! >:V");
        let spike_str: &str = &spike;                // Only lives for the block
        evil_feeder(&mut mr_snuggles, spike_str);    // EVIL!
    }
    println!("{}", mr_snuggles);                     // Use after free?
}

この例も以下のように解釈されてcompile errorになります。

// signature: &'a mut T           , T
// providing: &'a mut &'static str, &'spike str

// signature: &'a mut &'static str, &'static str
// providing: &'a mut &'static str, &'spike str

となって、&'static strに&'spike strは渡せなくなります。

`MessageCollector`

最後にlifetime-variance-exampleにのっていた実際に遭遇しそうな&mutのvarianceが影響する例をとりあげます。リンク先のコードではより詳細にstep by stepの解説があります。

use std::collections::HashSet;
use std::fmt;

struct Message<'msg> {
    message: &'msg str,
}

struct MessageDisplayer<'a> {
    list: &'a Vec<Message<'a>>,
}

impl<'a> fmt::Display for MessageDisplayer<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for message in self.list {
            write!(f, "{}\n", message.message);
        }
        Ok(())
    }
}

struct MessageCollector<'a> {
    list: &'a mut Vec<Message<'a>>
}

impl<'a> MessageCollector<'a> {
    fn add_message(&mut self, message: Message<'a>) {
        self.list.push(message)
    }
}

fn collect_and_display<'msg>(message_pool: &'msg HashSet<String>) {
    let mut list = vec![];

    let mut collector = MessageCollector { list: &mut list };
    for message in message_pool {
        collector.add_message(Message { message });
    }

    let displayer = MessageDisplayer { list: &list };
    println!("{}", displayer);
}

error[E0502]: cannot borrow `list` as immutable because it is also borrowed as mutable
  --> src/main.rs:39:46
   |
34 |     let mut collector = MessageCollector { list: &mut list };
   |                                                  --------- mutable borrow occurs here
...
39 |     let displayer = MessageDisplayer { list: &list };
   |                                              ^^^^^
   |                                              |
   |                                              immutable borrow occurs here
   |                                              mutable borrow later used here

問題はMessageCollectorの定義にあります。

struct MessageCollector<'a> {
    list: &'a mut Vec<Message<'a>>
}

collector.add_message(Message { message }); ここのmessageのlifetimeが関数全体に及ぶのでひきづられてMessageCollectorのlistに対する&mut参照も関数全体におよび、compilerが&mutのlifetimeを縮めることができなくなってしまい、immutable refがエラーになってしまいます。

MessageCollectorの定義を以下のようにするとcompileがとおるようになります。

struct MessageCollector2<'a, 'msg> {
    list: &'a mut Vec<Message<'msg>>
}

impl<'a,'msg> MessageCollector2<'a,'msg> {
    fn add_message(&mut self, message: Message<'msg>) {
        self.list.push(message)
    }
}

まとめ

&,&mutはtype converterと考えるといろいろcompilerの挙動の説明がつく。
&mutにおける危険な操作がinvariantとして禁止されていたりとlifetimeが型として表現されている。
Drop checkの挙動を制御したりする関係で、PhantomData等で型のvarianceをコントロールするみたいなトピックについてはまだまだわかっていない。