強参照Rc<T> と弱参照Weak<T>

std::rc::Rc<T> 概要

動的な参照を実現。&演算子による参照がコンパイル時にされるのに対して、Rc<T>は実行時に参照を確保する。 これによってライフタイムを除去することができる。

ライフタイムの除去

参照による共有

借用チェッカーを通すために、ライフタイムを付与する必要がある

struct A<'a> {
    data: &'a [u8],
}
impl<'a> A<'a> {
    fn new(data: &[u8]) -> A {
        A {
            data: data,
        }
    }
}

// 1k bytes
let big_data = (0..1000).collect::<Vec<u8>>();
let a1 = A::new(&big_data); // ビッグデータの共有1
let a2 = A::new(&big_data); // ビッグデータの共有2

Rc<T>による共有

// ライフタイムの除去
struct B {
    data: Rc<Vec<u8>>,
}
impl B {
    fn new(data: Rc<Vec<u8>>) -> B {
        B {
            data: data,
        }
    }
}

// Rcに包む
let shared_data = Rc::new(big_data);
let b1 = B::new(shared_data);
let b2 = B::new(Rc::clone(&shared_data));
  • Rc::clone(&b1) or b1.clone() によって参照の共有を作っていく

強参照(std::rc::Rc<T>)と弱参照(std::rc::Weak<T>)

Rc::cloneを使用すると、強参照(Rc<T>)を生成するため、互いに参照し合うと、メモリーリークを発生させる。 この場合は、Rc::downgradeを使用することで、弱参照(Weak<T>)を生成する。

let p = Parent::new();
let p = Rc::new(p);

// 弱参照でparentと結ぶ
let c1 = Child::new(Rc::downgrade(&p), 1);
let c2 = Child::new(Rc::downgrade(&p), 2);
let c3 = Child::new(Rc::downgrade(&p), 3);

println!("{}", Rc::strong_count(&p)); // 1

// 強参照でchildを渡す
p.add_child(Rc::new(c1));
p.add_child(Rc::new(c2));
p.add_child(Rc::new(c3));

std::rc::Rc<T> と std::cell::RefCell<T>

Rc::borrow_mut の問題

let file = File::open("text.txt")?;
let mut bufreader = BufReader::new(&file);
let shared_reader = Rc::new(bufreader);

// NG
let _ = *shared_reader.borrow_mut().read_line(&mut line)?;

/*
error[E0599]: no method named `borrow_mut` found for struct `Rc<BufReader<&File>>` in the current scope
15  |     let _ = *shared_reader.borrow_mut().read_line(&mut line)?;
    |                            ^^^^^^^^^^ method not found in `Rc<BufReader<&File>>`
*/

直接Rc<T>にイミュータブルなFileインスタンスを包んでしまうと、borrow_mutメソッドが使用できない。

RefCell に包む

let refcell = RefCell::new(bufreader);

let shared_reader = Rc::new(refcell);

// OK
let _ = (*shared_reader.borrow_mut()).read_line(&mut line)?;

循環参照 - Rc<T>とRefCell<T>

循環参照はメモリーをリークする

Rustのメモリ安全保障において、メモリーリークを発生させることはとてつもなく難しい。

Preventing memory leaks entirely is not one of Rust's guarantees in the same way that disallowing data race at compile time is, meaning memory leaks are memory safe in Rust.

完全なるメモリーリークの予防は、コンパイル時間にデータ競合を許さないことと同じでRustの保証の1つではない。 それは、メモリーリークはメモリー安全であることを意味する。

Rc<T>RefCell<T>を使えば、サイクルにおいて互いに参照する参照を作りだすことができ、互いの参照カウントが永遠に0にならないため、メモリーリークを発生させることができる。

循環参照の作成

ConsListの定義。

#[derive(Debug)]
enum List {
    // RefCell<T>にすることによってtailの変更ができる
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}

tailをRefCell<Rc<List>>にすることで、値の取替が行えるようにしている。

