歷史的塵埃

Unix作為一個舉世聞名的操作系統(tǒng)已有40余年的歷史，圍繞著這個古老的操作系統(tǒng)的發(fā)展又衍生出了一系列外圍軟件生態(tài)群，其中一個非常重要的組件就是shell。它是操作系統(tǒng)最外層的接口，負責直接面向用戶交互并提供內(nèi)核服務，包括命令行接口(CLI)或圖形界面接口(GUI)兩種形式。以CLI為例，它提供一套命令規(guī)范，是一種解釋性語言，將用戶輸入經(jīng)過解釋器(interpreter)輸出使其轉化成真正的系統(tǒng)調(diào)用，實現(xiàn)人機交互的功能。

和操作系統(tǒng)一樣，shell也經(jīng)歷了一個漫長的演變史。如今大部分資料講述最古老的shell都是從1977年的Bourne Shell說起的，它最初移植到Unix V7上，被追認整個shell家族成員的鼻祖，后來的種群都是從其身上分支出來的。

對于1977年之前的歷史很多資料大多一筆帶過或略過不提。事實上，第一個移植到Unix上的shell卻不是Steve Bourne寫的，早在1975年5月，貝爾實驗室就對外發(fā)布了第一個廣泛傳播的Unix版本——Unix V6（之前開發(fā)的版本只供內(nèi)部研究之用），其根目錄下的/bin/sh是第一個Unix自帶的shell，由Ken Thompson寫的，因此也被稱為Thompson Shell。甚至，更早可以追溯到1971年的時候，Thompson Shell就作為一個獨立于內(nèi)核的應用程序而實現(xiàn)了，只不過從1975年正式問世到1977年被取代，短短兩年的壽命使得它很少為大多數(shù)人所認識。

關于Thompson Shell被取代的原因在后文中會給出說明，這里著重介紹一下該shell本身的一些技術細節(jié)。坦白講，關于Thompson Shell的資料有點稀缺，但至少還能從網(wǎng)上找到源代碼和在線文檔。Thompson Shell本身是由一個不足900行代碼的解釋器和一些外部命令工具組件(utilities)構成，用K&R C寫成，下面給出各個組件的相關源碼和文檔鏈接。

解釋器sh：解析各種shell命令，包括內(nèi)置命令和外部命令；源碼sh.c；安裝路徑/bin/sh；手冊sh(1)。

• 內(nèi)置命令手冊包括chdir(1)，login(1)，newgrp(1)，shift(1)，wait(1)。

下面是外部命令：

• exit命令：退出一個文件；源碼exit.c；安裝路徑/bin/exit；手冊exit(1)。
• goto命令：在一個文件內(nèi)跳轉shell控制流程；源碼goto.c；安裝路徑/bin/goto；手冊goto(1)。
• if命令：條件判斷表達式，是test命令的前身；源碼if.c；安裝路徑/bin/if), 手冊if(1)。
• glob命令：擴展命令參數(shù)通配符；源碼glob.c；安裝路徑/etc/glob；手冊glob(8)。

命令結構和規(guī)范

盡管后來遭“埋汰”，Thompson Shell仍有著不容否認的歷史地位，其最大的價值在于它奠定了shell命令語言結構和規(guī)范的基礎，而且其解釋器具有跨平臺的可移植性，并影響到了后來包括Bourne Shell在內(nèi)的各種腳本語言設計實現(xiàn)。下面我們就以其中5個特性重溫一些大家已經(jīng)耳熟能詳?shù)拿钜?guī)范，你也可以通過sh(1)手冊查看原始資料。

