Rustで自己参照構造体が作れない理由と解決法


自分自身の一部への参照を持つ構造体(自己参照構造体とここでは呼ぶことにします)を作ろうとして、コンパイルエラーに遭遇してしまうのはRust初心者にありがちなようです。ここでは、なぜ自己参照構造体を作ることができないのかという理由と、その解決法を改めてまとめてみます。

# 自己参照構造体

自己参照構造体の例として、整数値`a`とその参照`b`をフィールドとして持つ構造体`SelfRef`を考えてみます。

``` Rust
struct SelfRef<'a> {
    a: i32,
    b: &'a i32,
}

impl<'a> SelfRef<'a> {
    fn new() -> Self {
        let a = 42i32;
    
        SelfRef {
            a,
            b: &a,
        }
    }
}
```

これをコンパイルすると、次のようなエラーが返ってきます。

```
error[E0515]: cannot return value referencing local variable `a`
  --> src/main.rs:11:9
   |
11 | /         SelfRef {
12 | |             a,
13 | |             b: &a,
   | |                -- `a` is borrowed here
14 | |         }
   | |_________^ returns a value referencing data owned by the current function
```

ローカル変数への参照を返すな、と怒られてしまいます。そこで、`b`の参照の作り方を変え、直接構造体`SelfRef`の中の`a`を指すように変えてみます。

``` Rust
struct SelfRef<'a> {
    a: i32,
    b: Option<&'a i32>,
}

impl<'a> SelfRef<'a> {
    fn new() -> Self {
        let mut s = SelfRef {
            a: 42,
            b: None,
        };
        s.b = Some(&s.a);
        s
    }
}
```

これでもコンパイルは通りません。その他どういじってもライフタイム関連のエラーが出てくるでしょう。そして、どうやらこのような構造体`SelfRef`を作成することはできないものと気付きます。

# 作れない理由

先程の`new`メソッドは、`SelfRef`を生成した後にその値を返そうとしていました。これは、一度`new`メソッドのスタック領域に`SelfRef`を生成し、それを別のメモリ領域にムーブすることになります。ところが、参照`b`の実態は変数`a`を指すポインタであり、ムーブが行われると`a`が置かれるメモリアドレスは変化してしまいます。これにより`new`メソッドが終了すると参照`b`は無効となってしまいます。これが自己参照構造体が作れない基本的な理由です。

ちなみに、この`SelfRef`をC言語で書くとしたら、次のようになるでしょう。

``` C
typedef struct SelfRef {
    int a;
    int *b;
} SelfDef;

SelfDef selfref_new() {
    SelfDef s;
    s.a = 42;
    s.b = &s.a;
    return s;
}
```

このコードはコンパイルは通りますが、`selfref_new`関数が終了した後には、`s.b`は意味のある場所を指していないことがわかります。自己参照構造体が作れない理由は、Rustのライフタイムの制限という以前に、メモリとポインタの仕組みそのものにあると言えます。

# ヒープ領域の場合

もし、ムーブが起きても参照先が変わらない場合はどうでしょうか。これは参照先がヒープ領域にある場合に該当し、先程の`SelfRef`は次のようになります。

``` Rust
struct SelfRef<'a> {
    a: Box<i32>,
    b: &'a i32,
}
```

`a`の実体はヒープ領域にあるので、`b`が`a`を指している場合にムーブが起きても、参照が壊れることはなさそうです。しかしながら、このような自己参照構造体も作ることができません。もし作れたとして、この`SelfRef`へのmutableな参照が存在した場合、`b`の参照が生きているにも関わらず`a`を直接書き換えることが出来てしまいます。これは「ある変数へのmutableな参照をもつ場合、それが唯一の参照である」というRustのルールを破りますし、また`a`に別の`Box`を代入することで、`b`が無効な参照になってしまいます。

# ライフタイムを持つオブジェクト

プログラマが明示的に参照を用いなくても、以上の制限に引っかかることがあります。それはオブジェクトがライフタイムを持っている場合です。例えば、次のような構造体`Parent`と`Child`を考えます。

