Rustのメモリ管理方法

# はじめに
　Rust初心者です。今までRustのメモリ管理方法については何となく理解をしたまま放置して書いてしまっていました。最近、脱初心者に向けてメモリ管理方法について改めて理解を深めてみたので書いています。
　はじめにメモリ管理方法の変遷について軽く紹介し、その後Rustのメモリを管理手法について述べます。

# メモリ管理の歴史
　C言語などにおいてはメモリの確保及び解放は手動管理されています。
　`＜メリット＞`
　・高速・効率が良い
　`＜デメリット＞`
　・人間が全部やるのでミスが発生しやすい
　　→ライフタイムを超えて変数へアクセス、メモリリークの発生
　　⇒信頼性が低い
![Qiita_adventcarender2020_Rust.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/896862/0656ab18-9dc8-a318-3c06-a2d030dc1dbd.png)

 メモリ管理が手動であると上記のようなデメリット（人為的ミス）が発生することから自動管理することでメモリリークの発生を未然に防いだり、再アクセスさせる可能性のある領域に対するアクセスが発生しないようにしたりするようになりました。自動管理手法は大きく分けて2つ、smart pointerとGC（garbage collection）になります。

## smart pointer
 　動的に確保したメモリを自動的に解放するポインタのような（Deref、Dropトレイトによりポインタのように振る舞っている）構造体のことです。所有権があり、リソース管理を行うことができるためメモリの解放忘れやメモリリークを防止できます。
　例えばC++のunique_ptrはヒープ領域を所有するようなポインタクラスで、この型変数が所有するヒープ領域は変数がスコープから抜けると自動解放されます。また複数のunique_ptr型変数が同じヒープ領域を所有することはないのでメモリリークは起こらないようになっています。あるいはshared_ptr型は所有権を共有することができ参照カウントを監視することでメモリ解放を実行します。

## garbage collection
　「再アクセスされるメモリを残し、されないものを解放→再利用する」というメモリ管理を自動で行うことです。これにより、リークやライフタイムを過ぎたメモリに対するアクセスに伴うメモリ破壊を防止できます。
　GCの方式はどのようにして再アクセスされるメモリを検出するのかという観点から2つに分類することができます。1つ目の方式が**traversing GC（走査型GC）**、2つ目の方式が**reference counting GC（参照カウントGC）**です。方式の詳細は割愛しますがtrversing GCは**mark & sweep GC**と**copying GC**の2タイプにさらに分類されます。
###GCのここがポイント
①オーバーヘッド
　GCを機能させるためにmutatorに課される処理時間
　※少なければ少ない程良い
②pause time
　GCを機能させるためにmutatorが一時停止する時間
　※少なければ少ない程良い

ここらへんがメモリ管理をプログラマが気にしなくていいため扱いやすいかつ安全だが実行速度的にどうなのよってなる主要因になります。

# Rustにおけるメモリ管理方法
　ここからRustにおけるメモリ管理方法について述べます。
　Rustにおけるメモリ管理方法は手動管理でもなくかと言ってGC方式でもないようです。
　Rustにおいては**所有規則**と**借用規則**という2つの規律により、コーディングがメモリの確保解放を管理しています。また**スマートポインタ**が数種類搭載されており（型が結構色々ある印象です）、部分的に所有規則と借用規則をスルーしたいときにこれらが利用できる仕掛けになっているようです。スマートポインタはオブジェクト同士の相互参照が発生するような場合には利用しないと実装できないです。

##スタック領域＆ヒープ領域
　Rustにおけるメモリ管理でスタック領域とヒープ領域がそれぞれどのような働きを持っているのかについて再確認します。

＜用語復習＞
・スタック領域
＝コンパイラ、OSにより確保される領域で、アロケーションはひとつの関数呼び出しに限定される局所的なものであるためサイズ制限がある
・ヒープ領域
＝メモリ上のどこかに確保される領域でプログラムにより明示的にアロケートされる。事実上サイズ制限はない。広域的アクセスが可能