• 過濾器/管道線(filter/pipeline)。這絕對是要載入Unix史冊的發(fā)明，創(chuàng)立者是Douglas McIlroy，Thompson Shell引入并實現(xiàn)了這個偉大的概念——一個或多個命令組成一根過濾器的鏈條，由’|'或’^'符號分隔。除最后一個命令之外，每個命令的標準輸出都被作為下一個命令的標準輸入。這樣每個命令都作為一個獨立的進程來運行，并通過管道與鄰近的進程相連接。圓括弧內(nèi)的命令序列整體上可以替代單個命令作為過濾器實現(xiàn)，比如用戶可以輸入”(A;B)|C”。
• 命令序列和后臺進程。分號’;'指示多個命令序列化執(zhí)行。’&’符號指示該命令在后臺異步執(zhí)行，使得前面的管道線不必等待其終止，僅僅報告一個進程id，這樣用戶以后可以通過kill命令與它通信。有益于進程管理。
• I/O重定向。它利用了Unix設計上的一個重要特性——一切皆文件，用三個符號表示：”重定向輸出，如果文件不存在則創(chuàng)建它，如果文件存在則截斷它；’>>’追加模式重定向輸出，如果文件不存在則創(chuàng)建它，如果文件存在則追加輸出至末尾處。
• 通配符擴展(globbing)。通配符的概念源自于正則表達式，使得解釋器智能地處理用戶不完全輸入，比如記不清文件名、一次性輸入多個文件等。’?'匹配任意單一字符；’*'匹配任意字符串（包括空串）；成對’['和']‘定義了字符集合一個類，可匹配方括號內(nèi)任意成員，用’-'兩端可指定一系列連續(xù)字符匹配范圍。
• 參數(shù)傳遞。這里主要引入了位置參數(shù)和選項參數(shù)的概念：’$n’指示shell調(diào)用的第n個參數(shù)替代；還定義了兩個選項參數(shù)’-t’和’-c’，前者用于交互，導致shell從標準輸入中讀入一行作為用戶執(zhí)行的系統(tǒng)命令，后者指示shell將附帶的下一個參數(shù)作為命令執(zhí)行（可正確處理換行符），是對’-t’的補充，特別是調(diào)用者已經(jīng)讀取了命令其中某些字符的情況下。如果不帶選項參數(shù)則直接讀取文件名

解釋器的原理與實現(xiàn)

接下來馬上要進入核心部分了，為了搞懂shell解釋器原理，我們要對其整個工作流程做個描述（這里給出一份帶注解的sh.c源碼剖析）。讀過《編譯原理》的同學知道，解釋器的實現(xiàn)跟編譯器差不多，只不過省略了生成目標代碼這一步，直接將用戶輸入（shell命令）轉化成輸出（系統(tǒng)調(diào)用）。軟件前端是一致的，包括預處理、詞法掃描、語法分析和語義分析，最后還要附加一個進程管理。當然相較于現(xiàn)代編譯器，Thompson Shell解釋器在算法和規(guī)模上都要簡單得多，不過原理上是相通的，何況年代上要比Lex & Yacc還要早。麻雀雖小，五臟俱全，對于初學者來說，從Thompson Shell去入手編譯原理或許不失為一種好選擇。

預處理(preprocessor)

同C預處理器需要事先將源代碼中包含的宏和頭文件展開一樣，Thompson Shell首先需要處理命令中的選項參數(shù)和位置參數(shù)。選項參數(shù)有兩種’-t’和’-c’，決定了shell從標準輸入還是參數(shù)緩存中讀取字符（見sh(1)）。此外字符序列中還要處理反斜杠’\’，判斷是轉義字符還是行接續(xù)符，前者對下一個字符設置引用標識，表明做普通字符處理，后者將緊鄰其后換行符過濾掉。

位置參數(shù)是美元符號’$’打頭的，后帶一個數(shù)字，如’$n’，預處理器對shell命令參數(shù)從頭開始計數(shù)，返回數(shù)字n指定的參數(shù)位置。如果遇上double’$$’，則表示當前的進程標識，調(diào)用getpid()獲取。

