Chapter 3: 高度な所有権パターン

学習目標

  • 内部可変性パターンを習得する
  • RcとArcの使い分けを理解する
  • RefCellとMutexのトレードオフを学ぶ
  • スマートポインタの設計パターンを理解する
  • グラフ構造などの複雑なデータ構造の実装方法を学ぶ

---

3.1 内部可変性（Interior Mutability）

3.1.1 外部可変性 vs 内部可変性

// 外部可変性（通常のパターン）
let mut x = 5;
x = 6;  // OK: xがmut

let y = 5;
// y = 6;  // エラー: yはimmutable

// 内部可変性
use std::cell::Cell;
let x = Cell::new(5);
x.set(6);  // OK: xはimmutableだが内部を変更できる

概念図：

外部可変性:
mut ────► 値
│
└─► 外側からの変更

内部可変性:
────────► Cell<T>/RefCell<T> ────► 値
immutable      │
               └─► 内側での変更

---

3.2 Cell と RefCell

3.2.1 Cell

use std::cell::Cell;

struct Counter {
    count: Cell<usize>,
}

impl Counter {
    fn new() -> Self {
        Counter {
            count: Cell::new(0),
        }
    }

    fn increment(&self) {  // &self（immutable）
        let current = self.count.get();
        self.count.set(current + 1);
    }

    fn get(&self) -> usize {
        self.count.get()
    }
}

fn main() {
    let counter = Counter::new();  // mutなし
    counter.increment();
    counter.increment();
    println!("{}", counter.get());  // 2
}

制限：

  • T: Copy が必要
  • 参照を取得できない

3.2.2 RefCell

use std::cell::RefCell;

struct Node {
    value: i32,
    children: RefCell<Vec<Node>>,
}

impl Node {
    fn add_child(&self, child: Node) {
        self.children.borrow_mut().push(child);
        //            ^^^^^^^^^^^
        //            実行時に借用チェック
    }
}

動的借用チェック：

use std::cell::RefCell;

let data = RefCell::new(5);

{
    let r1 = data.borrow();  // OK: 不変借用
    let r2 = data.borrow();  // OK: 複数の不変借用
    // let r3 = data.borrow_mut();  // panic! 不変借用中
}

{
    let mut r = data.borrow_mut();  // OK: 可変借用
    *r += 1;
    // let r2 = data.borrow();  // panic! 可変借用中
}

---

3.3 参照カウント

3.3.1 Rc（シングルスレッド）

use std::rc::Rc;

struct Node {
    value: i32,
    next: Option<Rc<Node>>,
}

fn main() {
    let a = Rc::new(Node {
        value: 5,
        next: None,
    });
    println!("count = {}", Rc::strong_count(&a));  // 1

    let b = Rc::new(Node {
        value: 10,
        next: Some(Rc::clone(&a)),
    });
    println!("count = {}", Rc::strong_count(&a));  // 2

    let c = Rc::new(Node {
        value: 15,
        next: Some(Rc::clone(&a)),
    });
    println!("count = {}", Rc::strong_count(&a));  // 3
}

メモリレイアウト：

Rc<T>:
┌───────────────────────────────┐
│  RcBox<T>                     │
│  ├─ strong_count: usize       │
│  ├─ weak_count: usize         │
│  └─ value: T                  │
└───────────────────────────────┘
        ▲
        │ (複数の Rc ポインタ)

3.3.2 Arc（マルチスレッド）

use std::sync::Arc;
use std::thread;

fn main() {
    let data = Arc::new(vec![1, 2, 3]);

    let mut handles = vec![];

    for _ in 0..3 {
        let data = Arc::clone(&data);
        let handle = thread::spawn(move || {
            println!("{:?}", data);
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }
}

Rc vs Arc：

┌─────────────────────────────────────────────────────────┐
│         Rc<T> vs Arc<T>                                 │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  Rc<T>:                       Arc<T>:                   │
│  ────────                     ─────────                │
│  シングルスレッド              マルチスレッド           │
│  参照カウント（非アトミック）  参照カウント（アトミック）│
│  高速                         若干遅い                  │
│  !Send, !Sync                 Send, Sync               │
│                                                         │
└─────────────────────────────────────────────────────────┘

---

3.4 複合パターン

3.4.1 Rc>

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

#[derive(Debug)]
struct Node {
    value: i32,
    children: Vec<Rc<RefCell<Node>>>,
    parent: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(value: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            value,
            children: vec![],
            parent: None,
        }))
    }

    fn add_child(parent: &Rc<RefCell<Node>>, child: &Rc<RefCell<Node>>) {
        child.borrow_mut().parent = Some(Rc::clone(parent));
        parent.borrow_mut().children.push(Rc::clone(child));
    }
}

fn main() {
    let root = Node::new(1);
    let child1 = Node::new(2);
    let child2 = Node::new(3);

    Node::add_child(&root, &child1);
    Node::add_child(&root, &child2);

    println!("root children: {}", root.borrow().children.len());
}