impl List {
    // tailの取り出し
    fn tail(&self) -> Option<&RefCell<Rc<List>>> {
        match self {
            Cons(_, item) => Some(item),
            Nil => None,
        }
    }
}

// tailの取り出し Option<&RefCell<Rc<List>>>
if let Some(link) = a.tail() {
    // RefCellの中身を変更
    *link.borrow_mut() = Rc::clone(&b);
}

循環参照の作成。

let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));
println!("a initial rc count = {}", Rc::strong_count(&a));              // 1 aの値は、aのみ参照
println!("a next item = {:?}", a.tail());                               

let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));
println!("a rc count after b creation = {}", Rc::strong_count(&a));     // 2 aの値は、aとbが参照
println!("b initial rc count = {}", Rc::strong_count(&b));              // 1 bの値は、bのみ参照
println!("b next item = {:?}", b.tail());

if let Some(link) = a.tail() {
    // aのお尻のNilをbに変更し、循環参照にする
    *link.borrow_mut() = Rc::clone(&b);
}

println!("b rc count after changing a = {}", Rc::strong_count(&b));     // 2 bの値は、aとbが参照
println!("a rc count after changing a = {}", Rc::strong_count(&a));     // 2 aの値は、aとbが参照

// 以下のコードを実行するとオーバーフローが発生する。
// println!("a next item = {:?}", a.tail());

循環参照の防止: RckらWeakに変更する

Rc::cloneを呼ぶことで、Rc<T>インスタンスstrong_countをインクリメントする。

子供配列を持つノード

f:id:yossan2:20210221170048p:plain

循環参照
f:id:yossan2:20210221170125p:plain

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Node {
    value: i32,
    children: RefCell<Vec<Rc<Node>>> // Nodeへの所有権を共有する
}

Nodeへの所有権を共有するために、Rc<Node>型の配列を持つようにする。 また他の子供である各ノードを変更できるように、Vec<Rc<Node>>を包むchildrenRefCell<T>で持つようにする。

fn main() {
    // 葉 (辺を持たない)
    let leaf = Rc::new(Node { value: 3, children: RefCell::new(vec![]) });
    // 節 (辺を持つ)
    let branch = Rc::new(Node { value: 5, children: RefCell::new(vec![Rc::clone(&leaf)]) });

leafの値は、2つのオーナーが存在する。(leafbranch)

branchからleafを取得することはできるが、leafからbranchは取得することができないので、parentをもたせるようにする。

子供からその親への参照を追加する

parentへの参照をRc<T>型でもってしまうと、循環参照が発生する。

親ノードは、子供ノードへの所有権を持つべきであるとすると、 もし親ノードがドロップしたならば、全ての子供ノードも同様にドロップするべきと考えられる。 しかしながら、1つの子供ノードがドロップしたとしても親ノードをドロップさせるべきではない。

つまりこれは弱参照を使うためのケースである。

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,  // RefCellを挟むことで変更できるようにする
    children: RefCell<Vec<Rc<Node>>>,
}

ノードは、親への参照をもつが所有を持たない。

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![]),
    });

    // Weak::upgradeは、Option<Rc<T>>を返す
    println!("leaf parent = {:?}", leaf.parent.borrow().upgrade());

    let branch = Rc::new(Node {
        value: 5,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![Rc::clone(&leaf)]),
    });

    // Rc::downgradeは、Weak<T>を返す
    *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

    println!("leaf parent = {:?}", leaf.parent.borrow().upgrade());
}

Rc::clonestrong_countの値をインクリメントし、Rc<T>インスタンスは、strong_countが0になるまでドロップされない。

そこで、Rc::downgradeを呼び、Rc<T>への参照を渡すことによって、Rc<T>インスタンスを内部に持つ値への弱参照を作ることも可能である。

Rc::downgrade関数を呼び出すと、Weak<T>インスタンス型のポインタを得ることができる。 strong_countの値をインクリメントする代わりに、Rc::downgradeは、weak_countをインクリメントする。

Rc<T>型はweak_countをトラックしつづけるが、strong_countとの違いは、0にならなくてもドロップすることができる。