＜Rustにおける領域の動き方＞
・スタック領域
→基本的な値はスタックに置かれる
　ローカル変数のメモリは一度に確保でき、一度に破棄できる
　ローカルな束縛だけでなく引数にも使われる
・ヒープ領域
→Box\<T>型（スマートポインタの型の一種）を利用するとヒープ領域へのアロケートができる
　一部がデアロケートされると間隙が生じる
　（Box\<T>型にはDropトレイトが実装されている）

## 所有＆借用
　Rustにおける「所有権」「借用」「ライフタイム」について少し触れます。Rustをはじめたてのころは、なんかこの辺りが特殊という理解に留まっていたので、そこの関係性を整理し、また特殊であることがRustにどんなメリットを生んでいるのかポイントが理解できたらと思っています。
### 所有権
`ある変数がその変数に代入された値のメモリ上の値に対してえる権利のこと`
例えばごくシンプルな例として下のようなコードがあるとします。

```rust
fn main() {
    let a = 1;
    let b = a + 2;
}
``` 
このとき変数aはメモリ上の値(1)に対して所有権を持ち、変数bはメモリ上の値(3)に対して所有権を持ちます。
#### 所有規則
ここから所有権についてその規則を見ていきます。
規則１：各値は各所有者と対応する（所有者＝変数）
規則２：所有者は１つでなければならない
規則３：所有者がスコープから外れたとき同時に値は破棄される（＝メモリが解放される）

規則１、３は比較的明解かなと思います。規則２が指すところとしては、途中で値が別の所有者に所有されることを考えたときに、「所有者が複数にならない」あるいは「所有者が誰もいない状態にはならない」と考えるられます。
この規則の目指すところは何か、ポイントにまとめました。

＜ポイント＞
①規則は**多重解放を防止**する
：規則３より変数がスコープを抜けた瞬間にメモリが解放されます。このため多重解放を起こすためには同一変数が2回スコープ抜けなければないということになり、後述するライフタイムの作り方からそれは起こらず、多重解放が起こりません。
②規則は**解放後メモリへのアクセスを防止**する
：メモリが生存できる期間はスコープと等しいためコンパイルした際に確定します。そのため参照がメモリの解放後に起こっているときにはコンパイルが通りません。そのため実行時に解放後メモリにアクセスしてしまい。。ということが発生しません。

### ライフタイム
`所有権の持つ様々な規則を強制するための概念`
ライフタイムは所有権の持つ様々な規則を強制するための概念と定義付けられますが要するにプログラム中のスコープ名のことであると理解できると思います。似たような名前にliveness（生存性）がありますが、これとライフタイムは異なる概念です。
※生存性は参照を参照外しできるかどうかのような文脈で扱われる概念です。

ライフタイムについてざっくりまとめると、
・let文は非明示的にスコープを導入する（推論してくれる）
・関数本体では関係するライフタイム名は非明示で良い
・関数本体から出たらライフタイムのことを気にしないといけない
・参照及び参照を含むものは有効なスコープをしめすライフタイムでタグ付けされている
・省略にはルールがあるので守らないと怒られる

ライフタイムは'hogeというように「'」がついた名前をもちます。ライフタイムを理解するにはやはりdesugarが分かりやすいと思ったのでここではdesugerしてライフタイムを解説します。
例えば以下に示すようなシンプルなコードをdesugarすると、

```rust
fn main() {
    let a = 1;
    let b = &a;
}
```

```rust
's: {
   let a: i32 = 1;
   't: {
       let b: &'t i32 = &'t a;
       }
}
```
このようになります。's、'tがライフタイム名になります。
### 借用
`関数の引数に参照をとること`
借用をざっくりまとめると、
・借りているだけなので変更はできない（可変参照をすれば変更できる）
・ダングリングポインタはコンパイルエラー
・構造体を分割して別々のフィールドを同時に借用することは可能
・配列を分割して借用することはできない