3.4.2 Arc>

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    let counter = Arc::new(Mutex::new(0));
    let mut handles = vec![];

    for _ in 0..10 {
        let counter = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            let mut num = counter.lock().unwrap();
            *num += 1;
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Result: {}", *counter.lock().unwrap());
}

---

3.5 弱参照（Weak References）

3.5.1 循環参照の問題

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

struct Node {
    next: Option<Rc<RefCell<Node>>>,
}

fn main() {
    let a = Rc::new(RefCell::new(Node { next: None }));
    let b = Rc::new(RefCell::new(Node { next: Some(Rc::clone(&a)) }));
    a.borrow_mut().next = Some(Rc::clone(&b));

    // 循環参照！メモリリーク
    // a → b → a → b → ...
}

3.5.2 Weakで解決

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

struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

impl Node {
    fn new(value: i32) -> Rc<Self> {
        Rc::new(Node {
            value,
            parent: RefCell::new(Weak::new()),
            children: RefCell::new(vec![]),
        })
    }
}

fn main() {
    let leaf = Node::new(3);
    let branch = Node::new(5);

    branch.children.borrow_mut().push(Rc::clone(&leaf));
    *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

    // leafの親を取得
    match leaf.parent.borrow().upgrade() {
        Some(parent) => println!("leaf's parent: {}", parent.value),
        None => println!("leaf has no parent"),
    }
}

---

3.6 グラフ構造の実装

3.6.1 有向グラフ

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

type NodeRef = Rc<RefCell<Node>>;

struct Node {
    id: usize,
    neighbors: Vec<NodeRef>,
}

struct Graph {
    nodes: Vec<NodeRef>,
}

impl Graph {
    fn new() -> Self {
        Graph { nodes: vec![] }
    }

    fn add_node(&mut self, id: usize) -> NodeRef {
        let node = Rc::new(RefCell::new(Node {
            id,
            neighbors: vec![],
        }));
        self.nodes.push(Rc::clone(&node));
        node
    }

    fn add_edge(&mut self, from: &NodeRef, to: &NodeRef) {
        from.borrow_mut().neighbors.push(Rc::clone(to));
    }
}

3.6.2 アリーナアロケータ

struct Arena<T> {
    items: Vec<T>,
}

struct NodeId(usize);

struct Node {
    value: i32,
    children: Vec<NodeId>,
}

impl Arena<Node> {
    fn new() -> Self {
        Arena { items: vec![] }
    }

    fn alloc(&mut self, node: Node) -> NodeId {
        let id = self.items.len();
        self.items.push(node);
        NodeId(id)
    }

    fn get(&self, id: NodeId) -> Option<&Node> {
        self.items.get(id.0)
    }

    fn get_mut(&mut self, id: NodeId) -> Option<&mut Node> {
        self.items.get_mut(id.0)
    }
}

---

3.7 スマートポインタの設計

3.7.1 カスタムスマートポインタ

use std::ops::Deref;

struct MyBox<T>(T);

impl<T> MyBox<T> {
    fn new(x: T) -> MyBox<T> {
        MyBox(x)
    }
}

impl<T> Deref for MyBox<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

fn main() {
    let x = 5;
    let y = MyBox::new(x);

    assert_eq!(5, x);
    assert_eq!(5, *y);  // Derefで実現
}

3.7.2 Drop トレイト

struct CustomSmartPointer {
    data: String,
}

impl Drop for CustomSmartPointer {
    fn drop(&mut self) {
        println!("Dropping: {}", self.data);
    }
}

fn main() {
    let _c = CustomSmartPointer {
        data: String::from("my stuff"),
    };
    let _d = CustomSmartPointer {
        data: String::from("other stuff"),
    };
    println!("Created");
}
// 出力:
// Created
// Dropping: other stuff
// Dropping: my stuff

---

3.8 まとめ

3.8.1 パターンの選択ガイド

シングルスレッド:
├─ 共有所有権が必要
│  └─ Rc<T>
├─ 内部可変性が必要
│  ├─ T: Copy
│  │  └─ Cell<T>
│  └─ T: !Copy
│     └─ RefCell<T>
└─ 両方必要
   └─ Rc<RefCell<T>>

マルチスレッド:
├─ 共有所有権が必要
│  └─ Arc<T>
├─ 内部可変性が必要
│  └─ Mutex<T> or RwLock<T>
└─ 両方必要
   └─ Arc<Mutex<T>>

---

練習問題

問題1

双方向リンクリストを Rc> を使って実装しなさい。

問題2

スレッドセーフな共有カウンタを Arc> を使って実装しなさい。

---

次の章へ

Chapter 4: 上級者向けテクニックへ →

Previous
演習: 借用チェッカー
Next
解説: ライフタイム基礎