課題3: 実践的な所有権パターン

マンダトリー要件（80点）

問題1: Interior Mutability（内部可変性）（25点）

1.1 RefCellの理解と実装（15点）

以下の要件を満たすプログラムを実装しなさい：

use std::cell::RefCell;

// 変更履歴を記録するカウンター
struct TrackedCounter {
    value: RefCell<i32>,
    history: RefCell<Vec<i32>>,
}

impl TrackedCounter {
    fn new() -> Self {
        // ここを実装しなさい（3点）
    }

    fn increment(&self) {
        // valueを1増やし、historyに記録（5点）
        // RefCellのborrow_mutを使用
    }

    fn get_value(&self) -> i32 {
        // 現在の値を取得（2点）
        // RefCellのborrowを使用
    }

    fn get_history(&self) -> Vec<i32> {
        // 履歴のクローンを返す（2点）
    }

    fn reset(&self) {
        // valueを0にリセットし、historyをクリア（3点）
    }
}

評価ポイント：

• RefCellの正しい使用（borrow/borrow_mut）
• パニックの可能性を考慮
• 適切なエラーハンドリング

1.2 Cellの実装（10点）

以下のシナリオでCellを使用してください：

use std::cell::Cell;

// スレッド非対応のシンプルなカウンター
struct SimpleCounter {
    count: Cell<u32>,
}

impl SimpleCounter {
    fn new() -> Self {
        // ここを実装（2点）
    }

    fn increment(&self) {
        // Cellのget/setを使用して実装（4点）
    }

    fn get(&self) -> u32 {
        // 現在の値を取得（2点）
    }

    fn add(&self, n: u32) {
        // nを加算（2点）
    }
}

比較分析（追加課題）：

• CellとRefCellの違いを説明しなさい（どちらを使うべきか？）

---

問題2: 参照カウント（Rc/Arc）（25点）

2.1 Rcを使った循環参照のない木構造（15点）

親子関係を持つ木構造を実装しなさい：

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

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

impl TreeNode {
    fn new(value: i32) -> Rc<RefCell<Self>> {
        // ここを実装（3点）
    }

    fn add_child(parent: &Rc<RefCell<TreeNode>>, child: Rc<RefCell<TreeNode>>) {
        // 子ノードを追加（4点）
    }

    fn print_tree(node: &Rc<RefCell<TreeNode>>, depth: usize) {
        // 木構造を再帰的に表示（インデント付き）（5点）
        // 例：
        // 1
        //   2
        //     3
        //   4
    }

    fn count_nodes(node: &Rc<RefCell<TreeNode>>) -> usize {
        // ノードの総数を数える（3点）
    }
}

テストコード：

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

    TreeNode::add_child(&root, child1.clone());
    TreeNode::add_child(&root, child2);
    TreeNode::add_child(&child1, TreeNode::new(4));

    TreeNode::print_tree(&root, 0);
    println!("Total nodes: {}", TreeNode::count_nodes(&root));
}

2.2 Arcを使ったスレッドセーフなカウンター（10点）

複数スレッドから安全にアクセスできるカウンターを実装しなさい：

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

struct SharedCounter {
    count: Arc<Mutex<i32>>,
}

impl SharedCounter {
    fn new() -> Self {
        // ここを実装（2点）
    }

    fn increment(&self) {
        // スレッドセーフに1増やす（3点）
    }

    fn get(&self) -> i32 {
        // スレッドセーフに値を取得（2点）
    }

    fn spawn_incrementers(&self, n: usize) {
        // n個のスレッドを生成し、それぞれでincrementを呼ぶ（3点）
        // 全スレッドの終了を待つ
    }
}

fn main() {
    let counter = SharedCounter::new();
    counter.spawn_incrementers(10);
    println!("Final count: {}", counter.get());  // 期待値: 10
}

---

問題3: Weak参照による循環参照の回避（20点）

3.1 双方向リンクリスト（10点）

WeakとRcを使って循環参照を防ぐ双方向リンクリストを実装しなさい：

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
    prev: Option<Weak<RefCell<Node>>>,  // Weakで循環参照を防ぐ
}

impl Node {
    fn new(value: i32) -> Rc<RefCell<Self>> {
        // ここを実装（2点）
    }

    fn append(head: &Rc<RefCell<Node>>, value: i32) -> Rc<RefCell<Node>> {
        // リストの末尾に新しいノードを追加（5点）
        // prev/nextを正しく設定
    }

    fn print_forward(head: &Rc<RefCell<Node>>) {
        // 前方向に走査して表示（2点）
    }

    fn print_backward(tail: &Rc<RefCell<Node>>) {
        // 後方向に走査して表示（1点）
    }
}

3.2 メモリリークの検出（10点）

以下のコードにメモリリークがあるかどうか判定し、修正しなさい：

コード1：

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

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

fn create_cycle() {
    let a = Rc::new(RefCell::new(Node { next: None }));
    let b = Rc::new(RefCell::new(Node { next: None }));

    a.borrow_mut().next = Some(b.clone());
    b.borrow_mut().next = Some(a.clone());
}

