Crust of Rust: Smart Pointers and Interior Mutability

直播錄影

• 主機資訊
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx ~> neofetch --stdout
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx 
  ​​​​----------------------------------------------- 
  ​​​​OS: Ubuntu 22.04.3 LTS x86_64 
  ​​​​Host: HP Pavilion Plus Laptop 14-eh0xxx 
  ​​​​Kernel: 6.2.0-39-generic 
  ​​​​Uptime: 5 mins 
  ​​​​Packages: 2373 (dpkg), 13 (snap) 
  ​​​​Shell: bash 5.1.16 
  ​​​​Resolution: 3840x2160 
  ​​​​DE: GNOME 42.9 
  ​​​​WM: Mutter 
  ​​​​WM Theme: Adwaita 
  ​​​​Theme: Yaru-dark [GTK2/3] 
  ​​​​Icons: Yaru [GTK2/3] 
  ​​​​Terminal: gnome-terminal 
  ​​​​CPU: 12th Gen Intel i5-12500H (16) @ 4.500GHz 
  ​​​​GPU: Intel Alder Lake-P 
  ​​​​Memory: 3372MiB / 15695MiB
  

• Rust 編譯器版本 ：
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx ~/CrustOfRust> rustc --version
  ​​​​rustc 1.70.0 (90c541806 2023-05-31) (built from a source tarball)
  

Introduction

0:00:00

In this fourth Crust of Rust video, we cover smart pointers and interior mutability, by re-implementing the Cell, RefCell, and Rc types from the standard library. As part of that, we cover when those types are useful, how they work, and what the equivalent thread-safe versions of these types are. In the process, we go over some of the finer details of Rust's ownership model, and the UnsafeCell type. We also dive briefly into the Drop Check rabbit hole (https://doc.rust-lang.org/nightly/#the-rustonomicon) before coming back up for air.

你在 Rust 世界中經常遇到的一些類型，也許你對它們有一些了解，但它們是如此普遍，你需要了解它們，像是 Arc, RC, RefCell, Mutex, Cell, DeRef, AsRef, Borrow, Cow, Sized …。想要好好地了解它們的話，最好的方法就是自己去實作其中幾個，也就是本章節要做的事情。

Discord

0:01:11

Rustacean Station : Discord 連結

Agenda

0:02:31

本次要實作的內容 : Rc, RefCell, Cell
本次要討論的內容 : Arc, Mutex
本次要觀看的內容 : AsRef, Deref, borrow, Cow

我們會先從 cell 實作開始，因為它有最少的怪癖，但要實作之前，先看一下 interior mutability 是什麼，我們才會知道自己要做什麼。

Interior Mutability

0:03:50

Module std::cell

• Shareable mutable containers : 這在 Rust 有點奇怪，因為 Rust 要嘛就是有多個 immutable 參考，要嘛就是只有一個 mutable 參考。這個模組是多種容器類型，可讓您在允許的限制下以受控方式執行此操作
• Interior Mutability : 這種型別它從外面看像是 immutable，但是它有提供方法允許你去改變它。

你擁有的主要三個的是 Cell, RefCell 以及 Mutex 。Mutex 在 Sync 下，而不是 Cell，因為它就是用來解決同步問題的，Mutex 主要由 OS 或 CPU 提供，來確保操作符合預期。不過 Mutex 有點屬於 Cell，你可以將 Mutex 視為 Cell 類型，一種 interior mutability 的型別。

Q : If we could outline why using one versus the other would be great. Shared mutation sounds fine, but there seem to be a number of specialised tools to a similar problem
A : 我們等等來了解不同 Cell 類型、不同 interior mutability 的類型，它們的限制是什麼。Cell, RefCell, Mutex 對於可以放入其中的東西有不同的限制，以及使用方法也有所不同。一般來說，如果你離 Mutex 越遠，你就可以越自由的放任何東西進去，不過要讓型別可以正常工作，所需的後勤工作的開銷也會相對增加，這就有點像是要將用到 lock 的 linked list，想讓 linked list 變成 lock-free 的話，實作會變得非常的麻煩。

Q : what about box?
A : box 不提供 interior mutability，如果你的 box 裡面有共享參考，你就不能去更改 box 裡面的東西。

Q : is there a way to tell that a supposedly immutable struct has some stuff inside it that is mutable like a Cell?
A : 沒有 ! 您無法從類型的外部知道它是否具有 interior mutability。

Cell

0:07:47

Struct std::cell::Cell

看一下 Cell 提供的一些函式的簽章 :

// 傳入你要打包成 Cell 的值
pub const fn new(value: T) -> Cell<T>

// 傳入 immutable reference, 但仍允許你修改 Cell 裡的值
pub fn set(&self, val: T)

// 傳入兩個 Cell 的參考，並將其裡面的值交換
pub fn swap(&self, other: &Cell<T>)

// 假設你有 self 的所有權 (沒有共享參考) 的前提下耗用 self
pub fn into_inner(self) -> T

// 若 T 有 Copy trait，它就會有 get()
// 它回傳的不是 Cell 裡面的值，
// 而是會先複製 Cell 裡面的值再回傳那個複製的值
impl<T> Cell<T>
where
    T: Copy,
pub fn get(&self) -> T

當你看了所有 Cell 的方法之後，你會發現，沒有任何方法是會回傳 Cell 裡面的值的參考，你可以取代裡面的值、拿到裡面複製的值，但你不可以有指標指向 Cell 裡面的值，這很重要，因為如果你不能指向 Cell 裡面的值，這樣操作起來就會很安全，確保了 Cell 在操作值的過程中，沒有指標指向它，在這基礎之上，改變 Cell 裡面的值是安全的。以上這些都是在編譯時期就可以被保證的。

這就像是如果你有一個 queue，這個 queue 若想要確保 thread safety，你不能讓想要增減 queue 的人直接操作 buffer，只能讓他們透過 enqueue() 以及 dequeue() 的方法讓他們達成目的，但 enqueue() 和 dequeue() 就是要透過一些 Mutex 機制來保證在多個執行緒執行完畢後，其結果能符合預期。

接著看到這個實作 :

impl<T> !Sync for Cell<T>
where
    T: ?Sized,

Cell 是不支援多執行緒去執行的，所以就不會有資料爭用的問題。

Q : Question: Why can't we borrow as mut more then once for Rc if it's only one thread
A : 這裡沒有 RC 也沒有借用。一般情況下，你不會使用對 Cell 的 exclusive 參考。如果你擁有對 Cell 的 exclusive 參考，你就可以拿到 Cell 裡面的值得 exclusive 參考，但是這有一個壞處，你將無法呼叫 set(), get() … 方法

pub fn get_mut(&mut self) -> &mut T

Q : In the example you mentioned, you say that if there is a single thread, then there is no need to worry about multiple references to a cell. In that case, what benefit does using Cell…
A : 好處就是你可以有多個東西的共享參考，這個好處也帶來衍伸的優點，第一個優點是你可以把 Cell 存到很多地方，第二個優點是在不同地方或不同資料結構的多個指標都可以指向它。不過因為單執行緒的時候，你知道在一個時間點內，只有一個參考會被使用，Cell 讓你可以在 safe 的程式碼裡面去改變那個值。這看起來有點迂迴，但其實要回到 Rust 要保證只有一個 exclusive 的參考，Cell 就是要讓你繞過編譯器的檢查，因為 Cell 只被限制能在被單一執行緒被執行，而 Rust 之所以要保證只有一個 exclusive 的參考就是要確保 thread safety，但你已經被限制只有單一執行緒，那也就不用考慮 thread safety，因為單一執行緒一定是符合預期的。

Q : So Cell should usually be used for small copy types?
A : 是的，因為你在呼叫 get() 函式的時候，會牽涉到記憶體複製的問題。

Q : is there a Sync version of Cell?
A : 沒有。

開始建置 Rust 專案 :

$ cargo new --lib pointers
$ cd pointers

src/lib.rs :

pub mod cell;

src/cell.rs :

pub struct Cell<T> 
{
    value: T,
}

impl<T> Cell<T> 
{
    pub fn new(value: T) -> Self
    {
        Cell {value}
    }
    
    // 目前無法通過編譯，這裡只是原形
    pub fn set(&self, value: T)
    {
        self.value = value;
    }
    
    pub fn get(&self) -> T
    {
        self.value
    }
}

幾乎所有這些提供 interior mutability 的類型的核心是一種稱為 UnsafeCell 的特殊 Cell 型別。UnsafeCell 持有一些型別，你可以隨時獲得指向這些型別的原始 exclusive 指標。當你知道這樣做是安全的時候，你可以將其轉換為 exclusive 的 Rust 參考。

引入 UnsafeCell 到我們剛剛的實作，這樣我們才可以去改變 immutable 參考的值 :

use std::cell::UnsafeCell;

pub struct Cell<T> 
{
    value: UnsafeCell<T>,
}

