Rustで単方向リストを実装する(Enum+Rc版)

## 概要
Rustの仕様理解のために、単方向リストを実装してみた。
今回は Enum(Tuple) + Rc版になります。

これまでは、作成してみたものは次のものがありますが、Rc\<RefCell> 版 に登場する Option に相当する None というか Nullableな値を自前で実装するとどういう工夫が必要かが透けて見えます。

* [Rustで単方向リストを実装する(Box版)](https://qiita.com/syuuu/items/e1379427e4d84b046b83)
* [Rustで単方向リストを実装する(Rc<RefCell>版)](https://qiita.com/syuuu/items/db75947e979444b39c01)
* [Rustで単方向リストを実装する(unsafe版)](https://qiita.com/syuuu/items/562a2c07457ace707477)

### 環境

* rustc 1.58.0 (Rust 2021)
* WSL1 (Ubuntu 18.04 LTS)

## Enum(Tuple) + Rc版の特徴

* 先頭ノードを指す構造体と各ノードを指す構造体をひとまとめにできる
* Option型相当の処理を部分的に実装しなければならず、面倒な気分になる
  * match構文で値の取り出しが必要で、変数へのアクセスが面倒
* new()などの初期化は、struct と少し書き方が異なる
* 今回は RefCell を使っていないので、置換は `Rc` に頼っています (通常は素直に RefCell を使ったほうが良いでしょう)

## コードの概要

今回は次のメソッドを対象にしています。書いてみた試行錯誤の段階での難易度はこうです。(試行錯誤の過程でコードは短くなっているので、きっと簡単に見えると思います。なお、RcはBoxより組みやすいです。)

なお、難易度は Enum が…というよりは、 `Rc<RefCell<_>>` でなく `Rc<_>` としたことに起因します。
コード量の多さは主に Enum の値の参照や取り出しにくさが原因です。

| method     | 難易度           |
|------------|-----------------|
| push_front | ★ (とても簡単)
| push_back  | ★★★
| pop_front  | ★★
| pop_back   | ★★★★ (とても難しい)

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

pub enum SList<T> {
    Cons(T, Rc<SList<T>>),
    Nil,
}

impl<T> SList<T> {
    pub fn push_back(&mut self, v: T) {}
    pub fn push_front(&mut self, v: T) {}
}

impl<T: Clone> SList<T> {
    pub fn pop_back(&mut self) -> Option<T> { None }
    pub fn pop_front(&mut self) -> Option<T> { None }
}

impl<T> From<T> for SList<T> {
    fn from(v: T) -> Self {}
}

impl<T> Default for SList<T> {
    fn default() -> Self {}
}
```

### 初期化
一番簡単です。ここでは Default トレイトと Fromトレイトで実装しています。

```rust
impl<T> From<T> for SList<T> {
    fn from(v: T) -> Self {
        SList::Cons(v, Rc::new(SList::Nil))
    }
}

impl<T> Default for SList<T> {
    fn default() -> Self { SList::Nil }
}
```

### push_front()

一番簡単なメソッドです。
Enum 自体は replace で置換するしかないですね。

1. replace で 先頭ノードの中身を吐き出させる
2. 新しい先頭ノードの次ノードにもともとのヘッドノードの内容を付け加える

```rust
    pub fn push_front(&mut self, v: T) {
        let head_node: SList<T>;
        head_node = std::mem::replace(self, SList::Nil);

        let _ = std::mem::replace(
            self, SList::Cons(v, Rc::new(head_node))
        );
    }
```

リファクタリング

`SList::new` を実装することで `Rc::new()` の内部構造を隠ぺいできます。
これにより `pub enum SList<T> { Cons(T, Box<SList<T>>), Nil }` など Rc → Box などに変更したときに、再利用できるコードが増えます。

```rust
    pub fn new(v: T, next: SList<T>) -> Self {
        SList::Cons(v, Rc::new(next))
    }

    pub fn push_front(&mut self, v: T) {
        let head_node: SList<T>;
        head_node = std::mem::replace(self, SList::Nil);

        let _ = std::mem::replace(self, SList::new(v, head_node));
    }
```

### push_back()

まず、ループをどう回すかでかなり悩みました。
幸いなことに Rc の場合は `Rc::get_mut` で辛うじてループを回せることに気づいて、実現できました。

`Rc::get_mut` は、参照カウント・弱カウントがゼロの場合のみ使えるとても制約の強いものです。`Rc<RefCll>` 版で多用していた `Rc::clone()` は今回は使えません。引数の `&mut` が論理に大きな影響を与えます。`RefCell` を使ったほうがよほど楽。

* 最初のmatchブロックは、どのメソッドでも大抵必要になります。self が `SList::Nil` かそれ以外なのかを判別することから始まります  
  Enum版の興味深いところはここですね。自分自身が `Nil` という状態を作れます。
* 後半のループは `Rc::get_mut()` で `&mut Rc<_>` を得て制御しています。
  * `Slist::Nil` のルートを break して外だししようとしたら、書き込みで借用している関係でコンパイルはできませんでした (これ以外の書き方が難しいという意味でかなり巧妙なコードです)

```rust
    pub fn push_back(&mut self, v: T) {
        let mut cur_rc_ref = match self {
            SList::Nil => {
                let _ = std::mem::replace(
                    self, SList::Cons(v, Rc::new(SList::Nil)) 
                );
                return;
            },
            SList::Cons(_, next_rc_ref) => next_rc_ref,
        };

        while let Some(node_ref) = Rc::get_mut(cur_rc_ref) {
            cur_rc_ref = match node_ref {
                SList::Cons(_, next_rc_ref) => next_rc_ref,
                SList::Nil => {
                    *node_ref = SList::Cons(v, Rc::new(SList::Nil));
                    return;
                },
            };
        }
    }
```

追記: リファクタリング

RefCellを使っていない関係で、更新手段が乏しく `Rc::get_mut()` に頼るため、Boxのような占有状態の制御となり、このケースにおいてはRcをループ変数とするメリットがありません。ループ変数を `&mut Rc<SList<T>>` から `&mut SList<T>` とするほうが都合が良いです。

こうすることで、 self とループ変数の型が一緒になるので、先頭部分とそれ以降の処理を別々とする必要がなくなります。あと、実は `Rc::get_mut` は next の変数に対して適用すればよく、書き直したコードは次のようになります。

```rust
    pub fn push_back(&mut self, v: T) {
        let mut cur_rc_ref_mut = self;

        while let SList::Cons(_, next_rc_ref_mut) = cur_rc_ref_mut {
            cur_rc_ref_mut = Rc::get_mut(next_rc_ref_mut).unwrap();
        }

        let _ = std::mem::replace(cur_rc_ref_mut, SList::from(v));
    }
```


### pop_front()

今回は Clone を必要としてます。replaceをうまく使えば不要にできるかもしれません。

* 最初の match は先頭の次ノードを指す Rcの参照を返却します
* 後半
     * Rc::get_mut()` で replaceの要求する `&mut` を指定できるので、self の参照をなくしています
     * その次に head 自体をもともとの次ノードで置換します
     * 最後の replace の復帰値に先頭ノードの値も入っているのですが、match 構文を使わないと value が取り出せないので、最初の match 構文中で value の取り出しをしています。


```rust
impl<T: Clone> SList<T> {
    pub fn pop_front(&mut self) -> Option<T> {
        let some_value: Option<T>;

        let head_rc_ref: &mut Rc<_> = match self {
            SList::Nil => return None,
            SList::Cons(v_ref, head_rc_ref) => {
                some_value = Some(v_ref.clone());
                head_rc_ref
            },
        };

        let head_node: SList<T>;
        head_node = std::mem::replace(
            Rc::get_mut(head_rc_ref).unwrap(), SList::Nil
        );
        let _ = std::mem::replace(self, head_node);
        some_value
    }
}
```

### pop_back()

難しすぎて挫折しそうになったものです。
初期のコードから1/3ぐらいにスリム化しています。相当巧妙だと思います。

単方向リストにて素朴な実装をすると、prev ポインターと next ポインターを用いて、next が NULL終端の時に prev->next のポインターを書き換える操作をします。同じことをしようとすると、今回は mut で排他的に操作しているのでコンパイルすらできません。
そのため、ポインターの先読みをして一つ前の prev ノードの判定を行います。
この判定自体を排他的に行ってしまうと、あとの replace のときに借用で怒られるので、メソッドチェーンで1行で収まるように判定を加えています。何気に関数を使わず match や if でその場でロジックを書くと比較的はまります。

そのため、次の方針を取ると良いことが分かってきます。

* cur, next と複数ポインターを扱うのを諦める
* ループ変数は prev (一つ前のNull終端のポインター)を用いる
* while let は借用の影響範囲が大きいので loop を使い局所的に借用する

そのほか、雑多な話

* loop では復帰値を渡せるので、ループは変数の所有権を渡してやることで、コードの可読性を高められる
* `unwrap_or`  
  別に使わなくても良いのですが、これを使うことで if ブロックを1行にかけました。
  `next_ref()` で None が流れて来たときに None -> false の変換ができます。正常時は Some(true) -> true です。
* `Rc::get_mut(prev_rc_ref)?.next_ref_mut()?` は unwrap できないときに retrun してくれるのでコードを短くするのに役立ちました

```rust
impl<T: Clone> SList<T> {
    pub fn pop_back(&mut self) -> Option<T> {
        let get_value = |n: SList<T>| {
            match n {
                SList::Nil => None,
                SList::Cons(v_ref, _) => Some(v_ref.clone()),
            }
        };
        let mut prev_rc_ref = match self {
            SList::Nil => return None,
            SList::Cons(_v_ref, next_rc_ref) => {
                if next_rc_ref.is_nil() {
                    // SList(x) -> SList(Nil)
                    // v
                    // SList(Nil)
                    return get_value(
                        std::mem::replace(self, SList::Nil)
                    );
                }
                next_rc_ref
            }
        };

        let tail_prev_rc_ref = loop {
            let is_prev_tail: bool = prev_rc_ref.next_ref().map(
                |next_ref| next_ref.is_nil()
            ).unwrap_or(false);
            if is_prev_tail { break prev_rc_ref }

            prev_rc_ref = Rc::get_mut(prev_rc_ref)?.next_ref_mut()?;
        };

        let tail_node: SList<T> = std::mem::replace(
            Rc::get_mut(tail_prev_rc_ref).unwrap(), SList::Nil
        );
        return get_value(tail_node)
    }
}

impl<T> SList<T> {
    fn is_nil(&self) -> bool {
        match self {
            SList::Nil => true,
            _ => false,
        }
    }

    fn next_ref(&self) -> Option<&Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }

    fn next_ref_mut(&mut self) -> Option<&mut Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }
}
```


## コード全体

```rust
use std::fmt::{Debug, Formatter, Result};
use std::rc::Rc;

pub enum SList<T> {
    Cons(T, Rc<SList<T>>),
    Nil,
}

impl<T> SList<T> {
    pub fn new(v: T, next: SList<T>) -> Self {
        SList::Cons(v, Rc::new(next))
    }

    fn is_nil(&self) -> bool {
        matches!(self, SList::Nil)
    }

    fn next_ref(&self) -> Option<&Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }

    fn next_ref_mut(&mut self) -> Option<&mut Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// list.push_back(3);
    /// assert_eq!(
    ///     format!("{:?}", &list).as_str(),
    ///     "SList(1) -> SList(2) -> SList(3) -> SList(Nil)"
    /// );
    /// ```
    pub fn push_back(&mut self, v: T) {
        let mut cur_slist_ref_mut = self;

        while let SList::Cons(_, next_rc_ref_mut) = cur_slist_ref_mut {
            // &mut SList<T> <- &mut Rc<SList<T>>
            cur_slist_ref_mut = Rc::get_mut(next_rc_ref_mut).unwrap();
        }

        let _ = std::mem::replace(cur_slist_ref_mut, SList::from(v));
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_front(1);
    /// list.push_front(2);
    /// list.push_front(3);
    /// assert_eq!(
    ///     format!("{:?}", &list).as_str(),
    ///     "SList(3) -> SList(2) -> SList(1) -> SList(Nil)"
    /// );
    /// ```
    pub fn push_front(&mut self, v: T) {
        let head_node: SList<T>;
        head_node = std::mem::replace(self, SList::Nil);

        let _ = std::mem::replace(self, SList::new(v, head_node));
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_back(), Some(2));
    /// assert_eq!(list.pop_back(), Some(1));
    /// assert_eq!(list.pop_back(), None);
    /// ```
    pub fn pop_back(&mut self) -> Option<T> {
        let get_value = |n: SList<T>| {
            match n {
                SList::Nil => None,
                SList::Cons(v_ref, _) => Some(v_ref),
            }
        };
        let mut prev_rc_ref = match self {
            SList::Nil => return None,
            SList::Cons(_v_ref, next_rc_ref) => {
                if next_rc_ref.is_nil() {
                    // SList(x) -> SList(Nil)
                    // v
                    // SList(Nil)
                    return get_value(
                        std::mem::replace(self, SList::Nil)
                    );
                }
                next_rc_ref
            }
        };

        let tail_prev_rc_ref = loop {
            let is_prev_tail: bool = prev_rc_ref.next_ref().map(
                |next_ref| next_ref.is_nil()
            ).unwrap_or(false);
            if is_prev_tail { break prev_rc_ref }

            prev_rc_ref = Rc::get_mut(prev_rc_ref)?.next_ref_mut()?;
        };

        let tail_node: SList<T> = std::mem::replace(
            Rc::get_mut(tail_prev_rc_ref).unwrap(), SList::Nil
        );
        get_value(tail_node)
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_front(), Some(1));
    /// assert_eq!(list.pop_front(), Some(2));
    /// assert_eq!(list.pop_front(), None);
    /// ```
    pub fn pop_front(&mut self) -> Option<T> {
        let head_rc_ref = self.next_ref_mut()?;

        let head_node: SList<T>;
        head_node = std::mem::replace(
            Rc::get_mut(head_rc_ref).unwrap(), SList::Nil
        );
        let head_node_old = std::mem::replace(self, head_node);
        match head_node_old {
            SList::Nil => None,
            SList::Cons(v_ref, _) => Some(v_ref)
        }
    }
}

impl<T> From<T> for SList<T> {
    fn from(v: T) -> Self { SList::new(v, SList::Nil) }
}

impl<T> Default for SList<T> {
    fn default() -> Self { SList::Nil }
}

impl<T: Debug> Debug for SList<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        if let SList::Cons(v, n) = self {
            write!(f, "SList({v:?}) -> {n:?}")
        } else {
            write!(f, "SList(Nil)")
        }
    }
}

#[cfg(test)]
mod tests;
```

## まとめ

全体的にコード量は増えますが、値を取り出す関数を追加していくと主要な論理は Struct と同等かそれより短くなります。

* Enum は構造体に None 相当を組み込めることは利点となる (ただし大きい構造体の埋め込みは注意)
* Option型はで済むならそっちを使ったほうが良い
  * Option型にあるようなメソッドを自作をする手間は増えるため
  * Option型には非常に多くの機能があって便利だということに気づく
* Struct でなく Enum を使うと値の取り出しに if let / while let / match 構文が必要
  * if let / while let / match では可変借用などの影響が及ぶこともあり、悩ましい状況に遭遇しやすくなる (mut用メソッドと Imutable用メソッドを使い分ける必要に駆られる)
* 今回は、おそらく `Rc<RefCell<_>>` としていたなら苦労が少なかったはず  
  どこかのサンプルが Rc だったのでそれに従って、どこまでできるのかを試す意図もあった