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

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

自己参照構造体

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

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を指すように変えてみます。

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言語で書くとしたら、次のようになるでしょう。

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は次のようになります。

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

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

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

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

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つをフィールドとする構造体を作ろうとすると、次のようになるでしょう。

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が存在します。

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

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

#[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というクレートもあります。

参考

StackOverflow - Why can't I store a value and a reference to that value in the same struct?