Q : Is there a "classic" example of when someone would want to use a Cell?
A : 通常用在很小的值，例如數字、旗標，這些值可能會在很多地方被改動。Cell 很常被用在 Thread local，在 thread local，你知道只有一個執行緒會去存取那個值，你可能會想保存 thread local 的狀態，比如說旗標、計數器或其他東西。但 thread local 只會給你那個值的共享參考，因為一個執行緒可能會想要多次拿取 thread local，Cell 就是個很好的方法去提供 mutability。

Q : So why Cell has a as_ptr method?
A : 它會回傳原始指標指向 Cell 裡面的值，如果想要呼叫這個方法，你就必須要在 unsafe block 裡面做。為什麼暴露原始指標是可以的 ? 因為只有 unsafe block 可以操作原始指標。

回到實作 :

impl<T> Cell<T> 
{
    pub fn new(value: T) -> Self
    {
        Cell {
            value: UnsafeCell::new(value),
        }
    }
    
    pub fn set(&self, value: T)
    {
        // UnsafeCell::get() 函式簽章 :
        //     pub const fn get(&self) -> *mut T
        // *self.value.get() = value;
        //     這裡我們嘗試要解參考原始指標，但編譯器不允許你這麼做，
        //     因為 Rust 編譯器不知道改變值是不是可以的，
        //     它不知道是否有其他執行緒當前在改變那個值
        // 直接用 unsafe block 包起來雖然可以通過編譯器檢查，
        // 但這並沒有預防跨執行緒的使用，要在加入 !Sync 才能確保這件事。
        unsafe { *self.value.get() = value };
    }
    
    pub fn get(&self) -> T
    where 
        T: Copy // 加 bound，讓回傳值是 Copy ，這樣就不會有多個指標指向 value
    {
        unsafe { *self.value.get() } // 加到 unsafe block
    }
}

我們想要讓以下這個 test case 得到錯誤 :

#[cfg(test)]
mod test 
{
    use super::Cell;

    #[test]
    fn concurrent_set() 
    {
        // 我們還沒討論到 Arc，
        // 不過它的功能就是讓我們可以跨執行緒分享參考
        use std::sync::Arc;
        // Cell 必須不允許跨執行緒，
        // 編譯時期就要抓出這個錯誤，
        // 但我們的還沒有支援這個功能。
        let x = Arc::new(Cell::new(42));
        let x1 = Arc::clone(&x);
        std::thread::spawn(|| {
            x1.set(43);
        });
        let x2 = Arc::clone(&x);
        std::thread::spawn(|| {
            x2.set(44);
        });
    }
}

目前程式碼

src/lib.rs :

pub mod cell;

src/cell.rs :

use std::cell::UnsafeCell;

pub struct Cell<T> 
{
    value: UnsafeCell<T>,
}

// implied by UnsafeCell
// impl<T> !Sync for Cell<T> {}

impl<T> Cell<T> 
{
    pub fn new(value: T) -> Self
    {
        Cell {
            value: UnsafeCell::new(value),
        }
    }
    
    pub fn set(&self, value: T)
    {
        unsafe { *self.value.get() = value };
    }
    
    pub fn get(&self) -> T
    where 
        T: Copy
    {
        unsafe { *self.value.get() }
    }
}

#[cfg(test)]
mod test 
{
    use super::Cell;

    #[test]
    fn concurrent_set() 
    {
        use std::sync::Arc;
        let x = Arc::new(Cell::new(42));
        let x1 = Arc::clone(&x);
        std::thread::spawn(|| {
            x1.set(43);
        });
        let x2 = Arc::clone(&x);
        std::thread::spawn(|| {
            x2.set(44);
        });
    }
}

我們明明還沒限制 Cell 只能在單一執行緒執行，測試程式竟然有得到以下錯誤 :

$ cargo test
...
error[E0277]: `cell::Cell<i32>` cannot be shared between threads safely
   --> src\cell.rs:47:28
    |
47  |           std::thread::spawn(|| {
    |  _________------------------_^
    | |         |
    | |         required by a bound introduced by this call
48  | |             x1.set(43);
49  | |         });
    | |_________^ `cell::Cell<i32>` cannot be shared between threads safely
...

為什麼我們明明還沒實作 !Sync，我們的 Cell 就已經支援了只能單一執行緒執行的功能呢 ? 先探討一下編譯器怎麼看待 impl<T> !Sync for Cell<T> {} ，編譯器只有 nightly 支援 impl<T> !Sync for Cell<T> {} 這個語法 (編譯器會提醒你 negative trait bounds are not yet fully implemented; use marker types for now)，想要擺脫這個情形的作法是你在 impl block 裡面放一個 thread unsafe 的值。至於什麼型別是 thread unsafe，就是 UnsafeCell!

因為我們已經在我們的 struct 裡面放 UnsafeCell 的值了，所以我們早就已經有 !Sync 了。就不用在另外實作 impl<T> !Sync for Cell<T> {...} 了。

Trying to Test Cell

0:23:39

新增一個單一執行緒也會錯的 test case :

    #[test]
    fn bad2() 
    {
        let x = Cell::new(vec![42]);
        let first = &x.get()[0];
        x.set(vec![]);
        eprintln!("{}", first);
    }

Q : can you unsafe impl Sync to show your test failing?
A : 看以下實驗

實驗一 (懸空指標)

use std::cell::UnsafeCell;

pub struct Cell<T> 
{
    value: UnsafeCell<T>,
}

// implied by UnsafeCell
// impl<T> !Sync for Cell<T> {}
unsafe impl<T> Sync for Cell<T> {}  // 加這個

impl<T> Cell<T> 
{
    pub fn new(value: T) -> Self
    {
        Cell {
            value: UnsafeCell::new(value),
        }
    }
    
    pub fn set(&self, value: T)
    {
        unsafe { *self.value.get() = value };
    }
    
    pub fn get(&self) -> &T // 回傳參考型態
    {                       // 移除 T: Copy
        unsafe { &*self.value.get() }
    }
}

#[cfg(test)]
mod test 
{
    use super::Cell;

    #[test]
    fn set_during_get() 
    {
        let x = Cell::new(String::from("hello"));
        // 我們不應該將 first 指向 x
        let first = x.get();
        // 即使是不同的記憶體配置，
        // first 也會從指向 "hello" 改指向 "world"
        // 因為記憶體配置器並沒有釋放記憶體，所以指標仍合法
        // 註 : 雖然預期是要展示配置器釋放記憶體導致 first 變為懸空指標
        x.set(String::from("world"));
        // 所以我們預期要得到 hello，卻得到 "world"
        eprintln!("{}", first);
    }
}

驗證 set_during_get 結果 :

$ cargo test --lib set_during_get -- --nocapture
...
running 1 test
world
test cell::test::set_during_get ... ok
...

實驗二 (資料爭用)

use std::cell::UnsafeCell;

pub struct Cell<T> 
{
    value: UnsafeCell<T>,
}

// implied by UnsafeCell
// impl<T> !Sync for Cell<T> {}
unsafe impl<T> Sync for Cell<T> {}  // 加這個

impl<T> Cell<T> 
{
    pub fn new(value: T) -> Self
    {
        Cell {
            value: UnsafeCell::new(value),
        }
    }
    
    pub fn set(&self, value: T)
    {
        unsafe { *self.value.get() = value };
    }
    
    pub fn get(&self) -> T   // get 現在不回傳參考型態
    where 
        T: Copy
    {
        unsafe { *self.value.get() }
    }
}

#[cfg(test)]
mod test 
{
    use super::Cell;

    #[test]
    fn concurrent_set_take2() 
    {
        use std::sync::Arc;
        // 使用陣列來展示資料爭用
        let x = Arc::new(Cell::new([0; 40240]));
        let x1 = Arc::clone(&x);
        let jh1 = std::thread::spawn(move || { // 加上 move
            x1.set([1; 40240]);
        });
        let x2 = Arc::clone(&x);
        let jh2 = std::thread::spawn(move || { // 加上 move
            x2.set([2; 40240]);
        });
        jh1.join().unwrap();
        jh2.join().unwrap();
        let xs = x.get();
        // 預期會有交錯的輸出結果 (失敗的結果)
        // 但底層記憶體系統夠快，所以交錯並沒有發生
        // 只有得到全部是 1 或全部是 2 的結果
        for &i in xs.iter() {
            eprintln!("{}", i);
        }
    }
    
    #[test]
    fn concurrent_get_set() 
    {
        use std::sync::Arc;
        // 使用累加 counter 來展示資料爭用
        let x = Arc::new(Cell::new(0));
        let x1 = Arc::clone(&x);
        let jh1 = std::thread::spawn(move || {
            for _ in 0..1000000 {
                let x = x1.get();
                x1.set(x + 1);
            }
        });
        let x2 = Arc::clone(&x);
        let jh2 = std::thread::spawn(move || {
            for _ in 0..1000000 {
                let x = x2.get();
                x2.set(x + 1);
            }
        });
        jh1.join().unwrap();
        jh2.join().unwrap();
        assert_eq!(x.get(), 2000000);
    }
}