• このコードにメモリリークはあるか？（2点）
• なぜメモリリークが発生するか説明しなさい。（3点）
• Weakを使って修正しなさい。（5点）

コード2：

use std::sync::Arc;

struct Data {
    items: Vec<Arc<Data>>,
}

fn create_self_reference() {
    let data = Arc::new(Data { items: vec![] });
    // この実装は不完全（コンパイルエラー）
    // メモリリークが起きないように完成させなさい
}

---

問題4: パターンの選択（10点）

以下の各シナリオに対して、最適な所有権パターンを選択し、理由を説明しなさい：

4.1 シナリオ分析（10点）

各シナリオについて、以下の表を埋めなさい：

シナリオ1: 単一スレッドで、読み取り専用のデータを複数箇所で共有

• 推奨パターン: ?
• 理由: ?
• 代替案: ?

シナリオ2: 単一スレッドで、データを複数箇所で読み書き

• 推奨パターン: ?
• 理由: ?
• 代替案: ?

シナリオ3: 複数スレッドで、読み取り専用のデータを共有

• 推奨パターン: ?
• 理由: ?
• 代替案: ?

シナリオ4: 複数スレッドで、データを読み書き

• 推奨パターン: ?
• 理由: ?
• 代替案: ?

シナリオ5: 循環参照が必要な構造（グラフ、双方向リスト）

• 推奨パターン: ?
• 理由: ?
• 代替案: ?

各シナリオ2点、計10点

---

ボーナス課題（20点）

ボーナス1: OnceCell/LazyLockの実装（10点）

標準ライブラリのOnceCellに似た型を実装しなさい：

use std::cell::UnsafeCell;
use std::mem::MaybeUninit;

pub struct SimpleOnceCell<T> {
    inner: UnsafeCell<MaybeUninit<T>>,
    initialized: Cell<bool>,
}

impl<T> SimpleOnceCell<T> {
    pub const fn new() -> Self {
        // const関数として実装（2点）
    }

    pub fn get(&self) -> Option<&T> {
        // 初期化済みなら値を返す（2点）
    }

    pub fn set(&self, value: T) -> Result<(), T> {
        // 未初期化なら値をセット（3点）
        // 既に初期化済みならエラー
    }

    pub fn get_or_init<F>(&self, f: F) -> &T
    where
        F: FnOnce() -> T,
    {
        // 未初期化なら初期化、初期化済みなら値を返す（3点）
    }
}

// Dropの実装も必要
impl<T> Drop for SimpleOnceCell<T> {
    fn drop(&mut self) {
        // 適切にドロップ
    }
}

要件：

• スレッド非対応でOK
• unsafeブロックの使用が必要
• 全ての操作の安全性を保証

---

ボーナス2: グラフ構造の実装（10点）

有向グラフをRcとRefCellを使って実装しなさい：

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

type NodeId = usize;

#[derive(Debug)]
struct GraphNode {
    id: NodeId,
    value: String,
    edges: Vec<NodeId>,  // 隣接ノードのID
}

struct Graph {
    nodes: HashMap<NodeId, Rc<RefCell<GraphNode>>>,
    next_id: NodeId,
}

impl Graph {
    fn new() -> Self {
        // ここを実装
    }

    fn add_node(&mut self, value: String) -> NodeId {
        // ノードを追加し、IDを返す
    }

    fn add_edge(&mut self, from: NodeId, to: NodeId) -> Result<(), String> {
        // エッジを追加
        // ノードが存在しない場合はエラー
    }

    fn get_neighbors(&self, id: NodeId) -> Vec<String> {
        // 隣接ノードの値のリストを返す
    }

    fn dfs(&self, start: NodeId) -> Vec<NodeId> {
        // 深さ優先探索で訪問したノードのIDを返す
    }

    fn has_cycle(&self) -> bool {
        // グラフに閉路があるかチェック
    }
}

要件：

• 完全な実装
• DFS（深さ優先探索）
• 閉路検出アルゴリズム
• テストコードも提出

---

ボーナス3: パフォーマンス比較（10点）

以下のパターンのパフォーマンスを測定し、レポートを作成しなさい：

// パターン1: Box<T>
fn pattern1() {
    let data = Box::new([0u8; 1024]);
    // ベンチマーク
}

// パターン2: Rc<T>
fn pattern2() {
    let data = Rc::new([0u8; 1024]);
    let clone1 = data.clone();
    let clone2 = data.clone();
    // ベンチマーク
}

// パターン3: Arc<T>
fn pattern3() {
    let data = Arc::new([0u8; 1024]);
    let clone1 = data.clone();
    let clone2 = data.clone();
    // ベンチマーク
}

// パターン4: Rc<RefCell<T>>
fn pattern4() {
    let data = Rc::new(RefCell::new([0u8; 1024]));
    let clone1 = data.clone();
    data.borrow_mut()[0] = 1;
    // ベンチマーク
}

// パターン5: Arc<Mutex<T>>
fn pattern5() {
    let data = Arc::new(Mutex::new([0u8; 1024]));
    let clone1 = data.clone();
    data.lock().unwrap()[0] = 1;
    // ベンチマーク
}

要件：