強参照は、Rc<T>インスタンスの所有権を共有することができる方法である。 弱参照は、所有の関係を表すものではない。 これは循環参照を引き起こさない。なぜならば、弱参照を含んでいるいかなる循環は、強参照の値が0になったさいに破壊される。

Weak<T>インスタンスupgradeメソッドは、Option<Rc<T>>を返す。 もしRc<T>の値がドロップされていなければ、結果がSomeとなる。

leaf.parent.borrow()によって、RefCell<T>の値を借用し、Weak<Node>インスタンスを取得している。値がドロップしていなければ、upgradeメソッドで親ノードの取得が可能となる。

まとめ

  • Box<T>: ヒープ上に配置されたデータへのポインタとサイズの決定
  • Rc<T>: ヒープ上のデータへの参照カウンタによる複数所有者の実現
  • RefCell<T>: イミュータブルな型が必要であるが、その内部の値を変更する必要があるとき、またコンパイル時間ではなくランタイム時に借用ルールを強制するとき
  • Weak<T>: 循環参照を防止する

参照

doc.rust-lang.org

スマートポインタ Rc<T> - 参照カウンタ

Rc<T>, the Reference Counted Smart Pointer

所有権は多くの場合において明白である。つまり「1変数は、1つの値の所有する 」。

しかしながら 一つの値が複数の所有者を持つ ケースが存在する。 例として、グラフ構造がある。 グラフは、複数の辺が同一のノードを指し示しす。つまりノードは概念的にそれを指し示す全ての辺によって所有される。 またノードは、それを指し示す辺がある限り、削除されるべきではない。

Rustは、複数の所有権を可能にするために、Rc<T>型(参照カウンタ(reference counting)と称される)を持つ。

Rc<T>型は、値が使われているかどうかを決定するための値への参照の数 をトラックし続ける。 もし値への参照数が0になれば、その時、値は消去される。

Rc<T>を部屋に置かれたテレビとすれば、一人の人間がそのテレビをつけると、その他の人も部屋に入ってテレビを見ることができ、 最後の人間が離れると、もはや使用されていないので、テレビを消すことができる。 もし誰かが他の人が見ているのに、テレビを消した場合、大論争になるかもしれません。

とあるデータをプログラムのあちこちで読むためにヒープ上に配置したいとき、そしてどの箇所が最後に使用されるのか決定できないときに、Rc<T>型を使用します。

万が一、もし最後に使用する場所が分かっているならば、その場所をまさに所有者と決定することができるので、コンパイル時間に強制される通常の所有権ルールが効果を発揮するかもしれません。

Note:

Rc<T>型は1つのスレッド上のみで動作させる。マルチスレッドにおける参照カウントは、こちら

Rc<T> - データの共有

以下のcons listを考える。b,cからのノードは直接aを指し示すノードを参照している。

f:id:yossan2:20210221140524p:plain
Cons List

これをBox<T>型で書くと、所有権の問題が発生する。

enum List {
    Cons(i32, Box<List>),
    Nil,
}

fn main() {
    let a = Cons(5, Box::new(Cons(10, Box::new(Nil))));
    let b = Cons(3, Box::new(a)); // aの所有権が移動する
    let c = Cons(4, Box::new(a)); // エラーが発生する

もしくはこちらのようにaへの参照を直接持つようにすると、ライフタイムを明示する必要が発生する。

enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}


use crate::List::{Cons, Nil};
// リファレンスでは動かないとあるが、v1.50では動く
let a = Cons(5, &Cons(10, &Nil));
let b = Cons(3, &a);
let c = Cons(4, &a);

(v1.50以前では、借用チェッカーが、&Cons(10, &Nil)コンパイルさせることを許可しない。なぜならば変数aが一時的なNil値の参照を取る前にドロップさせてしまうため。)

その代わりに、Box<T>からRc<T>型に変更する。

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
use std::rc::Rc;

let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil))))); // a: Rc<List>
let b = Cons(3, Rc::clone(&a)); // Rc::cloneによって、aへの参照カントを増やす
let c = Cons(4, Rc::clone(&a)); // Rc::cloneによって、aへの参照カウントを増やす