驗證 concurrent_set_take2，因為資料爭用 (x 的參考)，導致交錯的結果 (因為記憶體系統過快導致沒展示出我們想展示的交錯) :

$ cargo test --lib concurrent_set_take2 -- --nocapture 2>&1 | sort | uniq -c
...
40240 1
...

$ cargo test --lib concurrent_set_take2 -- --nocapture 2>&1 | sort | uniq -c
...
40240 2
...

驗證 concurrent_get_set，因為資料爭用導致非預期的結果 :

$ cargo test --lib concurrent_get_set -- --nocapture
...
running 1 test
thread 'cell::test::concurrent_get_set' panicked at 'assertion failed: `(left == right)`
  left: `1003052`,
 right: `2000000`', src/cell.rs:86:9
...

---

目前程式碼

註解掉 unsafe impl<T> Sync for Cell<T> {}，讓 Cell 不能多執行緒執行 :

use std::cell::UnsafeCell;

pub struct Cell<T> 
{
    value: UnsafeCell<T>,
}

// implied by UnsafeCell
// impl<T> !Sync for Cell<T> {}
// unsafe impl<T> Sync for Cell<T> {}

impl<T> Cell<T> 
{
    pub fn new(value: T) -> Self
    {
        Cell {
            value: UnsafeCell::new(value),
        }
    }
    
    pub fn set(&self, value: T)
    {
        // SAFETY: we know no-one else is concurrently mutating (because !Sync)
        // SAFETY: we know we're not invalidating any references, because we never give any out
        unsafe { *self.value.get() = value };
    }
    
    pub fn get(&self) -> T
    where 
        T: Copy
    {
        // SAFETY: we know no-one else is modifying this value, since this thread can mutate
        // (because !Sync), and it is executing this function instea
        unsafe { *self.value.get() }
    }
}

#[cfg(test)]
mod test 
{
    use super::Cell;

    #[test]
    fn concurrent_set_take2() 
    {
        use std::sync::Arc;
        let x = Arc::new(Cell::new([0; 40240]));
        let x1 = Arc::clone(&x);
        let jh1 = std::thread::spawn(move || {
            x1.set([1; 40240]);
        });
        let x2 = Arc::clone(&x);
        let jh2 = std::thread::spawn(move || {
            x2.set([2; 40240]);
        });
        jh1.join().unwrap();
        jh2.join().unwrap();
        let xs = x.get();
        for &i in xs.iter() {
            eprintln!("{}", i);
        }
    }
    
    #[test]
    fn concurrent_get_set() 
    {
        use std::sync::Arc;
        let x = Arc::new(Cell::new(0));
        let x1 = Arc::clone(&x);
        let jh1 = std::thread::spawn(move || {
            for _ in 0..1000000 {
                let x = x1.get();
                x1.set(x + 1);
            }
        });
        let x2 = Arc::clone(&x);
        let jh2 = std::thread::spawn(move || {
            for _ in 0..1000000 {
                let x = x2.get();
                x2.set(x + 1);
            }
        });
        jh1.join().unwrap();
        jh2.join().unwrap();
        assert_eq!(x.get(), 2000000);
    }
}

Q : What is the point of allowing T to be non-Copy (like String) if we only have the .get() method for Copy types?
A : 為什麼 struct 不宣告成這樣 : pub struct Cell<T: Copy> ? 我們是可以這麼做，只有泛型是 Copy 型態的才能呼叫 Cell，但只有 get 方法會用到 Copy 的 bound，我們希望我們的 bound 只放在需要的地方就好。

UnsafeCell

0:40:17

Q : an you explain why we need UnsafeCell and cannot just cast (unsafely) the &T to a mutable reference/pointer?
A : 在 Rust，唯一的方法可以正確地將共享參考轉換成 exclusive 參考是一定要使用 UnsafeCell，因為 Rust 本來就永不允許你將共享參考直接轉換成 exclusive 參考，這條件保證了編譯器在最佳化的時候不會出錯。

RefCell

0:41:21

Struct std::cell::RefCell : A mutable memory location with dynamically checked borrow rules。

Q : Cell the type which had special compiler instructions or was it something else?
A : 沒有。UnsafeCell 是特別的型別，但 Cell 不是。

正常來說，所有的 borrow checking 是在編譯時期做的。但 RefCell 讓你等到執行時期才去做 borrow checking，如果你正在走訪一張循環圖，這將會很方便 : 可能在遞迴的早期，您已經獲得了對此節點的 mutable 參考，但稍後你嘗試對同一節點 (因為循環圖) 採用 mutable 參考，並且 RefCell 將捕獲這種情況，但假設你現在有個圖，你知道它沒有循環，這時候你就不會取道同一節點的 mutable 參考。不過編譯器並不知道你在走訪的過程中會不會因為循環而拿到 mutable 參考，這時的 RefCell 就可以滿足這個需求。

Q : Actually RefCell sounds like a good use-case for single-threaded binary trees with cycles
A : 沒錯。

src/lib.rs :

pub mod cell;
+pub mod refcell;

src/refcell.rs :

use std::cell::UnsafeCell;

enum RefState 
{
    Unshared,
    Shared(usize),
    Exclusive,
}

pub struct RefCell<T>
{
    // RefCell 其核心也是 UnsafeCell。
    value: UnsafeCell<T>,
    // 用來追蹤目前借用情況如何。
    state: RefState,
}

impl<T> RefCell<T>
{
    pub fn new(value: T) -> Self 
    {
        Self {
            value: UnsafeCell::new(value),
            state: RefState::Unshared,
        }
    }
    
    // 如果你嘗試借用 (呼叫 borrow)，
    // 那麼你將得到一個 Some，呼應了 Rust 程式可以有多個共享參考，
    // 直到已經提供了 exclusive 參考 (呼叫 borrow_mut)
    pub fn borrow(&self) -> Option<&T> 
    {
        None
    }
    
    // 如果值已經被借用了，又再呼叫一次 borrow_mut，
    // 它將會回傳 None 來保持 Rust 程式只有一個 exclusive 參考的原則。
    pub fn borrow_mut(&self) -> Option<&mut T>
    {
        None
    }
}

Q : Why can't we use the borrow and borrowmut trait here?
A : 這兩個 trait 是為了一些非常不同的東西，等等你就會知道為什麼。

Q : are you intentionally deviating from the RefCell api in std lib?
A : 沒有，是想透過簡化程式碼來讓你了解 RefCell 的原理。

開始實作 borrow 以及 borrow_mut :

    pub fn borrow(&self) -> Option<&T> 
    {
        match self.state {
            RefState::Unshared => {
                self.state = RefState::Shared(1);
                Some(unsafe { &*self.value.get() })
            }
            RefState::Shared(n) => {
                self.state = RefState::Shared(n + 1);
                Some(unsafe { &*self.value.get() })
            }
            RefState::Exclusive => None,
        }
    }

    pub fn borrow_mut(&self) -> Option<&mut T>
    {
        if let RefState::Unshared = self.state {
            self.state = RefState::Exclusive;
            Some(unsafe {&mut *self.value.get()})
        } else {
            None
        }
    }

想法是這樣，但實作有兩大問題 :

1. 因為我們嘗試修改了共享參考的值。
2. 我們目前的實作並不保證 thread safety。

這兩個問題都出在 self.state 修改的那幾行。

想要一次解決兩個問題，只要使用我們剛剛實作的 Cell 即可 :

use std::cell::UnsafeCell;
use crate::cell::Cell;

+#[derive(Copy, Clone)] // 加這行，原因是為了 Line 18
enum RefState 
{
    Unshared,
    Shared(usize),
    Exclusive,
}

pub struct RefCell<T>
{
    value: UnsafeCell<T>,
-   state: RefState,
+   // 回想 Cell 特性
+   //    1. 只能在單一執行緒被編譯。
+   //    2. get 需要回傳 Copy 型態而不是參考
+   state: Cell<RefState>,
}

impl<T> RefCell<T>
{
    pub fn new(value: T) -> Self 
    {
        Self {
            value: UnsafeCell::new(value),
-           state: RefState::Unshared,
+           state: Cell::new(RefState::Unshared),
        }
    }
    