注意到預處理器需要一次讀取多個字符，這樣就會多讀一個不必要的字符。對此解釋器提供了一種預讀(peek)方式，即每次從輸入流讀取一個字符時，放入一個預讀緩存里（只有一個int大小的堆棧），也叫回退(push back)。此后先從預讀緩存中讀取，如果緩存被讀完，則從輸入流中讀取。

詞法掃描(lexical scanning)

經(jīng)過預處理后的字符序列將被切割成為一系列詞法記號(token)，安置在token列表中，掃描器將對以下幾類字符做如下處理。

• 空格和tab：簡單過濾。
• 引號：需要成對出現(xiàn)，字符本身被過濾，一對引號之間所有字符都被設置引用標識，作為一個token。
• 元字符：如’&’，’|'等，字符本身作為一個單獨token。
• 其他字符：一律填充token，直到碰上以上字符分隔為止。

舉一個例子，當我們輸入命令”(ls; cat tail) >junk”，那么token列表映像將是這樣的：

#p#

語法分析(syntax parser)

語法分析就是將token列表中的元素作為表達式(expression)并以節(jié)點為單位構建語法樹，簡單命令是一個表達式，而復合命令以及命令序列是多個表達式的組合。Thompson Shell中以簡單數(shù)組作為語法樹的容器，實際上這是結構體的一種變形，只不過每個成員字段大小都一樣（都是sizeof int）而已。一個語法樹節(jié)點最多有6個字段（大小根據(jù)類型可變），分別是

• DTYP（節(jié)點類型）：每個節(jié)點都有唯一的類型，又分為四種——TCOM（簡單命令）、TPAR（復合命令）、TFIL（過濾器/管道線）、TLST（命令序列）。
• DLEF（左子樹節(jié)點）：相當于鏈表指針，根據(jù)DTYP定義有所不同。如過濾器類型左子樹節(jié)點為前一個命令的輸出重定向文件，右子樹節(jié)點為后一個命令的輸入重定向文件。
• DRIG（右子樹節(jié)點）：同上。
• DFLG（節(jié)點屬性）：這是個標志位(flag)，決定該節(jié)點包含命令的屬性以及以什么樣的狀態(tài)執(zhí)行。
• DSPR（子命令）：兩重含義，對于簡單命令，該字段為空；對于復合命令，該字段指向子語法樹節(jié)點。
• DCOM（命令字符）：引用命令字符序列。

語法樹節(jié)點生成順序根據(jù)token列表中每個元素的優(yōu)先級(priority)而定，首先遍歷整個列表，找到優(yōu)先級最高的token作為根節(jié)點，再分別生成左右子樹，這是一種最簡單的自頂向下(top-down)解決方案。各個token優(yōu)先級視DTYP字段而定

語法樹的構建過程中還使用了一種基于“有限狀態(tài)機(finite-state machine)”的動態(tài)規(guī)劃算法，其實現(xiàn)是將整個邏輯流程劃分為四個狀態(tài)：syntax、syn1、syn2、syn3，對應于上面token優(yōu)先級，程序在每個狀態(tài)下都生成一個相應類型的節(jié)點，同時還生成四種策略，以決議下一步將轉移到何種狀態(tài)（根據(jù)優(yōu)先級搜索對應的token）。這個四種策略分別是

• 生成左子樹：左邊token列表遞進到下層狀態(tài)。
• 生成右子樹：右邊token列表并回溯到上層狀態(tài)或遞歸調(diào)用。
• 找不到對應token：保持原有token列表遞進到下層狀態(tài)。
• 生成節(jié)點：直接返回節(jié)點。

當我們遍歷完整個token列表后，程序總是能返回最初的調(diào)用點，即根節(jié)點上，從而生成一棵完整的語法樹。這種算法的好處是程序員不必關注具體實現(xiàn)的每個細枝末節(jié)，只要關注相應的狀態(tài)并制定對應的轉移策略即可。還值得一提的是每個轉移策略都是發(fā)生在賦值語句或返回語句上，并使用函數(shù)實參保存臨時變量，這樣就避免了調(diào)用次數(shù)過多導致堆棧溢出。

