Unix考古記：一個“遺失”的shell
作者：Leo
謹以此文紀念偉大的計算機科學巨匠 Ken Thompson 和 Dennis Ritchie，并同時向其他所有為 Unix 發展做出貢獻的黑客致敬。歷史的塵埃
Unix 作為一個舉世聞名的操作系統已有 40 余年的歷史，圍繞著這個古老的操作系統的發展又衍生出了一系列外圍軟件生態群，其中一個非常重要的組件就是 shell。它是操作系統最外層的接口，負責直接面向用戶交互并提供內核服務，包括命令行接口(CLI)或圖形界面接口(GUI)兩種形式。以 CLI 為例，它提供一套命令規范，是一種解釋性語言，將用戶輸入經過解釋器(interpreter)輸出使其轉化成真正的系統調用，實現人機交互的功能。
和操作系統一樣，shell 也經歷了一個漫長的演變史。如今大部分資料講述最古老的 shell 都是從 1977 年的 Bourne Shell 說起的，它最初移植到 Unix V7上，被追認整個 shell 家族成員的鼻祖，后來的種群都是從其身上分支出來的。
對于 1977 年之前的歷史很多資料大多一筆帶過或略過不提。事實上，第一個移植到 Unix 上的 shell 卻不是 Steve Bourne 寫的，早在 1975 年 5 月，貝爾實驗室就對外發布了第一個廣泛傳播的 Unix 版本——Unix V6（之前開發的版本只供內部研究之用），其根目錄下的/bin/sh 是第一個 Unix 自帶的 shell，由 Ken Thompson 寫的，因此也被稱為 Thompson Shell。甚至，更早可以追溯到 1971 年的時候，Thompson Shell 就作為一個獨立于內核的應用程序而實現了，只不過從 1975 年正式問世到 1977 年被取代，短短兩年的壽命使得它很少為大多數人所認識。
關于 Thompson Shell 被取代的原因在后文中會給出說明，這里著重介紹一下該 shell 本身的一些技術細節。坦白講，關于 Thompson Shell 的資料有點稀缺，但至少還能從網上找到源代碼和在線文檔。Thompson Shell 本身是由一個不足 900 行代碼的解釋器和一些外部命令工具組件(utilities)構成，用K&R C 寫成，下面給出各個組件的相關源碼和文檔鏈接。
- 解釋器 sh：解析各種 shell 命令，包括內置命令和外部命令；源碼 sh.c；安裝路徑/bin/sh；手冊 sh (1)。
- 內置命令手冊包括 chdir (1)，login (1)，newgrp (1)，shift (1)，wait (1)。 </ul>
- exit 命令：退出一個文件；源碼 exit.c；安裝路徑/bin/exit；手冊 exit (1)。
- goto 命令：在一個文件內跳轉 shell 控制流程；源碼 goto.c；安裝路徑/bin/goto；手冊 goto (1)。
- if 命令：條件判斷表達式，是 test 命令的前身；源碼 if.c；安裝路徑/bin/if)， 手冊 if (1)。
- glob 命令：擴展命令參數通配符；源碼 glob.c；安裝路徑/etc/glob；手冊 glob (8)。 </ul>
- 過濾器/管道線(filter/pipeline)。這絕對是要載入 Unix 史冊的發明，創立者是 Douglas McIlroy，Thompson Shell 引入并實現了這個偉大的概念——一個或多個命令組成一根過濾器的鏈條，由’'或’^'符號分隔。除最后一個命令之外，每個命令的標準輸出都被作為下一個命 令的標準輸入。這樣每個命令都作為一個獨立的進程來運行，并通過管道與鄰近的進程相連接。圓括弧內的命令序列整體上可以替代單個命令作為過濾器實現，比如 用戶可以輸入”(A;B)C”。
- 命令序列和后臺進程。分號’;'指示多個命令序列化執行。’&’符號指示該命令在后臺異步執行，使得前面的管道線不必等待其終止，僅僅報告一個進程 id，這樣用戶以后可以通過 kill 命令與它通信。有益于進程管理。
- I/O重定向。它利用了 Unix 設計上的一個重要特性——一切皆文件，用三個符號表示：”重定向輸出，如果文件不存在則創建它，如果文件存在則截斷它；’>>’追加模式重定向輸出，如果文件不存在則創建它，如果文件存在則追加輸出至末尾處。
- 通配符擴展(globbing)。通配符的概念源自于正則表達式，使得解釋器智能地處理用戶不完全輸入，比如 記不清文件名、一次性輸入多個文件等。’?'匹配任意單一字符；’*'匹配任意字符串（包括空串）；成對’['和']‘定義了字符集合一個類，可匹配方括 號內任意成員，用’-'兩端可指定一系列連續字符匹配范圍。
- 參數傳遞。這里主要引入了位置參數和選項參數的概念：’$n’指示 shell 調用的第n個參數替代；還定義了兩個選項參數’-t’和’-c’，前者用于交互，導致 shell 從標準輸入中讀入一行作為用戶執行的系統命令，后者指示 shell 將附帶的下一個參數作為命令執行（可正確處理換行符），是對’-t’的補充，特別是調用者已經讀取了命令其中某些字符的情況下。如果不帶選項參數則直接讀 取文件名 </ul>
- 空格和 tab：簡單過濾。
- 引號：需要成對出現，字符本身被過濾，一對引號之間所有字符都被設置引用標識，作為一個 token。
- 元字符：如’&’，’'等，字符本身作為一個單獨 token。
- 其他字符：一律填充 token，直到碰上以上字符分隔為止。 </ul>
- DTYP（節點類型）：每個節點都有唯一的類型，又分為四種——TCOM（簡單命令）、TPAR（復合命令）、TFIL（過濾器/管道線）、TLST（命令序列）。
- DLEF（左子樹節點）：相當于鏈表指針，根據 DTYP 定義有所不同。如過濾器類型左子樹節點為前一個命令的輸出重定向文件，右子樹節點為后一個命令的輸入重定向文件。
- DRIG（右子樹節點）：同上。
- DFLG（節點屬性）：這是個標志位(flag)，決定該節點包含命令的屬性以及以什么樣的狀態執行。
- DSPR（子命令）：兩重含義，對于簡單命令，該字段為空；對于復合命令，該字段指向子語法樹節點。
- DCOM（命令字符）：引用命令字符序列。 </ul>
下面是外部命令：
命令結構和規范
盡管后來遭“埋汰”，Thompson Shell 仍有著不容否認的歷史地位，其最大的價值在于它奠定了 shell 命令語言結構和規范的基礎，而且其解釋器具有跨平臺的可移植性，并影響到了后來包括 Bourne Shell 在內的各種腳本語言設計實現。下面我們就以其中 5 個特性重溫一些大家已經耳熟能詳的命令規范，你也可以通過 sh (1)手冊查看原始資料。
解釋器的原理與實現
接下來馬上要進入核心部分了，為了搞懂 shell 解釋器原理，我們要對其整個工作流程做個描述（這里給出一份帶注解的 sh.c 源碼剖析）。讀過《編譯原理》的同學知道，解釋器的實現跟編譯器差不多，只不過省略了生成目標代碼這一步，直接將用戶輸入（shell 命令）轉化成輸出（系統調用）。軟件前端是一致的，包括預處理、詞法掃描、語法分析和語義分析，最后還要附加一個進程管理。當 然相較于現代編譯器，Thompson Shell 解釋器在算法和規模上都要簡單得多，不過原理上是相通的，何況年代上要比 Lex & Yacc 還要早。麻雀雖小，五臟俱全，對于初學者來說，從 Thompson Shell 去入手編譯原理或許不失為一種好選擇。
預處理(preprocessor)
同C預處理器需要事先將源代碼中包含的宏和頭文件展開一樣，Thompson Shell 首先需要處理命令中的選項參數和位置參數。選項參數有兩種’-t’和’-c’，決定了 shell 從標準輸入還是參數緩存中讀取字符（見 sh (1)）。此外字符序列中還要處理反斜杠’\’，判斷是轉義字符還是行接續符，前者對下一個字符設置引用標識，表明做普通字符處理，后者將緊鄰其后換行符過濾掉。
位置參數是美元符號’$’打頭的，后帶一個數字，如’$n’，預處理器對 shell 命令參數從頭開始計數，返回數字n指定的參數位置。如果遇上 double’$$’，則表示當前的進程標識，調用 getpid ()獲取。
注意到預處理器需要一次讀取多個字符，這樣就會多讀一個不必要的字符。對此解釋器提供了一種預讀(peek)方式，即每次從輸入流讀取一個字符時，放入一個預讀緩存里（只有一個 int 大小的堆棧），也叫回退(push back)。此后先從預讀緩存中讀取，如果緩存被讀完，則從輸入流中讀取。
詞法掃描(lexical scanning)
經過預處理后的字符序列將被切割成為一系列詞法記號(token)，安置在 token 列表中，掃描器將對以下幾類字符做如下處理。
舉一個例子，當我們輸入命令”(ls; cat tail) >junk”，那么 token 列表映像將是這樣的：
語法分析(syntax parser)
語法分析就是將 token 列表中的元素作為表達式(expression)并以節點為單位構建語法樹， 簡單命令是一個表達式，而復合命令以及命令序列是多個表達式的組合。Thompson Shell 中以簡單數組作為語法樹的容器，實際上這是結構體的一種變形，只不過每個成員字段大小都一樣（都是 sizeof int）而已。一個語法樹節點最多有 6 個字段（大小根據類型可變），分別是
語法樹節點生成順序根據 token 列表中每個元素的優先級(priority)而定，首先遍歷整個列表，找到優先級最高的 token 作為根節點，再分別生成左右子樹，這是一種最簡單的自頂向下(top-down)解決方案。各個 token 優先級視 DTYP 字段而定
執行命令(Executor)
當前面一系列步驟之后，如果錯誤計數為0，則解釋器從語法樹的根節點開始，深度優先遍歷所有節點，并根據前面語法和語義分析得到的類型和屬性，一一執行所包含的命令，以生成最后的系統調用。
對于命令序列(TLST)節點，從左至右順序執行子樹節點命令。
對于過濾器(TFIL)節點，創建管道文件句柄，作為左右子樹的重定向文件。
對于簡單命令(TCOM)和復合命令(TPAR)節點，首先篩選出系統內置命令(built-in)，對于剩下的外部命令則 fork 一個子進程執行它。如果是復合命令中最后一個子命令，那么仍在原來的進程上執行而不必創建新進程。可執行文件路徑按先后順序搜索：①本地路徑；②/bin；③/usr/bin。
多進程環境下，特別要注意文件句柄管理。命令間共享標準輸入輸出設備之外，還會重定向到管道線，而父進程在 fork 之后子進程會獲取一份文件句柄拷貝，所以父進程必須在 fork 之后立即關閉閑置的管道線句柄（如果有的話）以免造成資源泄漏，子進程也將在重定向之后關閉管道線句柄。
對于后臺命令需要打印 pid，但不需要響應中斷信號，父進程也不必等待子進程終止。其余進程命令執行中可捕獲中斷信號，并轉入相應的處理函數。
解釋器用內置的 errno 全局變量保存進程終止狀態，并生成終止報告(termination report)，系統調用 wait ()用于返回終止進程的 pid 并輸出報告消息索引。
孰優孰劣
盡管 Thompson Shell 是一款優秀的命令解釋器，還產生了多項歷史創舉，但遺憾的是依然得不到命運女神的垂青，這要歸咎于其自身的缺陷——功能單一、命令分散、控制流過于簡單，尚無法用來編寫腳本(script)。隨著 Unix 日益壯大，它已經無法應付趨于繁雜的編程項目了。那時還出現了一個叫 John Mashey 的人寫的 PWB Shell（又 叫做 Mashey Shell），基于 Thompson Shell 做了些改進，擴展了命令集，增加了 shell 變量，還增加了 if-then-else-endif，for，while 等控制邏輯。不幸的是它比 Thompson Shell 更短命，因為 1977 年它遇上了一個強勁的對手。
沒錯，那就是 Bourne Shell，它的主要優點是真正實現了結構化腳本編程，比之前的 shell 實現得都要好，更要命的是它與前兩個 shell 都不兼容，于是一場標準化的論戰開始了。在 David G. Korn（ksh 作者）寫的“ksh – An Extensible High Level Language”一 文中提及，Steve Bourne 和 John Mashey 在三次連續的 Unix 用戶組集會上爭論他們各自的理由。在這些集會之間，各自增進他們的 shell 來擁有對方的功能。還設立了一個委員會來選擇標準 shell，最終還是選擇了 Bourne shell 作為標準。
于是從 Unix V7 開始就有了前面所說的”Bourne Shell Family”。然而歷史上沒有完美的技術，隨著八、九十年代操作系統迅猛發展，針對 Bourne Shell 的詬病也越來越多了。在解釋器本身實現上，我看到網上一個對其評價是“universally considered to be one of the most horrible C code ever written”，至于原因去看一下 mac.h 就知道了，包括基本運算符、關鍵字在內的大量宏定義使得整個代碼看上去簡直不是C寫的，也許 Bourne 是想把解釋器打造成自己獨特的風格吧，也難怪后來的 bash 以“born again”命名就是對其祖先的戲謔性調侃。另外內存管理上的一些毛病帶來平臺可移植性問題，至于其中的技術細節有點高級，超出本文范疇。
Thompson Again Shell?
雖然歷史沒有給 Thompson Shell 一個機會，但它并非就此同 Unix V6 那樣一同淪為開源博物館上的古老“化石”。作為出自頂級黑客之手的作品，作為伴隨 Unix 那樣偉大操作系統一同曾經流行計算機的產物，至今仍受國內外程序員的緬懷，或將其改寫，或為其作注。比如國外一個站點 v6shell.org 上就實現了一個免費開源的可移植性 shell，它兼容并擴充原來的 Thompson Shell 并且可用來做腳本編程。再比如中國程序員寒蟬退士在其個人博客上發布了一個注解版，并對原版做了一些改寫，主要是將K&R C轉為ANSI C，并且符合POSIX 規范，使原本晦澀難懂的源碼變得清晰易讀起來。正是因為接觸到他的版本激起了我對老 Unix 的考古興趣，才有了這篇“考古筆記”。我在想不知今后會不會像 bash 那樣，出一個 tash 來呢？
一些感想
本來全文應該就此結束了，但此時此刻不禁想多說幾句。這篇筆記當初并非有意而為之，在 hacking 源碼的過程中感想積累多了也就逐漸成章了。看代碼、作注解、查資料、寫此文，前后歷經四個多禮拜，是在繁雜的工作中“擠乳溝”擠出來的零散時間片拼湊起來 的，雖然文字不長但也算耗費了一番心血，酸甜苦辣心中自明，體會到踏上社會之后潛下心做研究之艱難。如今面對這樣一份不到 900 行寫成的，沒有一行多余的代碼，簡潔(clarity)、干凈(clean)、快速(fast)，這就是 Pure C 的魅力，我深為這種厚重的編程功力所折服，正所謂“大道至簡”吧。雖然要完全弄懂它需要很多時間，但我相信這種代價卻是值得的。
最后再八卦一下，2011 年 Dennis Ritchie 去世了，有人生前問過他“學C需要多久才能成為熟練開發者并寫出重要產品代碼？”，Ritchie 回答“我不知道，我從沒去學過C。”(I don’t know. I never had to learn C.)其實這里已經給出了答案——那就是沒有比去閱讀 Unix 源代碼更好的選擇了，某種意義上C語言就是為 Unix 而生的。
參考資料
The Unix Heritage Society：Unix 社區遺產，上面有 v6 和 v7 以及其它一些衍生版本的操作系統源代碼。
The Traditional Bourne Shell Family：Bourne Shell 家族簡史。
v6shell：osh，一個基于 Thompson Shell 的開源可移植性 old shell。
寒蟬退士的博客：Thompson Shell 的一個注解版。
Evolution of shells in Linux：簡述 Linux Shell 演變史。
附錄一個中文注釋的 shell 源碼