    pub fn borrow(&self) -> Option<&T> 
    {
-       match self.state {
+       match self.state.get() {
            RefState::Unshared => {
-               self.state = RefState::Shared(1);
+               self.state.set(RefState::Shared(1));
                Some(unsafe { &*self.value.get() })
            }
            RefState::Shared(n) => {
-               self.state = RefState::Shared(n + 1);
+               self.state.set(RefState::Shared(n + 1));
                Some(unsafe { &*self.value.get() })
            }
            RefState::Exclusive => None,
        }
    }

    pub fn borrow_mut(&self) -> Option<&mut T>
    {
-       if let RefState::Unshared = self.state {
+       if let RefState::Unshared = self.state.get() {
-           self.state = RefState::Exclusive;
+           self.state.set(RefState::Exclusive);
            Some(unsafe {&mut *self.value.get()})
        } else {
            None
        }
    }
}

目前程式碼

use std::cell::UnsafeCell;
use crate::cell::Cell;

#[derive(Copy, Clone)]
enum RefState 
{
    Unshared,
    Shared(usize),
    Exclusive,
}

pub struct RefCell<T>
{
    value: UnsafeCell<T>,
    state: Cell<RefState>,
}

impl<T> RefCell<T>
{
    pub fn new(value: T) -> Self 
    {
        Self {
            value: UnsafeCell::new(value),
            state: Cell::new(RefState::Unshared),
        }
    }
    
    pub fn borrow(&self) -> Option<&T> 
    {
        match self.state.get() {
            RefState::Unshared => {
                self.state.set(RefState::Shared(1));
                // SAFETY: no exclusive references have been given out since state would be
                // Exclusive.
                Some(unsafe { &*self.value.get() })
            }
            RefState::Shared(n) => {
                self.state.set(RefState::Shared(n + 1));
                // SAFETY: no exclusive references have been given out since state would be
                // Exclusive.
                Some(unsafe { &*self.value.get() })
            }
            RefState::Exclusive => None,
        }
    }

    pub fn borrow_mut(&self) -> Option<&mut T>
    {
        if let RefState::Unshared = self.state.get() {
            self.state.set(RefState::Exclusive);
            // SAFETY: no ohter references have been given out since state would be
            // Shared or Exclusive.
            Some(unsafe {&mut *self.value.get()})
        } else {
            None
        }
    }
}

Q : could you use an AtomicIsize to make it thread-safe?
A : 等講到 Mutex 的部分會來談。Mutex 基本上是 rw lock 以及 thread safe 版本的 RefCell

Q : when using something like Rayon, would using RefCell/Cell make no sense? Would you just rely on Mutex?
A : 對於 Rayon，您需要 thread safe 的東西，例如 mutex, rw lock 或者其它的同步化原始物件；而 RefCell 不是 thread safe，也不需要是。

RefCell Smart Pointer

0:54:21

剛剛的程式碼其實還有一個問題，就是我們的實作只會增加參考計數器的值，並沒有減少參考計數器的值，所以一旦你呼叫了 borrow()，你之後就再也不能呼叫 borrow_mut() 了。

所以我們的 borrow() 不能只是回傳共享參考，borrow_mut() 不能只回傳 mutable 參考，因為呼叫者若拿到這些參考後，我們將無法追蹤他們的使用情形，所以我們需要回傳其他型別，也就是 Ref 型別和 RefMut 型別。

先新增定義 Ref 型別和 RefMut 型別以及相關實作 :

// 成員是指向 RefCell 的指標，因為當 RefCell 消失時，
// 我們當然需要確保所有參考都消失，否則這些參考將具有懸空指標。
pub struct Ref<'refcell, T> 
{
    refcell: &'refcell RefCell<T>,
}

impl<T> Drop for Ref<'_, T>
{
    // 當你呼叫 drop，會遞減參考計數器的值
    fn drop(&mut self)
    {
        match self.refcell.state.get() {
            // 只有在 share 的時候才有可能呼叫 drop
            RefState::Exclusive | RefState::Unshared => unreachable!(),
            RefState::Shared(1) => {
                self.refcell.state.set(RefState::Unshared);
            },
            RefState::Shared(n) => {
                self.refcell.state.set(RefState::Shared(n - 1));
            }
        }
    }
}

pub struct RefMut<'refcell, T> 
{
    refcell: &'refcell RefCell<T>,
}

impl<T> Drop for RefMut<'_, T>
{
    fn drop(&mut self)
    {
        match self.refcell.state.get() {
            // 不可能在呼叫 Drop 時，狀態為 Shared
            RefState::Shared(_) | RefState::Unshared => unreachable!(),
            RefState::Exclusive => {
                self.refcell.state.set(RefState::Unshared);
            }
        }
    }
}

再修改 borrow 以及 borrow_mut 函式 :

...
-   pub fn borrow(&self) -> Option<&T>
+   pub fn borrow(&self) -> Option<Ref<'_, T>>
    {
        match self.state.get() {
            RefState::Unshared => {
                self.state.set(RefState::Shared(1));
-               // SAFETY: no exclusive references have been given out since state would be
-               // Exclusive.
-               Some(unsafe { &*self.value.get() })
+               Some(Ref { refcell: self })
            }
            RefState::Shared(n) => {
                self.state.set(RefState::Shared(n + 1));
-               // SAFETY: no exclusive references have been given out since state would be
-               // Exclusive.
-               Some(unsafe { &*self.value.get() })
+               Some(Ref { refcell: self })
            }
            RefState::Exclusive => None,
        }
    }

-   pub fn borrow_mut(&self) -> Option<&mut T>
+   pub fn borrow_mut(&self) -> Option<RefMut<'_, T>>
+   // 這裡沒有阻止人們在這裡編寫會崩潰的程式碼。
+   // 他們可以 unwrap 回傳值，但他們無法同時獲得對某些內部值的 exclusive 參考。
    {
        if let RefState::Unshared = self.state.get() {
            self.state.set(RefState::Exclusive);
            // SAFETY: no ohter references have been given out since state would be
            // Shared or Exclusive.
-           Some(unsafe {&mut *self.value.get()})
+           Some(RefMut { refcell: self })
        } else {
            None
        }
    }
}

但現在呼叫者拿到的是 Ref 和 RefMut 型態，那呼叫者怎麼拿到 T 的值 ? 因為呼叫者本來就是想要拿到 T 值，而不是這兩種我們定義的型態，而要解決這個問題的方法是實作 Deref/DererMut trait :

// 1. Deref 基本上是一個 trait，每當你使用 . 運算子時就會呼叫它。
//    當你擁有一個型別為 T 的值，並執行類似 value.method 的操作時，
//    如果 T 沒有該方法，但它解參考到具有該方法的類型，
//    那麼 Deref trait 就會被呼叫。這基本上是一種自動深入型別的方式。
// 2. Ref 是智慧指標，它是個指向某些內部類型的透明指標，
//    但是當你卸除 (drop) 它時它具有附加語義，這基本上就是智慧指標。
impl<T> std::ops::Deref for Ref<'_, T> 
{
    type Target = T;
    // 傳入 self 的參考，而回傳型態是 Self::Target 的參考
    fn deref(&self) -> &Self::Target
    {
        // a `Ref` is only created if `no exclusive` references have been given out.
        // once it is given out, state is set to `Shared`. so `no exlusive` references are given out.
        // so dereferencing into a shared reference is fine.
        // 先 * 再 & 看似抵銷了作用，
        // 實際上 * 會探到最底層的型別，& 則是取得最底層型別的參考
        unsafe { &*self.refcell.value.get() }
    }
}

impl<T> std::ops::Deref for RefMut<'_, T> 
{
    type Target = T;
    // 傳入 self 的參考，而回傳型態是內部 (Target) 的共享參考
    fn deref(&self) -> &Self::Target
    {
        // SAFETY: 
        // see safety for DerefMut
        unsafe { &*self.refcell.value.get() }
    }
}

// RefMut 還要實作 DerefMut
// 1. DerefMut 讓你從 mutable 參考變成智慧指標，
//    回傳型態是內部 (Target) 的 mutable 參考。
// 2. RefMut 有 DerefMut 是對的，但在 Ref 就是錯的，
//    因為 Ref 如果也有 DerefMut，將導致 Shared 狀態有多個內部 mutable 參考
//    但 RefMut 是用在 Exclusive 狀態，所以不會有這個問題。

impl<T> std::ops::DerefMut for RefMut<'_, T> 
{
    // 傳入 self 的參考，而回傳型態是 Self::Target 的參考
    fn deref_mut(&mut self) -> &mut Self::Target
    {
        // SAFETY: 
        // a `RefMut` is only created if `no other` references have been given out.
        // once it is given out, state is set to `Exclusive`. so no `future` references are given out.
        // so we have an exclsive lease on the inner value, so mutably dereferencing is fine.
        unsafe { &mut *self.refcell.value.get() }
    }
}

Q : Is it common practice to write SAFETY comments for every unsafe use?
A : 是的，非常建議你這樣做。如果你的程式有 unsafe 區塊，您應該確保記錄保持 safe 的要求。

目前程式碼

src/lib.rs :

pub mod cell;
pub mod refcell;

src/refcell.rs :

use std::cell::UnsafeCell;
use crate::cell::Cell;

#[derive(Copy, Clone)]
enum RefState 
{
    Unshared,
    Shared(usize),
    Exclusive,
}

pub struct RefCell<T>
{
    value: UnsafeCell<T>,
    state: Cell<RefState>,
}

impl<T> RefCell<T>
{
    pub fn new(value: T) -> Self 
    {
        Self {
            value: UnsafeCell::new(value),
            state: Cell::new(RefState::Unshared),
        }
    }
    