依舊舉兩個個例子，比如命令”A & ; B | C”對應的語法樹

命令”(A ; B) | C”對應的語法樹：

語義分析(Semantic Analyzer)

語法分析僅僅停留在token表達式合法性層面上，它并不知道該表達式是否有意義，比如哪些命令是要后臺運行，哪些命令的I/O被重定向到管道線上，通配符該如何擴展等等，這時候要靠語義分析了。這里的“語義”體現(xiàn)在對特殊字符的動態(tài)處理以及語法樹節(jié)點的字段設置，根據(jù)上下文(context)而定。比如對于元字符’>’，我們要判斷輸出重定向到哪個文件，是截斷還是追加。對于通配符’?'、’*'和’[...]‘，我們要決定對哪些字符進行擴展，這些在/etc/glob中專門處理。對于語法樹節(jié)點，除了自身固有屬性之外，還需要繼承上層節(jié)點的屬性，以及下推屬性到下層子樹節(jié)點，下面列了一張表格說明。

執(zhí)行命令(Executor)

當前面一系列步驟之后，如果錯誤計數(shù)為0，則解釋器從語法樹的根節(jié)點開始，深度優(yōu)先遍歷所有節(jié)點，并根據(jù)前面語法和語義分析得到的類型和屬性，一一執(zhí)行所包含的命令，以生成最后的系統(tǒng)調(diào)用。

對于命令序列(TLST)節(jié)點，從左至右順序執(zhí)行子樹節(jié)點命令。

對于過濾器(TFIL)節(jié)點，創(chuàng)建管道文件句柄，作為左右子樹的重定向文件。

對于簡單命令(TCOM)和復合命令(TPAR)節(jié)點，首先篩選出系統(tǒng)內(nèi)置命令(built-in)，對于剩下的外部命令則fork一個子進程執(zhí)行它。如果是復合命令中最后一個子命令，那么仍在原來的進程上執(zhí)行而不必創(chuàng)建新進程。可執(zhí)行文件路徑按先后順序搜索：①本地路徑；②/bin；③/usr/bin。

多進程環(huán)境下，特別要注意文件句柄管理。命令間共享標準輸入輸出設備之外，還會重定向到管道線，而父進程在fork之后子進程會獲取一份文件句柄拷貝，所以父進程必須在fork之后立即關閉閑置的管道線句柄（如果有的話）以免造成資源泄漏，子進程也將在重定向之后關閉管道線句柄。

對于后臺命令需要打印pid，但不需要響應中斷信號，父進程也不必等待子進程終止。其余進程命令執(zhí)行中可捕獲中斷信號，并轉入相應的處理函數(shù)。

解釋器用內(nèi)置的errno全局變量保存進程終止狀態(tài)，并生成終止報告(termination report)，系統(tǒng)調(diào)用wait()用于返回終止進程的pid并輸出報告消息索引。

孰優(yōu)孰劣

盡管Thompson Shell是一款優(yōu)秀的命令解釋器，還產(chǎn)生了多項歷史創(chuàng)舉，但遺憾的是依然得不到命運女神的垂青，這要歸咎于其自身的缺陷——功能單一、命令分散、控制流過于簡單，尚無法用來編寫腳本(script)。隨著Unix日益壯大，它已經(jīng)無法應付趨于繁雜的編程項目了。那時還出現(xiàn)了一個叫John Mashey的人寫的PWB Shell（又叫做Mashey Shell），基于Thompson Shell做了些改進，擴展了命令集，增加了shell變量，還增加了if-then-else-endif，for，while等控制邏輯。不幸的是它比Thompson Shell更短命，因為1977年它遇上了一個強勁的對手。

