淺談rust option type

強者我同學qcl 做了一系列的簽名檔，大體的概念就是用女友狂炸執行緒，以下是C++ version：

int main(int argc, char *argv[]) {
  QCL *qcl = new QCL();
  Girl *gf = qcl->findGirlfriend();
  printf(“%s\n”, gf→name());
  return 0;
}
qcl@QCLS:~$ g++ qcl.cc
qcl@QCLS:~$ ./a.out
Segmentation fault

另外還有許多版本：python, java, objective C(太強啦都會寫objective C)等等
最近心血來潮寫了一個rust version ，發現正好可以藉此說明option type 的概念，這樣的設計見諸於一些較新的語言，和較舊語言的新標準，如java ver 8和C++，rust 版本如下：

fn main() {
  let qcl = QCL{};
  let gf = qcl.findGirlfriend();
  println!(“{}”, gf.unwrap().name());
}
qcl@QCLS:~$ rustc qcl.rs
qcl@QCLS:~$ ./qcl
thread '<main>' panicked

上面的code 裡，QCL struct 的 findGirlfriend()的宣告如下，它回傳的不是如C++中的Girl，而是Option<Girl>：

fn findGirlfriend(&self) -> Option<Girl>

所謂option type 是用在函式回傳值可能不會回傳東西的時候，包含了兩種可能的變體：Some或None，其基本定義：

pub enum Option<T> {
  None,
  Some(T),
}

例如文中出現的getGirlfriend，亦或在dictionary 查詢的getValue()
若是some 則可存取其中的內容；None 則類似null 的設計，如上例中用unwrap()強行取用內容會造成執行緒崩潰

在上例中，遇到option，比較正規的寫法應該是：

match gf {
  Some(girl) => println!("{}", girl.name()),
  None => println!("Not found"),
}

藉此迴避None 把thread 給炸了，直接unwrap相對在C/C++ version 就是沒去比較return 的pointer == NULL或在python 裡面沒寫 is None，亦或是Golang 裡面沒寫err != nil。

的確，加上match去辨識回傳值是否為None，就跟用了== NULL或is None看似相差無幾，但這裡有個至關緊要的差異，option type 就是option type ，None 只會出現在這裡，若girlfriend 回傳值不是option ，就一定要回傳一個Girl 的實體，不管存取它的name 之後是<林志玲>還是<qcl的右手>，它就必須是一個Girl，儘管解出來是<qcl的右手>它仍然夠格當一位適當的女友。

在其他語言中的Null則不然，我們看到C++ 回傳了一個Null pointer，Null 是空的東西，它什麼都不是；但他被視為Girl pointer，因此我們可以存取它的name，它可以被賦值給任何一種pointer，它又什麼都是，Null 如同變形蟲一樣通過對Girl 的型別檢查，這樣簡單的例外設計有極高的自由，卻也容易出錯。

使用option 讓設計師知道girlfriend有可能為None，也無法對option type 使用來自Girl 的函式與資料，編譯器能在編譯時清楚的指出這類錯誤，並強制設計師在編寫時使用match 檢查，從而避免None 在執行緒中四處散佈，並到了執行時才將執行緒炸掉，如上文中都已經知道可能是None了，又強行unwrap 程式會爆是自己活該。

如果我們用上面的例子寫個比喻：
C語言和允許Null 的語言大概就像：你女友的名字呀，拿去；噢qcl你沒女友呀…干我屁事！你還是自盡吧你
使用Option 的語言會比較貼心一點：女友的名字嗎，嘿qcl 呀，你有可能沒有女友噢，最好處理一下

有關rust 裡option 的相關文件：
https://doc.rust-lang.org/std/option/
https://en.wikipedia.org/wiki/Option_type

關於Null 的一些延伸閱讀：
https://linux.cn/article-6503-1.html
http://openhome.cc/Gossip/Programmer/Null.html

Minecraft 可堆疊式物品儲存系統

Minecraft 因為遊戲時間一久，玩家通常會累積大量物品，另外如果利用生怪磚建造農場，或者之前出現過的巨大化農場，大量物品儲存系統算是相當重要。

簡單的儲存系統要利用漏斗和箱子即可，如下圖所示的垂直儲存系統設計：


這樣的設計在擴展性方便較差，要更多箱子就要往下延伸，通常在建築物裡面要打掉樓板比較不適合。

水平的儲存系統可利用長條漏斗，連接到一般箱子和陷阱箱子交錯放置的箱子列中，如下圖所示：