    pub fn borrow(&self) -> Option<Ref<'_, T>>
    {
        match self.state.get() {
            RefState::Unshared => {
                self.state.set(RefState::Shared(1));
                Some(Ref { refcell: self })
            }
            RefState::Shared(n) => {
                self.state.set(RefState::Shared(n + 1));
                Some(Ref { refcell: self })
            }
            RefState::Exclusive => None,
        }
    }

    pub fn borrow_mut(&self) -> Option<RefMut<'_, T>>
    {
        if let RefState::Unshared = self.state.get() {
            self.state.set(RefState::Exclusive);
            // SAFETY: no ohter references have been given out since state would be
            // Shared or Exclusive.
            Some(RefMut { refcell: self })
        } else {
            None
        }
    }
}

pub struct Ref<'refcell, T> 
{
    refcell: &'refcell RefCell<T>,
}

impl<T> std::ops::Deref for Ref<'_, T> 
{
    type Target = T;
    fn deref(&self) -> &Self::Target
    {
        // a `Ref` is only created if `no exclusive` references have been given out.
        // once it is given out, state is set to `Shared`. so `no exlusive` references are given out.
        // so dereferencing into a shared reference is fine.
        unsafe { &*self.refcell.value.get() }
    }
}

impl<T> Drop for Ref<'_, T>
{
    fn drop(&mut self)
    {
        match self.refcell.state.get() {
            RefState::Exclusive | RefState::Unshared => unreachable!(),
            RefState::Shared(1) => {
                self.refcell.state.set(RefState::Unshared);
            },
            RefState::Shared(n) => {
                self.refcell.state.set(RefState::Shared(n - 1));
            }
        }
    }
}


pub struct RefMut<'refcell, T> 
{
    refcell: &'refcell RefCell<T>,
}


impl<T> std::ops::Deref for RefMut<'_, T> 
{
    type Target = T;
    fn deref(&self) -> &Self::Target
    {
        // SAFETY: 
        // see safety for DerefMut
        unsafe { &*self.refcell.value.get() }
    }
}

impl<T> std::ops::DerefMut for RefMut<'_, T> 
{
    fn deref_mut(&mut self) -> &mut Self::Target
    {
        // SAFETY: 
        // a `RefMut` is only created if `no other` references have been given out.
        // once it is given out, state is set to `Exclusive`. so no `future` references are given out.
        // so we have an exclsive lease on the inner value, so mutably dereferencing is fine.
        unsafe { &mut *self.refcell.value.get() }
    }
}

impl<T> Drop for RefMut<'_, T>
{
    fn drop(&mut self)
    {
        match self.refcell.state.get() {
            RefState::Shared(_) | RefState::Unshared => unreachable!(),
            RefState::Exclusive => {
                self.refcell.state.set(RefState::Unshared);
            }
        }
    }
}

Rc (reference counted ptr)

1:06:27

Module std::rc

• Single-threaded reference-counting pointers. Rc stands for ‘Reference Counted’
  • The type Rc<T> provides shared ownership of a value of type T, allocated in the heap. Invoking clone on Rc produces a new pointer to the same allocation in the heap. When the last Rc pointer to a given allocation is destroyed, the value stored in that allocation (often referred to as “inner value”) is also dropped.
  • Shared references in Rust disallow mutation by default, and Rc is no exception: you cannot generally obtain a mutable reference to something inside an Rc. If you need mutability, put a Cell or RefCell inside the Rc; see an example of mutability inside an Rc.

RC 適合用在一個元素出現在多個地方的資料結構，假設在你的程式有一個大的 blob，你應該不會想有很多它的複本，而是有很多指標指向 blob，但問題是，你要在什麼時間點去釋放那個儲存在 heap 空間的 blob ? 答案是，當全部指向 blob 的指標全部消失，那你要怎麼知道已經沒有指標指向 blob ? RC 就是提供這功能。

但關鍵的是，RC 並不是 Sync 以及 Sent (後面回談到)，基本上 RC 並不是 thread safe，RC 只能在單一執行緒做參考計數，但即便是在單一執行緒，對資料的上下文, 圖以及其它資料結構也是非常有幫助的。

Q : How does RC handle cyclic references?
A : 事實並非如此，如果你有一個循環，那麼循環只會阻止它被釋放。標準函式庫的 RC 有 Weak 智慧指標以及 Strong 智慧指標。它們的差別是，Weak 智慧指標不會阻止東西被刪除，而 Strong 智慧指標則會。如果 Strong 智慧指標的計數變成 0，那東西就會被 deallocate；而 Weak 智慧指標，你在使用它們之前，必須將它們 upgrade 為實指標，並且 upgrade 將會失敗。更詳細資訊請自行參考官方文件。

src/lib.rs :

pub mod cell;
pub mod refcell;
+pub mod rc;

src/rc.rs :

// `refcount` 必須是 `Rc` 的所有複本之間共享的值 ，
// 所以要將內部值跟參考計數打包在一起。
// (與 Line 18 比較差異)
struct RcInner<T>
{
    value: T,
    refcount: usize,
}
// 1. `T` 要存在 heap 是因為如果我的程式有多個函式，
//    而這些函式都在某處引用了 `T`，`T` 不能在函式的 stack 裡，
//    不然某函式回傳的時候，`T` 也會跟著該函式一起被釋放掉。
// 2. `RC` 有點像 `Box<T>`，但也不全然是，
//    因為如果我們 Clone 了 RC，我們就會 Clone `Box` 以及
//    它指向的那個在 heap 的值，而我們的目的是不要有複本的產生。
pub struct Rc<T>
{
    inner: *const RcInner<T>,
    // refcount: uszie,
    //     refcount 若放在表示每個 Rc 都有自己的參考計數
    //     這樣無法知道還有沒有指標指向 T 的值
    // (與 Line 7 比較差異)
}

impl<T> Rc<T>
{
    pub fn new(v: T) -> Self
    {
        let inner = Box::new(RcInner {
            value: v,
            refcount: 1,
        });
        
        Rc {
            // into_raw : 耗用 Box, 並給我們一個指標指向它
            // 即使我們不再有 Box，也不能卸除 Box (解決 Line 38 問題)
            inner: Box::into_raw(inner),
        }
        // Rc { inner: &*inner }
        //     不能這樣寫，因為當 new 函式結束的時候，
        //     inner 的值會被卸除，這樣回傳的參考將指向無效的記憶體空間
    }
}

impl<T> std::ops::Deref for Rc<T>
{
    type Target = T;
    fn deref(&self) -> &Self::Target 
    {
        // 拿到 self.inner 的參考，並且解參考是沒問題的 (Line 36)，
        // 但編譯器本身並不知道 `*const RcInner<T>` 是否有效。
        // 所以這裡才需要用到一個 unsafe block。
        // SAFETY: self.inner is a Box that only deallocated when the last Rc goes away
        // we have an Rc, therefore the Box has not been deallocated, so deref is fine.
        &unsafe { &*self.inner }.value
    }
}

// 1. 我們實際上不要求 T 一定要是 Clone 型態，
//    因為當我們 Clone Rc 時，我們實際上是增加參考計數而不是複製內部的值。
// 2. 有個問題是，如果你有 `Rc`，編譯器並不知道
//     `*const RcInner<T>` 是否有效，解決問題的作法是 Line 36
//    該作法確保了記憶體還會是合法，即使編譯器無法判斷記憶體是否合法。
impl<T> Clone for Rc<T>
{
    fn clone(&self) -> Self
    {
        let inner = unsafe { &*self.inner };
        inner.refcount += 1;
        Rc { inner: self.inner }
    }
}

Q : RC's are quite useful when building GTK apps since passing a reference to a closure is somewhat tricky. Wrap your value in a RC, clone and send to your closure.
A : 在任何像單一執行緒這樣的東西中，例如通常是 GUI 迴圈，Rc 非常適合這種東西。

Q : if you could explain the difference between reference types such as &mut T, *mut T and *const T and if there are any more
A :

• 型態前面若只有 & 則表示共享參考，你必須保證沒有 exclusive 參考指向該型態；類似地，型態前面有 &mut 則表示 exclusive 參考，你知道它沒有其它的共享參考指向該值。
• *mut T 和 *const T 不是參考，它們是原始指標，所以它並沒有像 &/&mut 保證共享/exclusive 參考指向該型態。舉例來說，如果你現在有 *mut/*const，你沒辦法保證沒有其它 *mut/*const 指向同一個值，但你對 * 也無能為力。所以當你有原始指標，你可以做的事是使用 unsafe block 去解參考它，將它轉成參考，這行為是 unsafe，所以你需要記錄下你做了什麼確保它是 safe 的。
• *mut 和 *const 的差異是 *mut 是你可能能夠改變的東西，你可能擁有 exclusive 參考的東西；*const 則表明這個值永遠不能被改變。一般來說，你不能將 constant 指標轉成 exclusive 參考，反之則不然。

Q : What does Box provide for us?
A : heap 記憶體配置。

目前程式碼

src/lib.rs :

pub mod cell;
pub mod refcell;
pub mod rc;

src/rc.rs :

struct RcInner<T>
{
    value: T,
    refcount: usize,
}

pub struct Rc<T>
{
    inner: *const RcInner<T>,
}

impl<T> Rc<T>
{
    pub fn new(v: T) -> Self
    {
        let inner = Box::new(RcInner {
            value: v,
            refcount: 1,
        });
        
        Rc {
            inner: Box::into_raw(inner),
        }
    }
}

impl<T> std::ops::Deref for Rc<T>
{
    type Target = T;
    fn deref(&self) -> &Self::Target 
    {
        // SAFETY: self.inner is a Box that only deallocated when the last Rc goes away
        // we have an Rc, therefore the Box has not been deallocated, so deref is fine.
        &unsafe { &*self.inner }.value
    }
}

impl<T> Clone for Rc<T>
{
    fn clone(&self) -> Self
    {
        let inner = unsafe { &*self.inner };
        inner.refcount += 1;
        Rc { inner: self.inner }
    }
}

接著使用我們前面實作的 Cell 讓程式只能在單一執行緒執行 :

+use crate::cell::Cell;

struct RcInner<T>
{
    value: T,
-   refcount: usize,
+   refcount: Cell<usize>,
}
...
impl<T> Rc<T>
{
    pub fn new(v: T) -> Self
    {
        let inner = Box::new(RcInner {
            value: v,
-           refcount: 1,
+           refcount: Cell::new(1),
        });
        
        Rc {
            inner: Box::into_raw(inner),
        }
    }
}
...
impl<T> Clone for Rc<T>
{
    fn clone(&self) -> Self
    {
        let inner = unsafe { &*self.inner };
-       inner.refcount += 1;
+       let c = inner.refcount.get();
+       inner.refcount.set( c + 1);
        Rc { inner: self.inner }
    }
}

Q : Isn't unsafe a pretty weird keyword name. It just means something the compiler cannot guarantee is safe, not that it actually is unsafe.
A : unsafe 關鍵字確實有點奇怪，它真實的意思是，我已經自己檢查了 unsafe block 裡面的程式是 safe 的，它並不是表示 unsafe block 裡面的程式是 unsafe。

目前程式遇到跟前面 RefCell 只有遞增參考計數器，而沒有遞減的問題，這將導致 Box 永遠不會被釋放，為 Rc 實作 drop 函式即可解決 :

impl<T> Drop for Rc<T>
{
    // 這裡先想一個問題，當我們卸除 Rc 的值
    // 我們是否也要卸除 T 的值 ? 要的話，時間點是什麼 ?
    fn drop(&mut self)
    {
        let inner = unsafe { &*self.inner };
        let c = inner.refcount.get();
        if c == 1 {
            // SAFETY: we are the _only_ Rc left, and we are being dropped.
            // therefore, after us, there will be no Rc's, and no references to T.
            drop(inner);
            // 1. 編譯失敗
            //    [rust c E0308] [E] mismatched types
            //    expected raw pointer `*mut _`
            //       found raw pointer `*const rc::RcInner<T>`
            //    之所以要求型態是 `*mut _` 是因為不想讓你傳入可能為共享的原始指標，
            //    並且再讓共享的原始指標轉為 Box。
            // 2. 這裡有一些相當微妙的東西在起作用，
            //    這與 Rust 中稱為 Variance 的東西有關。
            // 3. 最簡單的解決辦法是將 `*const rc::RcInner<T>` 
            //    改成 `*mut rc::RcInner<T>`，但我們不這麼做，請繼續看下去。
            let _ = Box::from_raw(self.inner);
        } else {
            // there are other Rcs, so don't drop the Box!
            inner.refcount.set(c - 1)
        }
    }
}

Q : what is the relationship between Box::into_raw and Box::leak
A : Box::into_raw 給你原始指標，你將可以對它做任何事，包含改變它的值。Box::leak 給你 static 共享參考指向 heap 記憶體，當你記憶體洩漏，它將活到到整個程式結束，但給 static 共享參考是可以的，因為 static 暗示著這個共享參考也是活到整個程式結束，但你不能改變它的值，因為它是完全共享的參考。

目前程式碼

無檢查點，因為 Rc 還無法編譯。

NonNull

1:23:49

Struct std::ptr::NonNull

• *mut T but non-zero and covariant.
• 使用 NonNull 的目的是為了最佳化，編譯器會知道，指標指向的值不可能是 Null，不像 *mut 可能指向 0 或 Null 值。所以編譯器可以使用它的 nullptr 作為其他值來使用。舉例來說 : Option<NonNull<T>>， 編譯器可以使用 nullptr 來表示 None，這將讓 Option 沒有額外開銷。
• NonNull 有點像 *mut :
  ​​​​// 我們給它一個 `*mut`，我們從 Box 獲取 `*mut`。
  ​​​​pub fn new(ptr: *mut T) -> Option<NonNull<T>>
  ​​​​// 回傳 `*mut T`，這是 Box::into_raw 所需要的型態。
  ​​​​pub const fn as_ptr(self) -> *mut T
  

加入 NonNull 結構到現有的程式碼 :

use crate::cell::Cell;
+use std::ptr::NonNull;

struct RcInner<T>
{
    value: T,
    refcount: Cell<usize>,
}

pub struct Rc<T>
{
-   inner: *const RcInner<T>,
+   inner: NonNull<RcInner<T>>,
+   // 原本是 inner: *const RcInner<T>，所以原本為了解參考到最底層
+   //     所以 Deref 回傳值要用到 &* 這種看似彆扭的寫法 : 
+   //         &unsafe { &*self.inner}.value 
+   // 現在是 NonNull<RcInner<T>>，
+   //     Deref 回傳值要用到 as_ref() 的寫法 :
+   //         &unsafe { self.inner.as_ref() }.value
}

impl<T> Rc<T>
{
    pub fn new(v: T) -> Self
    {
        let inner = Box::new(RcInner {
            value: v,
            refcount: Cell::new(1),
        });
        
        Rc {
-           inner: Box::into_raw(inner),
+           // SAFETY: Box does not give us a null pointers.
+           // 使用的函式如下 :
+           //     pub const unsafe fn new_unchecked(ptr: *mut T) -> NonNull<T>
+           inner: unsafe {NonNull::new_unchecked(Box::into_raw(inner))},
        }
    }
}

impl<T> std::ops::Deref for Rc<T>
{
    type Target = T;
    fn deref(&self) -> &Self::Target 
    {
        // SAFETY: self.inner is a Box that only deallocated when the last Rc goes away
        // we have an Rc, therefore the Box has not been deallocated, so deref is fine.
-       &unsafe { &*self.inner }.value
+       // 使用的函式如下 :
+       //     pub const unsafe fn as_ref<'a>(&self) -> &'a T
+       &unsafe { self.inner.as_ref() }.value
    }
}

impl<T> Clone for Rc<T>
{
    fn clone(&self) -> Self
    {
-       let inner = unsafe { &*self.inner };
+       // 使用的函式如下 :
+       //     pub const unsafe fn as_ref<'a>(&self) -> &'a T
+       let inner = unsafe { self.inner.as_ref() };
        let c = inner.refcount.get();
        inner.refcount.set( c + 1);
        Rc { inner: self.inner }
    }
}

impl<T> Drop for Rc<T>
{
    fn drop(&mut self)
    {
-       let inner = unsafe { &*self.inner };
+       // 使用的函式如下 :
+       //     pub const unsafe fn as_ref<'a>(&self) -> &'a T
+       let inner = unsafe { self.inner.as_ref() };
        let c = inner.refcount.get();
        if c == 1 {
            // SAFETY: we are the _only_ Rc left, and we are being dropped.
            // therefore, after us, there will be no Rc's, and no references to T.
+           // 為什麼在 Line 92 之前要卸除 inner 的值 ?
+           // 因為如果不先卸除 inner 的值，它會被拖到 drop 函式結束才被卸除 (Line 99)
+           // 如果使人可以再 Line 92 之後又 `意外地` 去操作 inner，編譯器並不會去警告這個情形。
+           // !!! 先卸除 inner 的值保證其它人不在 Box 被釋放後 (Line 85) 還去操作它!!!
+           drop(inner);
-           let _ = Box::from_raw(self.inner);
+           // 1. 使用的函式如下 :
+           //        pub const fn as_ptr(self) -> *mut T
+           // 2. 用 unsafe block 是因為編譯器不知道我們有最後一個指標，
+           //    因此編譯器沒辦法判斷將其轉回 Box 並卸除是否有問題，
+           //    但我們知道我們有最後一個指標因為我們正確地保留了參考計數。
+           let _ = unsafe { Box::from_raw(self.inner.as_ptr()) };
+           // inner.refcount.set(0);
        } else {
            // there are other Rcs, so don't drop the Box!
            inner.refcount.set(c - 1)
        }
    }
}

Q : Can't we leak a mutable reference to the value in RefCell by calling deref on RefMut, storing the return value somewhere, and then dropping RefMut?
A : 不行，回到 src/refcell.rs :

impl<T> std::ops::DerefMut for RefMut<'_, T> 
{
    // 這裡有 implicit 生命週期 :
    fn deref_mut<'a >(&'a mut self) -> &'a mut Self::Target
    {
        unsafe { &mut *self.refcell.value.get() }
    }
}

回傳值 mut Self::Target 參考的生命週期最長只能跟傳入值 mut self (RefMut) 參考一樣。如果您嘗試將從 DerefMut 返回的值儲存到某處，然後卸除 RefMut，並嘗試再次使用 &'a mut Self::Target，編譯器會說這是不允許的，因為你正在嘗試在它所綁定的生命週期已經過期之後 (mut self 參考已經消失了) 使用 mut Self::Target 參考。

Q : if we have a mut pointer why do we need a Cell?
A : 在 src/rc.rs 中，我們沒有使用 mutable 指標，其原因是改變它的值並不安全。這又可以談到mutable 指標與 mutable 參考的不同，其差異在於 mutable 參考保證沒有任何其它東西並行地改變值，它就是個 exclusive 參考；但 mutable 指標並沒有這種保證，mutable 指標只是具有一定語意的指標，我們稱之為 *mut，它不帶有額外的意義 (保證它是 exclusive )，這就是允許你改變值的原因。

Q : since memory is size aligned in rust, can the compiler fit other "NonNull" variants in (0, 1, 2, 3) for example when the NonNull points to a 4 byte u32?
A : 這個在 unsafe working group 被討論，Jon 認為他們還沒有對此做出裁決。

目前程式碼

src/lib.rs :

pub mod cell;
pub mod refcell;
pub mod rc;

src/rc.rs :

use crate::cell::Cell;
use std::ptr::NonNull;

struct RcInner<T>
{
    value: T,
    refcount: Cell<usize>,
}

pub struct Rc<T>
{
    inner: NonNull<RcInner<T>>,
}

impl<T> Rc<T>
{
    pub fn new(v: T) -> Self
    {
        let inner = Box::new(RcInner {
            value: v,
            refcount: Cell::new(1),
        });
        
        Rc {
            // SAFETY: Box does not give us a null pointers.
            inner: unsafe {NonNull::new_unchecked(Box::into_raw(inner))},
        }
    }
}

impl<T> std::ops::Deref for Rc<T>
{
    type Target = T;
    fn deref(&self) -> &Self::Target 
    {
        // SAFETY: self.inner is a Box that only deallocated when the last Rc goes away
        // we have an Rc, therefore the Box has not been deallocated, so deref is fine.
        &unsafe { self.inner.as_ref() }.value
    }
}

impl<T> Clone for Rc<T>
{
    fn clone(&self) -> Self
    {
        let inner = unsafe { self.inner.as_ref() };
        let c = inner.refcount.get();
        inner.refcount.set( c + 1);
        Rc { inner: self.inner }
    }
}

impl<T> Drop for Rc<T>
{
    fn drop(&mut self)
    {
        let inner = unsafe { self.inner.as_ref() };
        let c = inner.refcount.get();
        if c == 1 {
            // SAFETY: we are the _only_ Rc left, and we are being dropped.
            // therefore, after us, there will be no Rc's, and no references to T.
            drop(inner);
            let _ = unsafe { Box::from_raw(self.inner.as_ptr()) };
        } else {
            // there are other Rcs, so don't drop the Box!
            inner.refcount.set(c - 1)
        }
    }
}

PhantomData and Drop Check

1:31:55

Struct std::marker::PhantomData

use crate::cell::Cell;
+use std::marker::PhantomData;
use std::ptr::NonNull;

struct RcInner<T>
{
    value: T,
    refcount: Cell<usize>,
}

pub struct Rc<T>
{
    inner: NonNull<RcInner<T>>,
+   _marker: PhantomData<RcInner<T>>,
+   // 1. 如果沒有這個成員，Rust 不知道 Rc 擁有 T 的型別，
+   //    Rust 只知道 Rc 擁有指向 T 的指標。
+   // 2. 當 Rc 消失的時候，Rust 不知道 T 也有可能跟著卸除了。
+   // 3. 前兩點重要的原因是因為 T 可能有生命週期，所以 Rust 有一個
+   //    drop check 的機制 - 詳情見補充說明
+   // 結論 : 該成員告訴編譯器，當卸除 Rc 時，RcInner<T> 有可能被卸除了，
+   //       你(編譯器) 應該要去檢查。
}

impl<T> Rc<T>
{
    pub fn new(v: T) -> Self
    {
        let inner = Box::new(RcInner {
            value: v,
            refcount: Cell::new(1),
        });
        
        Rc {
            // SAFETY: Box does not give us a null pointers.
            inner: unsafe {NonNull::new_unchecked(Box::into_raw(inner))}, 
+           _marker: PhantomData,
        }
    }
}
...
impl<T> Clone for Rc<T>
{
    fn clone(&self) -> Self
    {
        let inner = unsafe { self.inner.as_ref() };
        let c = inner.refcount.get();
        inner.refcount.set( c + 1);
+       Rc { inner: self.inner, _marker: PhantomData }
    }
}
...

補充說明 : drop check
非常複雜

...
struct Foo<'a, T: Default> 
{ 
    v: &'a mut T 
}

impl<T: Default> Drop for Foo<'_, T>
{
    fn drop(&mut self)
    {
        std::mem::replace(self.v, T::default());
    }
}

fn main()
{
    // case 1 : `有`寫 drop 函式
    // 卸除值然參考該值，該程式被編譯器拒絕
    let t = String::from("hello");
    let foo = Foo { v: &mut t };
    drop(t);   
    drop(foo); 
    
    
    // case 2 - case 4 之後的 drop 都是 `implicit`
    // case 2 : `沒`寫 drop 函式
    // 當任意的型別要被卸除，編譯器必須假設 
    // "every drop of that type is a use of type and any field it contains"
    let (foo, mut t);
    // t 會先被卸除再來是 foo，因為 Rust 用相反的順序來卸除值。
    //    寫成 (foo, mut t) : `t` does not live long enough
    //    - 卸除錯順序，編譯器抓到
    //    寫成 (mut t, foo) : 編譯成功
    //    - 卸除對順序，編譯器給過
    t = String::from("hello");
    foo = Foo { v: &mut t };
    // 編譯器要能夠抓的到卸除錯誤的先決條件是 :
    //     "編譯器要知道 foo 是 T 的`所有權者`"
    //     "foo 會在 main 函式結束時被卸除"
    
    // case 3 : 沒寫 drop 函式 + 
    //          使用我們的 Rc 且`沒有`加入成員 : 
    //              _marker: PhantomData<RcInner<T>>
    // 編譯器會假設當 Rc 要被卸除時，沒有 foo 被卸除，
    // 因為編譯器不知道 foo 是 T 的 `所有權者`。
    let (foo, mut t);
    t = String::from("hello");
    foo = Rc::new(Foo { v: &mut t });
    // 所以編譯器就`不會`去檢查 `RcInner<Foo>` 的值還在不在。
    // 編譯器 (我的已經編不過了，需查版本更動) 竟然還可以編譯的過，
    // 導致 dangling pointer 可能會發生。
    
    // case 4 : 沒寫 drop 函式 + 
    //          使用我們的 Rc 且`有`加入成員 : 
    //              _marker: PhantomData<RcInner<T>>
    // 編譯器會假設當 Rc 要被卸除時，會去檢查 foo 有沒有被卸除，
    // 即使我們只有用指標指向 RcInner<Foo>。
    // 因為編譯器現在新加的成員而知道 foo 是 v 的所有權者。
    let (foo, mut t);
    t = String::from("hello");
    foo = Rc::new(Foo { v: &mut t });
    // 所以編譯器就`會`去檢查 `RcInner<Foo>` 的值還在不在，
    // 這樣編譯器就可以阻止 dangling pointer 的發生了。

}

目前程式碼

src/lib.rs :

pub mod cell;
pub mod refcell;
pub mod rc;

src/rc.rs :

use crate::cell::Cell;
use std::marker::PhantomData;
use std::ptr::NonNull;

struct RcInner<T>
{
    value: T,
    refcount: Cell<usize>,
}

pub struct Rc<T>
{
    inner: NonNull<RcInner<T>>,
    _marker: PhantomData<RcInner<T>>,
}

impl<T> Rc<T>
{
    pub fn new(v: T) -> Self
    {
        let inner = Box::new(RcInner {
            value: v,
            refcount: Cell::new(1),
        });
        
        Rc {
            // SAFETY: Box does not give us a null pointers.
            inner: unsafe {NonNull::new_unchecked(Box::into_raw(inner))}, 
            _marker: PhantomData,
        }
    }
}

impl<T> std::ops::Deref for Rc<T>
{
    type Target = T;
    fn deref(&self) -> &Self::Target 
    {
        // SAFETY: self.inner is a Box that only deallocated when the last Rc goes away
        // we have an Rc, therefore the Box has not been deallocated, so deref is fine.
        &unsafe { self.inner.as_ref() }.value
    }
}

impl<T> Clone for Rc<T>
{
    fn clone(&self) -> Self
    {
        let inner = unsafe { self.inner.as_ref() };
        let c = inner.refcount.get();
        inner.refcount.set( c + 1);
        Rc { inner: self.inner, _marker: PhantomData }
    }
}

impl<T> Drop for Rc<T>
{
    fn drop(&mut self)
    {
        let inner = unsafe { self.inner.as_ref() };
        let c = inner.refcount.get();
        if c == 1 {
            // SAFETY: we are the _only_ Rc left, and we are being dropped.
            // therefore, after us, there will be no Rc's, and no references to T.
            drop(inner);
            let _ = unsafe { Box::from_raw(self.inner.as_ptr()) };
        } else {
            // there are other Rcs, so don't drop the Box!
            inner.refcount.set(c - 1)
        }
    }
}

GitHub comment
Q : @jonhoo Thanks for your wonderful videos. I have a question about rc: I found I can still use inner and can even set and get inner.value in Rc's Drop, why? I added the example code in // Why? section: Rust Playground Code
A : Ah, yes, that's because I was being silly — drop(inner) doesn't actually do anything when inner is a reference. It doesn't remove it from scope, even though it kind of reads that way. The better way to safe-guard this code would be to intentionally shadow inner with: let inner = ();

Q : @jonhoo 👍 But what I still don't understand is why I can still set and get refcount after Box::from_raw. I thought the heap memory has been freed, so we can't access it. But I can still use it without panic.
A : Ah, that's because freeing memory just makes it available for future allocations, it doesn't actually make the memory inaccessible. The memory is still there, it's just undefined behavior to access it.

Q : Would it be sufficient to have PhantomData<T> instead of PhantomData<InnerRc<T>>?
A : 有一個 Pull Request 的內容是將 <T> -> wrapper<T>，會有這個改變是因為有人可能意外地實作了 :

impl<T> Drop for RcInner<T>

如果有人實作了這個 Drop，然後你的 struct 又是 <T> :

pub struct Rc<T>
{
    inner: NonNull<RcInner<T>>,
    _marker: PhantomData<T>,
}

這樣 Drop for RcInner<T> 就不會被檢查了。

Q : this only needed only when T is not 'static ?
A : 是的，但現在我們希望 Rc 能支援任何類型，所以才需要 PhantomData。

?Sized Briefly

1:44:25

標準函式庫的 Rc 的 T 是 ?Sized (動態長度) :

pub struct Rc<T, A = Global>
where
    A: Allocator,
    T: ?Sized,
{ /* private fields */ }