沒錯，那就是Bourne Shell，它的主要優(yōu)點是真正實現(xiàn)了結構化腳本編程，比之前的shell實現(xiàn)得都要好，更要命的是它與前兩個shell都不兼容，于是一場標準化的論戰(zhàn)開始了。在David G. Korn（ksh作者）寫的“ksh – An Extensible High Level Language”一文中提及，Steve Bourne和John Mashey在三次連續(xù)的Unix用戶組集會上爭論他們各自的理由。在這些集會之間，各自增進他們的shell來擁有對方的功能。還設立了一個委員會來選擇標準shell，最終還是選擇了Bourne shell作為標準。

于是從Unix V7開始就有了前面所說的”Bourne Shell Family”。然而歷史上沒有完美的技術，隨著八、九十年代操作系統(tǒng)迅猛發(fā)展，針對Bourne Shell的詬病也越來越多了。在解釋器本身實現(xiàn)上，我看到網(wǎng)上一個對其評價是“universally considered to be one of the most horrible C code ever written”，至于原因去看一下mac.h就知道了，包括基本運算符、關鍵字在內(nèi)的大量宏定義使得整個代碼看上去簡直不是C寫的，也許Bourne是想把解釋器打造成自己獨特的風格吧，也難怪后來的bash以“born again”命名就是對其祖先的戲謔性調(diào)侃。另外內(nèi)存管理上的一些毛病帶來平臺可移植性問題，至于其中的技術細節(jié)有點高級，超出本文范疇。

Thompson Again Shell?

雖然歷史沒有給Thompson Shell一個機會，但它并非就此同Unix V6那樣一同淪為開源博物館上的古老“化石”。作為出自頂級黑客之手的作品，作為伴隨Unix那樣偉大操作系統(tǒng)一同曾經(jīng)流行計算機的產(chǎn)物，至今仍受國內(nèi)外程序員的緬懷，或?qū)⑵涓膶懀驗槠渥髯ⅰ１热鐕庖粋€站點v6shell.org上就實現(xiàn)了一個免費開源的可移植性shell，它兼容并擴充原來的Thompson Shell并且可用來做腳本編程。再比如中國程序員寒蟬退士在其個人博客上發(fā)布了一個注解版，并對原版做了一些改寫，主要是將K&R C轉為ANSI C，并且符合POSIX規(guī)范，使原本晦澀難懂的源碼變得清晰易讀起來。正是因為接觸到他的版本激起了我對老Unix的考古興趣，才有了這篇“考古筆記”。我在想不知今后會不會像bash那樣，出一個tash來呢？

一些感想

本來全文應該就此結束了，但此時此刻不禁想多說幾句。這篇筆記當初并非有意而為之，在hacking源碼的過程中感想積累多了也就逐漸成章了。看代碼、作注解、查資料、寫此文，前后歷經(jīng)四個多禮拜，是在繁雜的工作中“擠乳溝”擠出來的零散時間片拼湊起來的，雖然文字不長但也算耗費了一番心血，酸甜苦辣心中自明，體會到踏上社會之后潛下心做研究之艱難。如今面對這樣一份不到900行寫成的，沒有一行多余的代碼，簡潔(clarity)、干凈(clean)、快速(fast)，這就是Pure C的魅力，我深為這種厚重的編程功力所折服，正所謂“大道至簡”吧。雖然要完全弄懂它需要很多時間，但我相信這種代價卻是值得的。

最后再八卦一下，2011年Dennis Ritchie去世了，有人生前問過他“學C需要多久才能成為熟練開發(fā)者并寫出重要產(chǎn)品代碼？”，Ritchie回答“我不知道，我從沒去學過C。”(I don’t know. I never had to learn C.)其實這里已經(jīng)給出了答案——那就是沒有比去閱讀Unix源代碼更好的選擇了，某種意義上C語言就是為Unix而生的。

[[74920]]

​原文鏈接：http://coolshell.cn/articles/9410.html