Rust の Rc<T> をディープコピーする方法

こんにちは。Rust には参照カウント方式で複数の所有権を持たせるスマートポインタの Rc ("R"eference "C"ount) があります。
doc.rust-lang.org
こいつのディープコピー、すなわち参照カウントが1で参照先が clone された状態のものを作りたい状況があったのですが、やりかたを調べるのに意外と時間がかかったのでメモとして残しておきます。

まず Rust だと「clone は何もせずとも deep copy」という雰囲気をまとっているので *1、何も考えず書くと以下のようになると思います。がこれは assertion error になります。

use std::rc::Rc;

#[derive(Debug, Clone)]
struct Foo {}

fn main() {
    let rcfoo = Rc::new(Foo{});
    let rcfoo2 = rcfoo.clone(); // 実は shallow copy
    assert_eq!(1, Rc::strong_count(&rcfoo)); // assertion error!
    println!("{:?}", rcfoo2);
}

理由は、Rc における clone は「参照カウントをインクリメントして新しい所有権を作る」という操作に割り当てられているからです。まさに shallow copy です。中身を clone して参照カウント1のものを作るには、文字通り、中身への参照を as_ref() でもらった上でそれを clone して、さらに Rc::new してやれば実現できます。

use std::rc::Rc;

#[derive(Debug, Clone)]
struct Foo {}

fn main() {
    let rcfoo = Rc::new(Foo{});
    let rcfoo2 = Rc::new(rcfoo.as_ref().clone()); // deep copy
    assert_eq!(1, Rc::strong_count(&rcfoo)); // ok
    println!("{:?}", rcfoo2);
}

これでめでたしめでたし…でも良かったんですが、Rc の中に入っている struct のフィールドにまた Rc に包まった値が入っているケースでは、やはりそのフィールドについては shallow copy になってしまいます。これは clone() の仕様として、各フィールドに対して再帰的に clone() するように実装されていることが原因です。

use std::rc::Rc;

#[derive(Debug, Clone)]
struct Foo {rcbaa: Rc<Baa>}

impl Foo {
    fn new() -> Self {
        Foo { rcbaa: Rc::new(Baa{}) }
    }
}

#[derive(Debug, Clone)]
struct Baa {}

fn main() {
    let rcfoo = Rc::new(Foo::new());
    let rcfoo2 = Rc::new(rcfoo.as_ref().clone()); // deep copy...?
    assert_eq!(1, Rc::strong_count(&rcfoo)); // ok
    assert_eq!(1, Rc::strong_count(&rcfoo.rcbaa)); // assestion error!
    println!("{:?}", rcfoo2);
}

解決方法はほぼ同じで、フィールドに対しても Rc::new(as_ref().clone()) を行うようにすれば ok です。
以下はこれを自前の trait DeepClone を作って実装する形で実現してみた例です。

use std::rc::Rc;

trait DeepClone {
    fn deep_clone(&self) -> Self;
}

impl<T> DeepClone for Rc<T>
where
    T: DeepClone,
{
    fn deep_clone(&self) -> Self {
        Rc::new(self.as_ref().deep_clone())
    }
}

#[derive(Debug, Clone)]
struct Foo {rcbaa: Rc<Baa>}

impl Foo {
    fn new() -> Self {
        Foo { rcbaa: Rc::new(Baa{}) }
    }
}

impl DeepClone for Foo {
    fn deep_clone(&self) -> Self {
        Foo { rcbaa: self.rcbaa.deep_clone() }
    }
}

#[derive(Debug, Clone)]
struct Baa {}

impl DeepClone for Baa {
    fn deep_clone(&self) -> Self {
        self.clone()
    }
}

fn main() {
    let rcfoo = Rc::new(Foo::new());
    let rcfoo2 = rcfoo.deep_clone(); // deep copy!
    assert_eq!(1, Rc::strong_count(&rcfoo)); // ok
    assert_eq!(1, Rc::strong_count(&rcfoo.rcbaa)); // ok
    println!("{:?}", rcfoo2);
}

最後にグラフを扱うときに出てくるような、再帰的な型で実装してみた例を書いておきます。

use std::rc::Rc;

trait DeepClone {
    fn deep_clone(&self) -> Self;
}

impl<T> DeepClone for Rc<T>
where
    T: DeepClone,
{
    fn deep_clone(&self) -> Self {
        Rc::new(self.as_ref().deep_clone())
    }
}

#[derive(Debug, Clone)]
enum Foo {
    Nil,
    Con(Rc<Foo>)
}

impl DeepClone for Foo {
    fn deep_clone(&self) -> Self {
        use Foo::*;
        match self {
            Nil => Nil,
            Con(rcfoo) => {
                Con(rcfoo.deep_clone())
            }
        }
    }
}

fn main() {
    let foo = Foo::Con(Rc::new(Foo::Nil));
    let rcfoo = Rc::new(foo);
    let rcfoo2 = rcfoo.deep_clone(); // deep copy!
    assert_eq!(1, Rc::strong_count(&rcfoo)); // ok
    if let Foo::Con(rcfoo_) = rcfoo.as_ref() {
        assert_eq!(1, Rc::strong_count(rcfoo_)); // ok
    }
    println!("{:?}", rcfoo2);
}

実は上記の書き方では、ループのあるグラフの場合には無限ループになるので、そのうち stackoverflow を起こして死にます。しかしまともにループのあるグラフを実装している場合は弱参照を適切に使うはずなので*2、たぶん std::rc::Weak にも DeepClone を実装しておいてあげれば解決するのかな？と想像します。がそろそろ疲れたので、今回はこのへんで終わりにします。ではまた。

*1:参考: https://qiita.com/namn1125/items/2d84086394e97489776a

*2:参照カウント方式で何も考えず循環参照をつくると、互いに参照カウント1つ分を持ってしまうので、メモリ解放できなくなります。参考: https://doc.rust-jp.rs/book-ja/ch15-06-reference-cycles.html