• Criterionクレートを使用してベンチマーク
• 各パターンの測定結果をグラフ化
• メモリ使用量の分析
• ユースケースごとの推奨パターンをまとめる
• レポートをMarkdown形式で提出（3000文字以上）

測定項目：

• アロケーション時間
• クローン時間
• アクセス時間（読み取り/書き込み）
• メモリフットプリント

---

評価基準

マンダトリー部分（80点）

項目	配点	評価ポイント
問題1：Interior Mutability	25点	RefCell/Cellの正確な使用
問題2：Rc/Arc	25点	参照カウントの理解
問題3：Weak参照	20点	循環参照の回避
問題4：パターン選択	10点	適切な判断力

ボーナス部分（20点）

項目	配点	評価ポイント
ボーナス1：OnceCell実装	10点	unsafeの正確な使用
ボーナス2：グラフ構造	10点	複雑なデータ構造の実装
ボーナス3：パフォーマンス比較	10点	実験の正確性と考察

注: ボーナスは最大20点まで加算されます。

---

提出方法

ファイル構成

rust-ownership-deep-dive-03/
├── mandatory/
│   ├── src/
│   │   ├── interior_mutability.rs
│   │   ├── rc_arc.rs
│   │   ├── weak_reference.rs
│   │   └── pattern_selection.md
│   ├── Cargo.toml
│   └── tests/
│       └── integration_tests.rs
├── bonus1-oncecell/
│   ├── src/lib.rs
│   └── tests/
├── bonus2-graph/
│   ├── src/lib.rs
│   └── tests/
└── bonus3-benchmark/
    ├── benches/
    │   └── comparison.rs
    ├── results/
    │   └── analysis.md
    └── Cargo.toml

提出期限

• マンダトリー：第3章学習後、1週間以内
• ボーナス：第4章修了時まで

---

ヒント

問題1のヒント（Interior Mutability）

RefCellの基本：

use std::cell::RefCell;

let data = RefCell::new(5);

// 不変参照を取得
let borrowed = data.borrow();
println!("{}", *borrowed);
// borrowedのスコープが終わるまで借用が続く

// 可変参照を取得
let mut borrowed_mut = data.borrow_mut();
*borrowed_mut += 1;
// borrowed_mutのスコープが終わるまで借用が続く

パニックに注意：

let data = RefCell::new(5);
let _borrow1 = data.borrow();
// let _borrow2 = data.borrow_mut();  // パニック！

問題2のヒント（Rc/Arc）

Rcの基本：

use std::rc::Rc;

let data = Rc::new(vec![1, 2, 3]);
println!("count: {}", Rc::strong_count(&data));  // 1

let clone1 = data.clone();
println!("count: {}", Rc::strong_count(&data));  // 2

let clone2 = data.clone();
println!("count: {}", Rc::strong_count(&data));  // 3

Arcの基本：

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

let data = Arc::new(vec![1, 2, 3]);
let data_clone = data.clone();

thread::spawn(move || {
    println!("{:?}", data_clone);
});

println!("{:?}", data);

問題3のヒント（Weak）

Weakの使用例：

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

let strong = Rc::new(5);
let weak = Rc::downgrade(&strong);

println!("strong count: {}", Rc::strong_count(&strong));  // 1
println!("weak count: {}", Rc::weak_count(&strong));      // 1

// Weakから値を取得
if let Some(value) = weak.upgrade() {
    println!("value: {}", *value);
}

drop(strong);

// strongがドロップされた後
assert!(weak.upgrade().is_none());

問題4のヒント（パターン選択）

選択基準：

┌─────────────────────────────────────┐
│ スレッド × 可変性マトリクス           │
├─────────────────────────────────────┤
│                                     │
│           不変          可変        │
│ 単一   Rc<T>      Rc<RefCell<T>>    │
│ 複数   Arc<T>     Arc<Mutex<T>>     │
│                   Arc<RwLock<T>>    │
│                                     │
└─────────────────────────────────────┘

ボーナス1のヒント（OnceCell）

unsafeの使用例：

use std::cell::UnsafeCell;

let cell = UnsafeCell::new(5);

unsafe {
    // 生ポインタを取得
    let ptr = cell.get();
    *ptr = 10;
}

MaybeUninitの使用：

use std::mem::MaybeUninit;

let mut uninit: MaybeUninit<i32> = MaybeUninit::uninit();

unsafe {
    uninit.as_mut_ptr().write(42);
    let init = uninit.assume_init();
    println!("{}", init);
}

---

学習の確認

この課題を通じて、以下を理解できたか確認してください：

• [ ] Interior Mutability（RefCell、Cell）
• [ ] 参照カウント（Rc、Arc）
• [ ] Weak参照と循環参照の回避
• [ ] 各パターンの適用場面
• [ ] スレッドセーフな共有パターン
• [ ] パフォーマンスのトレードオフ
• [ ] unsafeを使った低レベル実装

次の章では、unsafeRust、FFI、高度なライフタイムパターンを学びます。

---

参考資料

公式ドキュメント

• std::cell

• std::rc

• std::sync

追加リソース

• "Too Many Lists"

• "The Rustonomicon"

• "Rust Design Patterns"