給 C++ 使用者的 Rust 簡介：參考型別與 Borrow Checker (1)

,

大多數的程式語言，為了有效率地傳遞、修改物件內容，會提供指標或參考型別 (reference type)。若某個變數是參考型別，意味著它並不直接儲存物件的內容，而是儲存記憶體位址，該位址指向的記憶體區塊才是真正儲存物件內容的地方。

除了快速傳遞大型物件外，參考型別也在一些語言功能上扮演重要角色，比如說：

  • 表達像是 linked list 這樣的遞迴類別 (recursive data type)。
  • 在 OOP 中操作抽象物件時，由於具體型別未知，因此必需用「指向某抽象型別的參考」來進行操作。
  • 利用 copy on write 或是 flyweight 之類的共享資料節構減少記憶體浪費並提高執行效率。

作為追求執行效率的系統程式語言，Rust 也提供了參考型別，但是為了達成 memory safe 的目標，Rust 加上了一層嚴格的保護：borrow checker，讓它有著異常陡峭的學習曲線。本系列文章會試著從 borrow checker 的設計目標開始，解釋參考型別帶來的潛在危險，以及 borrow checker 如何幫我們檔下這些錯誤。

基本語法

Rust 中的參考型別就直接稱呼為參考 (reference)。雖然 C++ 也有參考，但 Rust 的參考在使用上其實比較接近 C++ 的指標 (pointer)。

1
2
3
4
5
6
fn main()
{
    let a: i32 = 10;
    let pa: &i32 = &a; // 相當於 int* pa = &a;
    println!("pa points to value {}", *pa);
}

取得物件位址的方法，是使用 & 運算子，這點與 C++ 是相同的。另一個相同的地方是 * 運算子同樣表達解參考 (deference)，可以從位址取得目標物件的值。不同的地方則在於指標型別的表示法：在 C++ 中會以 T* 來表示「指向 T 型別的指標」，但在 Rust 中的表示方法則是 &T。

相似之處到此為止。為了同時達到執行效率與安全的要求，Rust 對參考型別的設計和主流語言有非常大的差異。

Null Pointer

C++、Java 與 C# 都提供 null pointer，允許指標或參考不指向任何物件。然而一旦引入了 null，那麼操作任何參考型別之前，就必需檢查它是否為 null，否則會造成存取錯誤。Java 與 C# 是 memory safe 的語言，它們會犧牲一點執行效率，在存取物件成員的時候自動檢查物件參考是否為 null。而 C++ 則讓程式設計師自行選擇：你可以像 Java 與 C# 那樣犧牲一點效率來保證安全，或是冒著 undefined behavior 的風險略過檢查以追求效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
struct Foo {
    int data;
};
int main()
{
    Foo* obj = nullptr;
    // 在 C# 或 Java 中，compiler 會在存取成員之前檢查參考是否為 null
    // 因此相同的情況會丟出 NullPointerException
    cout << obj->data << endl; // undefined behavior
    return 0;
}

Rust 沒有 null pointer。在你拿一個合法物件的位址來初始化指標之前，任何操作指標的行為都會被編譯器阻止。

1
2
3
4
5
6
7
8
9
10
fn foo(ptr: &i32)
{}
fn main()
{
    let pa: &i32;
    let val = *pa;  // compile error
    let pb = pa;    // compile error
    foo(pa);        // compile error
}

因為 Rust 中不存在 null pointer，因此當你的函式接收到參考型別時，你可以假設它必然指向一個合法的物件，不需要進行額外檢查，編譯器也不會在執行時額外花時間去檢查參考是否合法，進而提昇執行效率。

1
2
3
4
5
fn dump_i32(ptr: &i32)
{
    // 呼叫 dump_i32 時，ptr 保證指向一個合法的 i32 變數
    println!("value is {}", *ptr);
}

Side Effect

另一個參考型別經常造成的問題是，對變數取位址後，該變數就有了別名 (alias)。所有對別名的操作都會反應到同一個變數上，產生了某些意想不到的結果。

迭代器失效 (iterator invalidation) 可以說是這方面最經典的示範：

1
2
3
4
5
6
7
8
void duplicate_key(std::vector<int>& data, int key)
{
    for(auto it = data.begin(); it != data.end(); ++it){
        if(key == *it) {
            data.insert(it, key);
        }
    }
}

這段程式碼會尋訪 vector 中的所有元素，並且把所有符合條件的元素在相同位置複製一份。不幸的是，呼叫 vector::insert 時，有可能會因為預留空間不足而造成 vector 重新配置記憶體以容納更多元素。一旦這件事發生，所有參考到這個 vector 迭代器都會失效，繼續用它來尋訪 vector 是未定義行為。