上面兩種設計共有問題在於：漏斗中都會殘留儲存的物品，很難確定現在究竟儲存了多少東西，另外，漏斗就是要傳送物品的，東西就應該要放在箱子裡面怎麼能殘留在漏斗中呢？

本文展示一種新型的儲存系統設計，能避免物品殘留在漏斗中：

基本架構如下，儲存同樣是用箱子列和側面的進貨漏斗，不一樣的是進貨漏斗上加上一層控制漏斗，最上面才是物品傳送鏈。

透過比較器感測進貨漏斗那是否有物品，一但有物品將會將控制漏斗關閉，使控制漏斗不會再進貨， 儲存箱滿了，漏斗中頂多殘留一個物品，確保物品都儲存在箱子中。

以下為建造說明影片：

使用Rust 實作regular expression tester

其實這個功能很早以前就已經完成了，將正規表示式對轉換成Non-Deterministic Automata(NFA) ，來match字串，
先前的實作有一些問題，因為再建 NFA的時候，狀態是使用整數來表示，在轉換成NFA時，正規表示式的Concatenate, Choose, Repeat 需要將兩個NFA 結合成一個，因為由Empty 或Literal 直接建NFA時，編號一定是從0開始，兩個都包含狀態０的狀態機，直接結合起來絕對不會是對的，需要讓兩邊的狀態都不一樣才行。
當然也不可能用亂數來作為狀態，畢竟以亂數作為狀態，連一個NFA裡面有哪些狀態都不知道，結合時根本就無法檢查是否有衝突。

這是之前版本的 toNFA：
toNFA with u32

可以看到因為使用整數來表示狀態，為了避免第二個NFA 接到第一個上面時，第二個NFA 的狀態和第一個的重複，必須實作一些必要的函式，例如FARule 的shift 將規則中的狀態都偏移一個數值；如果像Choose 或Repeat ，需要建一個新的start state，則兩個 NFA的 rule都要shift；另外像accept state也要用iterator的方式 shift，總之就是各種麻煩。

相對的在書中的例子，使用Ruby實作的關係，他直接使用Ruby Object來當作他的狀態，絕對不會有重複的問題，就像這裡的start_state：

class Choose
  def to_nfa_design
    first_nfa_design = first.to_nfa_design
    second_nfa_design = second.to_nfa_design
    start_state = Object.new
    accept_states = first_nfa_design.accept_states + second_nfa_design.accept_states
    rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
    extra_rules = [first_nfa_design, second_nfa_design].map { |nfa_design|
      FARule.new(start_state, nil, nfa_design.start_state)
    }
    rulebook = NFARulebook.new(rules + extra_rules)
    NFADesign.new(start_state, accept_states, rulebook)
  end
end

當然Rust 也是可以這樣做，只是麻煩些，畢竟Ruby 是動態語言，要用什麼東西當狀態都可以直接使用，Rust 需要明確的指定型別，某種程度它用Ruby 實作也是一種語言的霸凌Orz。

相對應的修改如下：
首先我們先建一個空的state，裡面不用內容，功用就跟Ruby 的Object 差不多：

Struct State;

這樣就可以建state了：

let start_state = State{};
let next_state = State{};
let rule = FARule(start_state, c, next_state);
NFA(start_state, next_state, rule);

因為Rust 在struct 的比較的時候，會直接把struct 拆開比較裡面的值，所以上面 start_state == next_state 會是true，解決方法在於自己實做比較的方法，改成比較struct 的位址即可避免不同struct 被認定成相同：

impl PartialEq for State {
  fn eq(&self, rhs: &Self) -> bool {
    self as *const _ == rhs as *const _
  }
}

另外 Rust 會避免同個struct 被兩個不同的地方擁有，當我們使用了某個State當作start_state，我的rule 就沒辦法再用這個State 了，上面的code 在建nfa 的時候會報錯，因為start_state 跟next_state 已經move 到FARule 中了。 因此我們狀態不能直接使用state 而必須用rust 的 Reference Count: Rc。
https://doc.rust-lang.org/std/rc/struct.Rc.html
用Rc<State> 當作state，這樣

let start_state = Rc::new(State{});
let next_state = Rc::new(State{});
let rule = FARule(start_state.clone(), c, next_state.clone());

就可以避免重複使用start_state 的問題，同時 start_state == start_state.clone() 也會是true。

以下是修改後的toNFA：
toNFA with struct state
相較起來簡單的多，也跟Ruby code 相似得多。