``` Rust
struct Parent {
    i: i32,
}

struct Child<'a> {
    parent: &'a Parent,
}

impl<'a> Child<'a> {
    fn new(parent: &'a Parent) -> Self {
        Child {
            parent
        }
    }
}
```

この`Child`は`Parent`のライフタイム内でしか存在できません。この2つをフィールドとする構造体を作ろうとすると、次のようになるでしょう。

``` Rust
struct SelfRef<'a> {
    parent: Parent,
    child: Child<'a>,
}

impl<'a> SelfRef<'a> {
    fn new() -> Self {
        let parent = Parent { i: 42 };
        let child = Child::new(&parent);

        SelfRef {
            parent,
            child,
        }
    }
}
```

このコードは、先程の例と同様に`SelfRef::new`がコンパイルエラーとなってしまいます。Rustではこのようなライフタイムを持つオブジェクトがよく現れるので、それらを使おうとしたときに頭を悩ませることになります。

# 解決法

自己参照構造体が作れない問題については、諦めてRust本来の方法であるスコープを基にしたライフタイム管理を使うようにするのが手っ取り早い方法です。しかしながら、自己参照構造体が使えると、効率的なデータ構造を定義できたり、複数のオブジェクトをまとめて簡潔な設計にできたりする場合もあります。このようにどうしても自己参照構造体が欲しい場合の解決法を取り上げます。

## unsafeを許容してポインタを使う

ポインタを使えば、上記の制限を全て無視して好きなように自己参照構造体を作ることが出来ます。もちろんポインタを使えば安全でないコードが容易に書けてしまうので、そこはプログラマの責任となります。必要なときは仕方ありませんが、あまり普段から常用したい方法ではないでしょう。

## ~~rentalクレートを使う~~

~~先述の通り、参照先がヒープ領域にあれば、自己参照構造体をムーブしても安全なはずです。そこで、そのような構造体を定義するためのツールを提供するためのクレートである[rental](https://crates.io/crates/rental)が存在します。~~

**※ 2022/1/29 追記
rentalクレートはメンテナンスされなくなったので、代替として[ouroboros](https://crates.io/crates/ouroboros)の使用を推奨します。**

rentalを使うと、先程の`Parent`と`Child`をまとめた構造体`MyRental`を次のように作ることが出来ます。

``` Rust
#[macro_use]
extern crate rental;

pub struct Parent {
    i: i32,
}

pub struct Child<'a> {
    parent: &'a Parent,
}

impl<'a> Child<'a> {
    fn new(parent: &'a Parent) -> Self {
        Child {
            parent
        }
    }
}

// マクロを使ってMyRentalを定義する
rental! {
    mod my_rentals {
        use super::*;

        #[rental]
        pub struct MyRental {
            parent: Box<Parent>,
            child: Child<'parent>,
        }
    }
}

// MyRentalを返す関数も記述できる
fn func() -> my_rentals::MyRental {
	// ParentをBoxの中に作る
    let f = Box::new(Parent { i: 42 });
	// クロージャ内でParentからChildを生成する
    my_rentals::MyRental::new(f, |parent: &Parent| {
        Child::new(parent)
    })

}

fn main() {
	// MyRentalは普通にムーブ可能
    let r = func();
	
	// フィールドにはクロージャを介してアクセスする
    r.rent_all(|rent| {
        let child: &Child = &rent.child;
        assert_eq!(child.parent.i, 42);
    });
}
```

rentalクレートでは、フィールド同士にあるライフタイムの関係を安全に取り扱うことができます。フィールドのアクセスにクロージャを介してやる必要があるなど制限はありますが、とりあえず自己参照構造体を作ることはできます。

似たようなものとして、`Box`や`Vec`といったヒープ領域への所有権と、その中身への参照をまとめるための[owning_ref](https://crates.io/crates/owning_ref)というクレートもあります。

# 参考
[StackOverflow - Why can't I store a value and a reference to that value in the same struct?](https://stackoverflow.com/questions/32300132/why-cant-i-store-a-value-and-a-reference-to-that-value-in-the-same-struct)