想要自己實作 Rc 支援 ?Sized 相當不容易，困難點需參照 Trait std::ops::CoerceUnsized

Q : The real question for me, is that should this problem exist in the first place? I'm feeling that if I write the same thing in C it will be clearer and I won't be wasting time in all of these.
A : 你鮮少會在你的程式碼寫像這次實作這麼複雜的東西，之所以那麼複雜是因為我們在實作 Rust 的 low level primitive，這個問題不會出現在你身上。重要的是你可以用 Rust 寫這些限制，但如果是 C 的話，編譯器會假設你是大人了，就不幫你做這些檢查。所以 C 才會在執行時期 crash 發生的頻率會高於 Rust，因為 Rust 都在編譯時期就幫你檢查好了。

Q : what is the difference between !Sized and ?Sized
A : !Sized 表示 not Sized，?Sized 表示它不一定要是 Sized，因為預設所有東西都有 Sized bound。

Thread Safety

1:47:30

• 標準函式庫以及我們的 Cell 皆為 Thread unsafety。
• 標準函式庫以及我們的 RefCell 皆為 Thread unsafety。
  • 我們的 RefCell 可以是 Thread safety，只要將我們的原本的計數器改成 atomic 計數器，但你這麼做的話，通常並不是人們想要的，因為如果你在 borrow 的時候，得到了 None 值，此時如果你需要 Some 值，就因為其他執行緒現在擁有該值，你必須要 busy waiting 直到取得 Some 值，這樣相當不好。
  • Thread safe 版本的 RefCell 通常是使用到 rw lock，borrow/borrow_mut 回傳也會從 Option<Ref<'_, T>>/Option<RefMut<'_, T>> 變成 Ref<'_, T>/RefMut<'_, T>，至於為什麼不是回傳 Option 來避免取到 None 值，是因為 rw lock 會 block 目前的執行緒 borrow/borrow_mut 沒有成功，直到某些條件變數滿足才會 unblock 該執行緒。
  • Mutex 有點像簡化版本的 RefCell，它就只有 borrow_mut，所以你不需要記錄現在有幾個 reader (共享參考)，因為現在就只有某個執行緒能擁有那個值。Mutex 也有 block 的機制，如果你當前無法獲得 lock，則你就會被 block 直到持有 lock 的執行緒釋放 lock。