借用にも所有同様に規則があります。この規則のポイントは**データ競合が起こるような参照関係を発生させない**というところです。すなわち全参照が借用規則に従う必要があります。
#### 借用規則
規則１：不変参照は同一所有者に対し複数定義が可能
規則２：可変参照は同一所有者に対して単数定義のみ可能
規則３：可変参照と不変参照は同時に定義不可能
規則４：参照変数の参照は可能

借用規則（＆所有権規則）によって安全性が保障されているなあというところが理解できるかと思います。

## スマートポインタ
最後に搭載されているRustのスマートポインタを見ていこうと思います。種類が豊富なので特徴を掴んで適切なスマートポインタを実装できるようになりたいという気持ちで理解を進めました。
### Box\<T>
＜特徴＞
・一番スタンダードなスマートポインタ
・ヒープ領域に対して単一所有権を持つ（共有はできないが変更可能）
・ライフタイム＝短い
最もシンプルなBox\<T>へのデータ格納コードを下に示します。

```rust
fn main(){
   let a = Box::new(10);
   println!("{}", a);
}
```
例えばこのコードを

```rust
fn main(){
    let a = Box::new(10)
    let b = a.clone();
    let c = b + 2;
}
```
のように書き換えるとこれは変更をしようとしているのでコンパイルエラーになります。
### Rc\<T>
＜特徴＞
・同一ヒープ領域の複数所有権を可能にする＝**所有規則をスルー**できる
・参照カウント型
・所有領域の値の変更は不可能
・ライフタイム＝'static
ここでは参照カウントがどのように動いているかを見るコードを書いてみます。

```rust
use std::rc::Rc;

fn main() {
    let a = Rc::new(10);
　　assert_eq!(Rc::strong_count(&a), 1);

    let b = a.clone();
    assert_eq!(Rc::strong_count(&b), 2);

    assert!(Rc::ptr_eq(&a, &b));
    eprintln!("a = {0:p}", a);
    eprintln!("b = {0:p}", b);
}
```
実行すると以下のような結果が得られa,bがともに同じポインタを指していることがわかります。

```
a = 0x10c95e6ba10
b = 0x10c95e6ba10
```
続いて「複数所有を可能」を少し掘り下げます。同じように複数所有権が可能で変更が不可能な型に**Arc\<T>**があります。違いは「スレッド間でも共有できるかどうか」です。試しに以下のようにスレッド共有しようとするとRc型ではコンパイルが通りません。

```rust
use std::rc::Rc;
use std::thread;

fn main() {
   let a = Rc::new(10);
   let b = thread::spawn(move || {
       println!("{}",a)
   });
   b.join().unwrap();
}
```
ここで`use std::rc::Rc`を`use std::sync::Arc`とし`Rc::new(10)`を`Arc::new(10)`とすればこのコードは私が意図したように動きます。

### Refcell\<T>
＜特徴＞
・ヒープ領域に対して単一所有権を持つ
・内部可変性を持つ（\*）＝**借用規則をスルー**できる
・ライフタイム＝短い

⋆特徴の内部可変性を持つとは、つまりRefcell自体が可変か不変かに依存せずに中の値を書き換えられるということです。このため**借用規則は実行時に強制**されます（コンパイルの時ではない）

Refcellを利用した簡単な例を示します。これは実行可能で、複数の不変借用が同時に実行可能になっていることがわかるかと思います。

```rust
use std::cell::RefCell;

fn main() {
    let a = RefCell::new(10);
    {
        let m = a.borrow_mut();
        assert!(a.try_borrow().is_err());
        println!("{}", m);
    }
    
    {
        let m = a.borrow();
        assert!(a.try_borrow().is_ok());
        println!("{}", m);
    }
}
```
ここで`let n = m + 2 ;`のようなことをしようとするとコンパイルできません。

