驀然回首萬事空

空指針漫談

在目前大多數的編程語言中,都存在一個很有意思的特殊的指針(或者引用),它代表指向的對象為「空」,名字一般叫做null、nil、None、 Nothing、nullptr等。這個空指針看似簡單,但它引發的問題卻一點也不少,空指針錯誤對許多朋友來說都不陌生,它在許多編程語言中都是非常非常常見的。用Java舉例來說,我們有一個String類型的引用,String str = null;。如果它的值為null,那麼接下來,用它調用成員函數的時候,那麼程序就會拋出一個NullPointerException。如果不catch住這個異常呢,整個程序就會crash掉。據說,這一類問題,已經造成了業界無法估量的巨大損失。

源起

在2009年的一個會議中,著名的「快速排序」演算法的發明者,Tony Hoare向全世界道歉,懺悔他曾經發明了「空指針」這個玩意。

他是這麼說的:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965.

At that time, I was designing the first comprehensive type system for references in an

object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn』t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

原來,在程序語言中加入空指針設計,其實並非是經過深思熟慮的結果,而僅僅是因為它很容易實現而已。這個設計是如此的影響深遠,以至於後來的編程語言都不假思索的繼承了這一設計,這個範圍幾乎包括了目前業界所有的流行的編程語言。對許多程序員來說,早就已經習慣了空指針的存在,就像日常生活中的空氣和水一樣。那麼,空指針究竟有什麼問題,以至於圖靈獎的獲得者Tony Hoare都表示後悔了呢?

問題詳解

空指針最大的問題在於:null是一個合法存在的不合理的值。許多語言讓所有的指針類型都默認具有「可空性」(nullability)。比如,在Java中,除了基本類型之外,其他所有類型的引用都是可以賦值為null的。許多程序員已經習慣於使用null來表示某個特殊的狀態。在某些地方,程序員可能會覺得某個變數從邏輯上可以保證它不會為空,於是就省略掉了空指針檢查。可是,時過境遷之後,因為代碼的各種變化,導致這樣的前提不再成立的時候,空指針異常就發生了。代碼因此非常脆弱。而有些謹慎的程序員,為未雨綢繆計,會在各個地方都加上保護性的空指針檢查,又讓代碼變得非常臃腫。

那麼病根究竟是出在哪裡呢?

一、 空指針引發的第一個問題在於,空指針違背了類型系統的初衷。

我們再來回憶一下,什麼是「類型」?按維基百科的定義,類型是:

Type is a classification identifying one of various types of data, that determines the possible values for that type; the operations that can be done on values of that type;

the meaning of the data; and the way values of that type can be stored.

類型規定了數據可能的取值範圍,規定了在這些值上可能的操作,規定了這些數據代表的含義,規定了這些數據的存儲方式。

我們如果有一個類型Thing,它有一個成員函數doSomeThing(),那麼只要是這個類型的變數,它就一定應該可以調用doSomeThing()函數,完成同樣的操作,返回同樣類型的返回值。

但是,null違背了這樣的約定。一個正常的指針,和一個null指針,哪怕它們是同樣的類型,做同樣的操作,所得到的結果也不一樣。那麼,憑什麼說,null指針是和普通指針是一個類型?

在C++標準文檔中,有這樣的對 pointer literals 的描述:

The pointer literal is the keyword nullptr. It is an rvalue of type std::nullptr_t.

C++引入這個關鍵字的原因是為了解決以前使用宏來定義NULL的各種問題,然而,它依然允許nullptr到各種指針類型的隱式類型轉換。

在C#標準文檔(ECMA C# launguage specification)中,我們可以找到這樣的對null literal的描述:

The null literal (§9.4.4.6) evaluates to the null value, which is used to denote a reference not pointing at any object or array, or the absence of a value. The null type has a single value, which is the null value. Hence an expression whose type is the null type can evaluate only to the null value. There is no way to explicitly write the null type and, therefore, no way to use it in a declared type.