這個問題的根源來自於對變數的寫入行為，會破壞所有指向該變數的參考。因此 Rust 做了這樣的設計：

  1. 使用 & 取得變數的參考後，你只能透過參考讀取內容，而不能寫入資料。這樣的取址行為，Rust 稱之為 immutable borrow。
  2. 若你想要透過參考寫入資料，必需透過 &mut 來取得位址。這樣的取址稱為 mutable borrow。
  3. Rust 在編譯時會保證，任何變數經過取址後，要嘛同時有許多個 immutable borrow，或是只存在唯一一個 mutable borrow，不允許兩種取址方法同時存在，也不允許有多個 mutable borrow。

馬上來看一個例子：

1
2
3
4
5
6
7
8
9
10
fn main()
{
    let mut a = 10;
    {
        let pa = &a;     // OK
        let pb = &a;     // OK: 多個 immutable borrow 可同時存在
        let pc = &mut a; // Error: mutable borrow 與 immutable borrow 不可同時存在
    }
    let pd = &mut a;     // OK: 已脫離 pa 與 pb 的 scope，因此可以進行 mutable borrow
}

Rust 希望達成的目標是，當你對某一塊記憶體寫入資料時，編譯器可以保證這塊記憶體沒有其它的別名 (alias)，從而避免前述的迭代器失效問題。當然，Rust 的變數本身也是別名之一，因此除了上述三個條款之外，對被取址的變數還有以下條款：

  1. 原本宣告為 mutable 的變數，經過 & 取址後，會暫時變為 immutable，直到所有的 immutable borrow 消滅為止。
  2. 原本宣告為 mutable 的變數，經過 &mut 取址後，會暫時無法存取，直到該 mutable borrow 消滅為止。

以下的程式碼示範這兩個條款的作用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fn main()
{
    let mut a = 10;
    {
        let pa = &a;           // OK: immutable borrow
        println!("a = {}", a); // OK: a 變成 immutable
        a = 20;                // Error: a 變成 immutable
    }
    a = 20;                    // OK: pa 已消滅，a 不存在 immutable borrow
    {
        let pb = &mut a;       // OK: mutable borrow
        println!("a = {}", a); // Error: 此時無法存取 a
        a = 30;                // Error: 此時無法存取 a
    }
    a = 30;                    // OK: pb 已消減，a 不存在 mutable borrow
}

這樣的設計，除了安全性的考量外，對於執行效率也有許多好處。考慮以下的 C++ 程式碼，以及使用 GCC 6.1 加上 -O2 編譯出來的結果：

1
2
3
4
5
6
7
void foo(int* x, int* y, const int* z)
{
               //  movl    (%rdx), %eax
    *x += *z;  //  addl    %eax, (%rdi)
               //  movl    (%rdx), %eax
    *y += *z;  //  addl    %eax, (%rsi)
}

儘管這邊 z 的型別是 const int*，但在 C++ 中 int* 可以安全轉型為 const int*，導致 x, y 與 z 可能指向同一塊記憶體位址，因此在做完第一次加法後，編譯器需要再度把 *z 的值讀取到暫存器，才能進行加法。但在 Rust 中，由於有上述條款護身，編譯器看到 x 與 y 都是 mutable reference，便能假設它們指向不同的空間，而且寫入時完全不影響到 *z 的內容，因此產生更有效率的程式碼。[1]

1
2
3
4
5
6
fn foo(x: &mut i32, y: &mut i32, z: &i32)
{
               //  movl    (%rdx), %eax
    *x += *z;  //  addl    %eax, (%rdi)
    *y += *z;  //  addl    %eax, (%rsi)
}

Lifetime

所有的變數都有生命週期 (lifetime)，而參考型別帶來最困難的問題，就是如何避免懸置參考 (dangling reference)，亦即參考所指向的物件已經消失，但是參考本身仍然可以存取的現象。

1
2
3
4
5
6
7
8
9
10
11
fn foo() -> &mut i32
{
    let mut data = 10;
    return &mut data;
}
fn main()
{
    let ptr = foo();
    *ptr = 20; // 應視為錯誤
}

Java 與 C# 為了避免這種情況，嚴格限制了參考型別指向的目標。因此，這兩個語言都限制 class 僅能使用 heap 配置記憶體空間，並且運用 GC 來保證這些物件的生命週期比所有指向它的參考還要長。然而 Rust 是系統程式語言，為了儘可能達到最高的執行效率，Rust 允許使用者在 stack 上配置物件，並且取得它們的參考。為了確保記憶體安全，Rust 設計了一套非常精細的規則來限制參考型別，保證在程式碼中所有能使用的參考，都必然指向一個有效的物件。

由於 lifetime borrow checker 是 Rust 中最複雜的功能，同時在其它程式語言中也非常罕見，因此我會在下一篇文章中講解這套規則，敬請期待。

  1. 在 C99 標準中的 restrict 關鍵字可以用來宣告某個指標沒有別名，進而達到與 Rust 相同的最佳化效果。然而編譯器並不幫使用者檢查 restrict 的條件是否真正成立，使用者仍有可能不慎傳入指向相同位址的指標，這時候會導致未定義行為。 ↩

分享到 評論