Consは、値(i32)とListを指し示すRc<T>を持つ。

変数bを作るとき、aの所有権を取る代わりに、aをホールドするRc<List>をクローンし、aへの参照カウントを増やす。 毎回Rc::cloneを呼ぶごとに、Rc<List>を内部に含んでいるデータへの参照カウントは増加すし、その値が0になるまでは、データは消去されない。 Rc<T>を使うには、useステートメントを使ってスコープに追加する必要がある。プレリュード(前奏曲)にないため。

このケースに置いては、Rc::clone(&a)の代わりに、a.clone()を呼ぶことができるが、Rustの慣習では、Rc::cloneを使用する。

Rc::cloneは、ディープコピーを作るのではなく、参照カウントをインクリメントするのみである。

Rc::cloneによって、ディープコピーをするクローンと参照カウントを増加するクローンの違いを視覚的にすることができる。 これはコードのパフォーマンスの問題を探す際に、Rc::cloneを呼び出しを無視することができ、ディープコピークローンを考えるだけですむようになる。

Cloning an Rc<T> - 参照カウントのインクリメント

変数aのRc<List>への参照を作成・ドロップさせることで、参照カウントの変更を見ていく。

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
// a: Rc<List>
let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
println!("count after creating a = {}", Rc::strong_count(&a));
let b = Cons(3, Rc::clone(&a));
println!("count after creating b = {}", Rc::strong_count(&a));
{
    let c = Cons(4, Rc::clone(&a));
    println!("count after creating c = {}", Rc::strong_count(&a));
}
println!("count after c goes out of scope = {}", Rc::strong_count(&a));

/*
count after creating a = 1
count after creating b = 2
count after creating c = 3
count after c goes out of scope = 2
*/

Rc::strong_count関数を呼ぶことで、参照カウントを取得することができる。 この関数は、countではなく、strong_count命名されているのは、Rc<T>型は、weak_countという関数をも持つためである。 weak_countについては、こちらを参照。

イミュータブル参照を通して、Rc<T>は、複数のプログラムのあちこちの間で、データへの参照を許可する。 もしRc<T>が、ミュータブルな参照を許可することがあれば、借用ルールを破壊することになる。

同じデータへの複数のミュータブルな参照は、データ競合と矛盾を引き起こす。

しかし、可変データは非常に有用である。 次のセクションでは、内部の可変パターンとRefCell<T>について議論する。

RefCell<T>型は、この不可変な制限をもつRc<T>とともに使用することができる。

まとめ

Rc<T>によって

  • スマートポインタの一種
  • ヒープ上の値への参照を、参照ではなく値(Rc<T>型)として保持することができる
  • イミュータブルな参照を実現
  • 参照では必要となるライフタイムの明示を除去

関連と参照

doc.rust-lang.org

ジェネリクスとトレイトオブジェクトの破壊的変更への対処

動機 ジェネリクスとトレイトオブジェクトの抱える問題

壮大たる破壊的変更につながる。

例 Fileインスタンスを持つStreamをジェネリクスに変更する

struct Stream {
    reader: std::fs::File,
}
impl Stream {
    fn new(reader: std::fs::File) {
        Stream {
            reader: reader,
        }
    }
    fn read<'a>(&mut self, buf: &'a mut [u8]) {
        self.reader.read(buf).unwrap();
    }
}

readerフィールドは、Readトレイトを実装していれば良いので、ジェネリクスに変更する。

pub struct Stream<R> {
        reader: R,
}
impl<R: std::io::Read> Stream<R> {
    pub fn new(reader: R) -> Self {
        Stream {
            reader: reader,
        }
    }
    pub fn read<'a>(&mut self, buf: &'a mut [u8]) {
        self.reader.read(buf).unwrap();
    }
}

上記に変更すると、Streamインスタンスをフィールドに含む型もジェネリクス化する必要が生じる。