### Rc\<RefCell\<T>>
＜特徴＞
・同一ヒープ領域の複数所有権×内部可変性＝同一ヒープ領域に対して複数所有者が変更権限を持てるようになる（共有可能かつ変更可能）
・ライフタイム＝'static

### Arc\<T>
＜特徴＞
・共有可能でスレッド共有も可能だが変更不可能
・ライフタイム＝'static

先ほどRc\<T>を紹介した際に大体書いてしまいましたが、改めて。スレッドでの共有方法は紹介したのでここではスレッド間で可変データを共有するシンプルな実装に触れます。

```rust
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::thread;

fn main(){
    let a = Arc::new(AtomicUsize::new(10));

    for _ in 0..20 {
        let a = Arc::clone(&a);

        thread::spawn(move || {
            let b = a.fetch_add(1, Ordering::SeqCst);
            println!("{:?}", b);
        });
    }
}
```
実行結果は以下のようになります。

```
10
11
14
16
18
19
13
22
12
25
20
21
29
23
```
### Arc\<Mutex\<T>>
＜特徴＞
・共有可能かつ変更可能
・ライフタイム＝'static

### Cell\<T>
＜特徴＞
・ロック用の領域を省くことが可能
・ヒープ領域に対して単一所有権を持つ
・内部可変性
・操作が限定的
・T=Copyであるとき効果あり

### Week\<T>
＜特徴＞
・同一ヒープ領域の複数所有権を可能にする
・参照カウントはメモリ領域の解放に関与しない（弱参照）
　→RcやArcでは**循環参照**が回収できないのでそんなときはこれを使う
　⇒Rc\<T>に対応するものが`std::rc::Weak`、
　　Arc\<T>に対応するものが`std::sync::Weak`
ここではRc\<T>における簡単なWeakの実装を考えます。Weakを使うことでaがcを弱参照できていることが分かるかと思います。また状態の共有が必要になるのでRefCellが登場しています。さらに強参照に昇格することも可能のようです。

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

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

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

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

    let c = Rc::new(Node {
        value: 12,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![Rc::clone(&a)]),
    });

    *a.parent.borrow_mut() = Rc::downgrade(&c);

    println!("{:?}", a.parent.borrow().upgrade());
}
```
実行結果

```
None
Some(Node { value: 12, parent: RefCell { value: (Weak) }, children: RefCell { value: [Node { value: 10, parent: RefCell { value: (Weak) }, children: RefCell { value: [] } }] } })
```
`upgrade()`を使用してaの親に対して参照を得ようとしたときNoneになっていることが確認できました。

ほかにもいくつかスマートポインターの種類があることは把握しているのですが筆者の理解が追い付いていないためここでは紹介いたしません（できません）。。

# おわりに
「Rustらしさ」の根幹を理解しにいくことで、Rustの威力を最大限引き出せるような実装ができる日はまだ遠そうですが、その第一歩が踏み出せていれば良いなあと思っています。
借用規則を学習していたときにこれって双方向連結リストとかどうやって解決するんだろうと思って調べたらすでに [標準ライブラリ](https://doc.rust-lang.org/std/collections/struct.LinkedList.html) にありました。まだ未攻略なので使ってみたいです。

いろいろと勉強不足な点があるかと思いますので間違えなどありましたらご指摘頂ければ幸いです。
# 参考文献
1. https://doc.rust-jp.rs/trpl-ja-pdf/a4.pdf
 <br>（Rustドキュメント：メモリ領域にて参照）
2. https://doc.rust-lang.org/book/2018-edition/ch04-00-understanding-ownership.html
<br>（Rustドキュメント：所有＆借用にて参照）
3. https://doc.rust-jp.rs/book-ja/ch15-00-smart-pointers.html
<br>（Rustドキュメント：スマートポインタにて参照）
4. 日経BR出版、増田智明著「Rust入門」（2020年）