總而言之,null實際上是在類型系統上打開了一個缺口,引入了一個必須在運行期特殊處理的一個特殊的「值」。它就像一個全局的無類型的singleton變數一樣,可以無處不在,可以隨意與任意指針實現自動類型轉換。它讓編譯器的類型檢查在此處失去了意義。

二、 空指針引發的第二個問題在於,它鼓勵API設計者使用空指針作為標記符號(sentinel value)

所謂「標記符號」指的是一種特殊的值,用於標記特殊的狀態。它指的是這樣的一種設計模式:當你需要多個類型A、B、C……的時候,不是去創建多個類型來匹配需求,而是轉而使用一個簡單的、容易實現的類型T,然後把多個類型映射到一個類型的多個區間的值。

比如說,有些這樣的API設計

  • 使用int作為函數的返回值,負數代表錯誤,非負數代表正常的結果,由使用者去判斷這個值的真實含義;
  • 在需要使用enum的場合,使用int類型,然後在每個使用它的地方小心翼翼地檢查這個值是否合理;

關於這一類行為,有網友機智地將其稱之為」Primitive Obsession」(基本類型偏執)。空指針就是這一設計的典範。從底層原理上來說,指針本身實際上就是用一個整數來表示的,它當然可以取值為0,也就是空指針。但是,從語言設計層面,邏輯上來說,我們不該將指針類型與整數類型等同起來,它們所起的作用完全不同,它們能執行的操作完全不同,它們在抽象層面的概念完全不同, 即便它們在機器碼層面的表示方式是一模一樣的。

三、 空指針讓程序設計語言變得更複雜

在C++中,我們考慮以下代碼,把一個整數賦值給一個指針,它會產生編譯錯誤

char *myChar = 123; // compile errorstd::cout << *myChar << std::endl;

但是,我們把整數的值變一下,它又可以編譯通過了

char *myChar = 0;std::cout << *myChar << std::endl; // runtime error

在Java中,我們考慮以下代碼,它是編譯不過的

int x = null; // compile error

但是,我們改個類型,於是就編譯通過了

Integer i = null;int x = i; // runtime error

可惜這樣更糟糕,它會在運行階段拋出異常,導致整個邏輯不能繼續進行。而且,它發生在隱蔽的地方,我們連函數都沒調用。

在javascript中,問題更有意思。如果一個object為空,那麼我們說它的值為null。但是,如果object有一個屬性,它的返回值是null,那麼我們該怎麼區分這個屬性不存在,還是這個屬性存在,但是值為null?javascript的設計者於是又添加了一個undefined全局屬性來區分這兩種情況。實質上,javascript為了解決null的問題,在語言中又加入了另外一種不同形態的null。

解決方案

空指針在許多程序設計語言中太常見了,以至於有許多人誤以為它就像空氣和水一樣,是我們不可或缺的一份子。恰恰相反,錯!

那麼,解決方案是什麼呢?那就是,利用類型系統(sum type),將空指針和非空指針區別開來,分別賦予不同的操作許可權,禁止針對空指針執行解引用操作。編譯器和靜態檢查工具不可能知道一個變數在運行期的「值」,但是可以檢查所有變數所屬的「類型」,來判斷它是否符合了類型系統的各種約定。如果我們把null從一個「值」上升為一個「類型」,那麼靜態檢查就可以發揮其功能了。

在許多的程序設計語言中,實際上早就已經有了這樣的一個設計,叫做Option Type。在 scala、haskell、Ocaml、F# 等許多語言中已經存在了許多年。

下面我們以Rust為例,介紹一下Option是如何解決掉空指針問題的。在Rust中,Option實際上只是一個標準庫中普通的enum:

pub enum Option<T> { /// No value None, /// Some value `T` Some(T)}

Rust中的enum要求,在使用的時候,必須「完整匹配」。意思是說,enum中的每一種可能性,都必須處理,不能遺漏。比如,有一個可空的字元串msg,我們想列印出其中包含的信息,可以這麼做:

let msg : Option<&str> = Some("howdy");match msg { //如果是Some類型,則m匹配到&str類型,於是它可以調用&str所屬的成員函數 Some(m) => println!("{}", m), // 如果是None類型,那麼它無法訪問msg內部數據 None => ()}

我們可以看到,對於一個可空的Option<T>類型,我們沒有辦法直接調用T類型的成員函數,要麼用模式匹配把其中的類型T的內容「拆」出來使用,要麼調用Option類型的成員方法使用。

而對於普通非空類型呢,Rust不允許賦值為None,也不允許不初始化就使用。Rust中,也沒有null這樣的關鍵字。所以,在Rust語言中,根本就沒有空指針錯誤這樣的問題。另外Option類型參數可以是常見的指針類型如 Box 和 & 等,也可以是非指針類型,它的表達能力其實已經超過了「可空的指針」這一種類型。

實際上,C++/C#等語言也發現了初始設計中的缺點,並且開發了一些補救措施。C++標準庫中加入了std::optional<T>類型,C#中加入了System.Nullable<T>類型。可惜的是,受限於早期版本兼容性的要求,這些設計已經不能作為強制要求使用,因此其作用也就弱化了許多。

方法詳解

Option類型有許多非常方便的成員函數可供使用,另外我們還可以利用if let while let等語法糖。許多情況下,沒必要動用match語句。

比如 map 方法,可以把一個 Option<U> 類型轉為另外一個 Option<V> 類型:

let maybe_some_string = Some(String::from("Hello, World!"));let maybe_some_len = maybe_some_string.map(|s| s.len());assert_eq!(maybe_some_len, Some(13));

再比如 and_then 方法,可以把一系列操作串聯起來:

fn sq(x: u32) -> Option<u32> { Some(x * x) }fn nope(_: u32) -> Option<u32> { None }assert_eq!(Some(2).and_then(sq).and_then(sq), Some(16));

這個類型還有許多有用的方法,不必每次都使用 match 語句或者調用 unwrap 方法,既簡潔又清晰。

性能分析

Option類型不僅在表達能力上非常優秀,而且運行開銷也非常小。在這裡我們還可以再次看到「零性能損失的抽象」能力。示例如下:

use std::mem::size_of;fn main() { println!("size of isize : {}", size_of::<isize>() ); println!("size of Option<isize> : {}", size_of::<Option<isize>>() ); println!("size of &isize : {}", size_of::<&isize>() ); println!("size of Box<isize> : {}", size_of::<Box<isize>>() ); println!("size of Option<&isize> : {}", size_of::<Option<&isize>>() ); println!("size of Option<Box<isize>> : {}", size_of::<Option<Box<isize>>>() ); println!("size of *const isize : {}", size_of::<* const isize>() ); println!("size of Option<*const isize> : {}", size_of::<Option<*const isize>>() );}

這個示例分析了Option類型在執行階段所佔用的內存空間大小,結果為:

size of isize : 8size of Option<isize> : 16size of &isize : 8size of Box<isize> : 8size of Option<&isize> : 8size of Option<Box<isize>> : 8size of *const isize : 8size of Option<*const isize> : 16

其中,不帶Option的類型的大小完全在意料之中。isize, &isize, Box<isize> 這幾個類型佔用空間大小都等於該系統一個指針佔用空間大小,不足為奇。Option<isize>類型實際表示的含義是「可能不存在的整數」,因此它除了需要存儲一個isize空間的大小之外,還需要一個標記位(至少 1 bit),來表示該值存在還是不存在的狀態。這裡的結果是16,猜測可能是因為內存對齊的原因。

最讓人驚奇的是,那兩個「可空的指針」類型,佔用空間竟然和一個指針佔用空間相同,並未多浪費一點點的空間來表示「指針是否為空」的狀態。這是因為Rust在這裡做了一個小優化:根據Rust的設計,借用指針&和所有權指針Box從語義上來說,都是不可能為「0」的狀態。它們必須被合適地初始化,不能通過其它類型強制轉換而來,也不能做算術運算。因此Option<&isize> 和 Option<Box<isize>> 類型可以利用這個特點,使用「0」值代表當前狀態為「空」。這意味著,使用Option類型對指針的包裝,在編譯後的機器碼層面,與C/C++的指針完全沒有任何區別。

Rust是如何做到這一點的呢?在標準庫中,Rust設計了這樣的一個struct:

/// A wrapper type for raw pointers and integers that will never be/// NULL or 0 that might allow certain optimizations.#[lang = "non_zero"]#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug, Hash)]pub struct NonZero<T: Zeroable>(T);

它有一個attribute #[lang = "..."]表明這個結構體是Rust語言的一部分,它是被編譯器特殊處理的。凡是被這個結構體包起來的類型,編譯器都將其視為「不可能為0」的。

我們再翻一下看看Box<T>是什麼定義:

#[lang = "owned_box"]#[fundamental]pub struct Box<T: ?Sized>(Unique<T>);

其中,Unique<T>的定義是:

pub struct Unique<T: ?Sized> { pointer: NonZero<*const T>, _marker: PhantomData<T>,}

其中PhantomData<T>是一個零大小的類型 pub struct PhantomData<T:?Sized>;,它的作用是在unsafe編程的時候輔助編譯器靜態檢查的,在運行階段無性能開銷,此處暫時略過。

把以上代碼綜合起來,可以發現,Option<Box<T>>的實際內部表示形式是Option<NonZero<*const T>>。

NonZero是一個特殊的類型,

#[lang = "non_zero"]#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug, Hash)]pub struct NonZero<T: Zeroable>(T);

#[lang = "non_zero],說明這是編譯器特殊照顧的功能,這個類型可以告訴編譯器,它不可能取值為0。那編譯器就自然有能力將這個類型的佔用空間壓縮到與* const T類型佔用空間一致。

而對於 * const T類型,它本身是有可能取值為0的,因此這種類型無法執行優化,Option<* const T> 的大小就變成了2個指針大小。

大家搞明白這一點後,我們自定義的類型如果也符合同樣的條件,也可以利用這個特性,來完成優化。

總結

總結來說,常見的過程式編程語言在類型系統設計上犯了一些錯誤。而這些問題實際上早就在類型理論基礎上得以解決。類型安全是Rust解決內存安全、線程安全的重要拼圖之一。在後面的一系列文章中,我們還會繼續討論類型系統的話題。Rust這樣的設計有以下幾個優點:

  1. 如果從邏輯上說,我們需要一個變數確實是可空的,那麼就應該顯式標明其類型為Option<T> 否則應該直接聲明為T類型。從類型系統的角度來說,這二者有本質區別,切不可混為一談。
  2. 代碼更安全。因為類型系統的存在,空指針現在可以被編譯器完美檢測,從根源上杜絕了這個問題,不可能有漏網之魚,大幅提高了程序的健壯性。
  3. 執行效率更高。Null不再是到處都可能出現的一個怪物,不再需要程序員到處檢查空指針問題。多餘的空指針檢查是完全沒有必要的。
  4. 大家也不必擔心這樣的設計會導致大量的match語句,使得程序可讀性變差。因為Option類型有許多方便的成員函數,再配合上閉包功能,實際上在表達能力和可讀性上要更勝一籌。

所以說,空指針的確是一個編程語言設計史上的重大失誤,該錯誤流毒之廣,影響之巨,難有其匹。怪不得Tony老爺子要感嘆一句:一失足成千古恨,再回頭已百年身!

本文同步發布在微信公眾號:Rust編程,歡迎關注!

推薦閱讀:

Clone VS Copy
地獄裡的Rust (一)struct 設計機巧初步

TAG:Rust编程语言 | 编程语言 | 编程学习 |