• 標準函式庫以及我們的 Rc 皆為 Thread unsafety。
  • 標準函式庫的 Thread safe 版本是 Arc。

Q : can you guarantee thread safety acros ffi boundaries? Or is that just, whatever (e.g C code) calls into you needs to uphold some guarantees?
A : 沒有保證。跨越 FFI 邊界的一切本質上都是 unsafe。

Q : Why would you ever prefer Rc over Arc?
A : Rc 開銷較小。atomic 操作的代價很大。

Q : Is there an async RwLock?
A : 現在的 crate 已經支援 : async_rwlock

Copy-on-Write (Cow)

1:54:20

Module std::borrow

std::borrow 有點像智慧指標，來看看標準函式庫的 std::borrow:Cow :

// `Cow` 的命名來自於 copy-on-write
pub enum Cow<'a, B>
where
    B: 'a + ToOwned + ?Sized,
{
    // 1. 只有兩種狀態 : 
    //     粗略地說，如果你有 Cow<T>，
    //     cow 要嘛包含對 T 的參考，要嘛包含 T 本身。
    // 2. 如果想要修改 Cow 內部的值，如果內部的值是共享參考，你不能更動它。
    //    如果你要求寫入權限，但現在是 Borrowed 的狀態，
    //    那它就會 Clone 內部的值，並將它改成 Owned 的狀態。
    Borrowed(&'a B),
    Owned(<B as ToOwned>::Owned),
}

看一下 Cow 的一些實作 :

impl<B> Deref for Cow<'_, B>
where
    B: ToOwned + ?Sized,
    <B as ToOwned>::Owned: Borrow<B>,

如果 COW 本身持有對其他內容的參考，你可以獲得對 COW 的共享參考，它只是通過該參考提供存取權；但如果 COW 擁有其包含的內容，那麼它將向您提供對該內容的 exclusive 參考。

Cow 的使用時機是，如果你的程式大部分時間都是 read，偶爾才需要 write。這常常發生在字串操作，假設你有 escape 函式 :

fn escape(s: &str) -> String
// 一堆記憶體複製，即使你不需要改變 foo 的值
{
    // ' => \'     鮮少出現
    // " => \"     鮮少出現
    // foo => foo  大部分都是這個
}

回傳值改為 Cow 型態 :

fn escape<'a>(s: &'a str) -> Cow<'a, str>
{
    // ' => \'     鮮少出現
    // " => \"     鮮少出現
    // foo => foo  大部分都是這個
    if already_escaped(s) {
        Cow::Borrow(s)
    } else {
        let mut string = s.to_string();
        // do something to string (add \)
        Cow::Owned(string);
    }
}