// XRef から XRef<R>へ
struct XRef<R> {
    stream: Stream<R>:
}

そうするとXRefインスタンスをフィールドに持つ型がある場合は、さらにその型をジェネリクス化する必要があり、壮大な破壊的変更となってしまう。

例 Fileインスタンスを持つStreamをトレイトオブジェクトに変更する

今度は、ライフタイムを付与する必要が発生し、破壊的変更は止まらない

以下ライフタイムを付与しなかった場合、エラーが発生する。

struct Stream {
    reader: Box<dyn std::io::Read>,
}
impl Stream {
    fn new<R: std::io::Read>(reader: R) -> Self {
        Stream {
            reader: Box::new(reader),
        }
    }
    fn read<'a>(&mut self, buf: &'a mut [u8]) {
        self.reader.read(buf).unwrap();
    }
}
/*
error[E0310]: the parameter type `R` may not live long enough
  |
5 |     fn new<R: std::io::Read>(reader: R) -> Self {
  |            -- help: consider adding an explicit lifetime bound...: `R: 'static +`
6 |         Stream {
7 |             reader: Box::new(reader),
  |                     ^^^^^^^^^^^^^^^^ ...so that the type `R` will meet its required lifetime bounds
*/

解決策として、'staticをつける手はあるが、'static以外のライフタイムを持つケースに置いて生成できなくなる。

// 'staticをつける
pub fn new<R>(reader: R) -> Self 
    where
        R: std::io::Read + 'static,
{
    Stream {
        reader: Box::new(reader),
    }
}

// NGとなる
fn make_stream_from_file<'a>(file: &'a std::fs::File) -> Stream {
    Stream::new(file)
}

解決策 トレイトオブジェクト + 具体型からの生成コンストラク

トレイトオブジェクトに変更した場合、コンストラクタのnewメソッドでジェネリクス型パラメーターを要求しているため、ライフタイムが必要となっている。 そこで具体型からのコンストラクタを用意することで、ライフタイムを削除することができる。

// Fileからの生成
pub fn new_from_file(reader: std::fs::File) -> Self {
    Stream {
        reader: Box::new(reader),
    }
}

// Vecからの生成
pub fn new_from_vec_u8(reader: vec<<u8>>) -> Self {
    Stream {
        reader: Box::new(reader),
    }
}

例 Stream

use std::io::{Cursor, Read, Seek};
use std::fs::File;

// 動的ディスパッチでは、複数のトレイトを付ける場合は、新たにトレイトを定義する必要がある
trait ReadSeek: Read + Seek {}
impl ReadSeek for File {}
impl ReadSeek for Cursor<Vec<u8>> {}

pub struct Stream {
    reader: Box<dyn ReadSeek>, // 動的ディスパッチ
}
impl Stream {
    // Fileからの生成
    pub fn new_from_file(reader: File) -> Self {
        Stream {
            reader: Box::new(reader),
        }
    }
    // Cursorからの生成
    pub fn new_from_cursor(reader: Cursor<Vec<u8>>) -> Self {
        Stream {
            reader: Box::new(reader),
        }
    }
    pub fn read<'a>(&mut self, buf: &'a mut [u8]) {
        self.reader.read(buf).unwrap();
    }
}

関数パラメーターにおける参照外し

関数パラメーターにおいても参照外しを行うことができる

例1 クロージャー map関数

let result = [1,2,3,4,5].iter().map(|&&x| x % 2 == 0).collect();
  • &&x : 参照参照外しをおこなっている

例2 関数の定義

参照外ししない場合

fn print_type_name<T>(_val: T) {
    println!("{}", std::any::type_name::<T>());
}

let vec = (0..5).collect::<Vec<i32>>();
for i in &vec {
    print_type_name(i);  // &i32
}

参照外しをした場合

fn print_type_name<T>(_val: &T) {
    println!("{}", std::any::type_name::<T>());
}

let vec = (0..5).collect::<Vec<i32>>();
for i in &vec {
    print_type_name(i);  // i32 
}

関連

yossan.hatenablog.com

doc.rust-lang.org