Q : so why does from_utf8_lossy return Cow but other from_utf etc variants don't?
A : 直接看以下程式碼 :

impl String {
    fn from_utf8_lossy(bytes: &[u8]) -> Cow<'_, str> 
    {
        // 如果給定的位元組字串是完全有效的 utf-8，
        // 那麼你可以直接傳遞它，您可以將其轉換為字串參考，然後將其傳遞。
        if valid_uft8(bytes) {
            Cow::Borrowed(bytes as &str)
        } else {
            let mut bts = Vec::from(bytes);
            for bts {
                // replace with INVALID_CHARACTER utf-8 symbol if not valid utf-8
            }
            Cow::Owned(bts as String)
        }
    }
}

// 其他 `from_utf` 類型通常不顧一切地配置記憶體，
// 如果它們不顧一切地配置記憶體，那麼就沒有理由使用 Cow 類型。

回顧 :

1. cell : non thread safe, non reference, interior mutablity.
2. refcell : dynamic interior mutablity.
3. rc : dynamically shared reference.
4. Cow : kind of smart pointer, upgrade when you need it.

GitHub comment
Q : How come for RefCell and Cell Drop is not implemented but it is for Rc?
A : Because neither RefCell nor Cell need to do anything special on Drop — they just have to drop their inner type, which happens automatically when dropping their inner UnsafeCell.

待整理

1. 搜尋 "我的已經編不過了，需查版本更動"