從零開始的 JSON 庫教程（二）：解析數字

01-31

本文是《從零開始的 JSON 庫教程》的第二個單元。本單元的源代碼位於 json-tutorial/tutorial02。

本單元內容：

初探重構
JSON 數字語法
數字表示方式
單元測試
十進位轉換至二進位
總結與練習
參考
常見問題

（題圖 Photo by Tim Evans）

1. 初探重構

在討論解析數字之前，我們再補充 TDD 中的一個步驟──重構（refactoring）。根據[1]，重構是一個這樣的過程：

在不改變代碼外在行為的情況下，對代碼作出修改，以改進程序的內部結構。

在 TDD 的過程中，我們的目標是編寫代碼去通過測試。但由於這個目標的引導性太強，我們可能會忽略正確性以外的軟體品質。在通過測試之後，代碼的正確性得以保證，我們就應該審視現時的代碼，看看有沒有地方可以改進，而同時能維持測試順利通過。我們可以安心地做各種修改，因為我們有單元測試，可以判斷代碼在修改後是否影響原來的行為。

那麼，哪裡要作出修改？Beck 和 Fowler（[1] 第 3 章）認為程序員要培養一種判斷能力，找出程序中的壞味道。例如，在第一單元的練習中，可能大部分人都會複製 lept_parse_null() 的代碼，作一些修改，成為 lept_parse_true() 和lept_parse_false()。如果我們再審視這 3 個函數，它們非常相似。這違反編程中常說的 DRY（dont repeat yourself）原則。本單元的第一個練習題，就是嘗試合併這 3 個函數。

另外，我們也可能發現，單元測試代碼也有很重複的代碼，例如 test_parse_invalid_value() 中我們每次測試一個不合法的 JSON 值，都有 4 行相似的代碼。我們可以把它用宏的方式把它們簡化：

#define TEST_ERROR(error, json)n do {n lept_value v;n v.type = LEPT_FALSE;n EXPECT_EQ_INT(error, lept_parse(&v, json));n EXPECT_EQ_INT(LEPT_NULL, lept_get_type(&v));n } while(0)nnstatic void test_parse_expect_value() {n TEST_ERROR(LEPT_PARSE_EXPECT_VALUE, "");n TEST_ERROR(LEPT_PARSE_EXPECT_VALUE, " ");n}n

最後，我希望指出，軟體的架構難以用單一標準評分，重構時要考慮平衡各種軟體品質。例如上述把 3 個函數合併後，優點是減少重複的代碼，維護較容易，但缺點可能是帶來性能的少量影響。

2. JSON 數字語法

回歸正題，本單元的重點在於解析 JSON number 類型。我們先看看它的語法：

number = [ "-" ] int [ frac ] [ exp ]nint = "0" / digit1-9 *digitnfrac = "." 1*digitnexp = ("e" / "E") ["-" / "+"] 1*digitn

number 是以十進位表示，它主要由 4 部分順序組成：負號、整數、小數、指數。只有整數是必需部分。注意和直覺可能不同的是，正號是不合法的。

整數部分如果是 0 開始，只能是單個 0；而由 1-9 開始的話，可以加任意數量的數字（0-9）。也就是說，0123 不是一個合法的 JSON 數字。

小數部分比較直觀，就是小數點後是一或多個數字（0-9）。

JSON 可使用科學記數法，指數部分由大寫 E 或小寫 e 開始，然後可有正負號，之後是一或多個數字（0-9）。

JSON 標準 ECMA-404 採用圖的形式表示語法，也可以更直觀地看到解析時可能經過的路徑：

上一單元的 null、false、true 在解析後，我們只需把它們存儲為類型。但對於數字，我們要考慮怎麼存儲解析後的結果。

3. 數字表示方式

從 JSON 數字的語法，我們可能直觀地會認為它應該表示為一個浮點數（floating point number），因為它帶有小數和指數部分。然而，標準中並沒有限制數字的範圍或精度。為簡單起見，leptjson 選擇以雙精度浮點數（C 中的 double 類型）來存儲 JSON 數字。

我們為 lept_value 添加成員：

typedef struct {n double n;n lept_type type;n}lept_value;n

僅當 type == LEPT_NUMBER 時，n 才表示 JSON 數字的數值。所以獲取該值的 API 是這麼實現的：

double lept_get_number(const lept_value* v) {n assert(v != NULL && v->type == LEPT_NUMBER);n return v->n;n}n

使用者應確保類型正確，才調用此 API。我們繼續使用斷言來保證。

4. 單元測試

我們定義了 API 之後，按照 TDD，我們可以先寫一些單元測試。這次我們使用多行的宏的減少重複代碼：

#define TEST_NUMBER(expect, json)n do {n lept_value v;n EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, json));n EXPECT_EQ_INT(LEPT_NUMBER, lept_get_type(&v));n EXPECT_EQ_DOUBLE(expect, lept_get_number(&v));n } while(0)nnstatic void test_parse_number() {n TEST_NUMBER(0.0, "0");n TEST_NUMBER(0.0, "-0");n TEST_NUMBER(0.0, "-0.0");n TEST_NUMBER(1.0, "1");n TEST_NUMBER(-1.0, "-1");n TEST_NUMBER(1.5, "1.5");n TEST_NUMBER(-1.5, "-1.5");n TEST_NUMBER(3.1416, "3.1416");n TEST_NUMBER(1E10, "1E10");n TEST_NUMBER(1e10, "1e10");n TEST_NUMBER(1E+10, "1E+10");n TEST_NUMBER(1E-10, "1E-10");n TEST_NUMBER(-1E10, "-1E10");n TEST_NUMBER(-1e10, "-1e10");n TEST_NUMBER(-1E+10, "-1E+10");n TEST_NUMBER(-1E-10, "-1E-10");n TEST_NUMBER(1.234E+10, "1.234E+10");n TEST_NUMBER(1.234E-10, "1.234E-10");n TEST_NUMBER(0.0, "1e-10000"); /* must underflow */n}n

以上這些都是很基本的測試用例，也可供調試用。大部分情況下，測試案例不能窮舉所有可能性。因此，除了加入一些典型的用例，我們也常會使用一些邊界值，例如最大值等。練習中會讓同學找一些邊界值作為用例。

除了這些合法的 JSON，我們也要寫一些不合語法的用例：

static void test_parse_invalid_value() {n /* ... */n /* invalid number */n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "+0");n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "+1");n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, ".123"); /* at least one digit before . */n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "1."); /* at least one digit after . */n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "INF");n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "inf");n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "NAN");n TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "nan");n}n

5. 十進位轉換至二進位

我們需要把十進位的數字轉換成二進位的 double。這並不是容易的事情 [2]。為了簡單起見，leptjson 將使用標準庫的strtod() 來進行轉換。strtod() 可轉換 JSON 所要求的格式，但問題是，一些 JSON 不容許的格式，strtod() 也可轉換，所以我們需要自行做格式校驗。

#include <stdlib.h> /* NULL, strtod() */nnstatic int lept_parse_number(lept_context* c, lept_value* v) {n char* end;n /* TODO validate number */n v->n = strtod(c->json, &end);n if (c->json == end)n return LEPT_PARSE_INVALID_VALUE;n c->json = end;n v->type = LEPT_NUMBER;n return LEPT_PARSE_OK;n}n

加入了 number 後，value 的語法變成：

value = null / false / true / numbern

記得在第一單元中，我們說可以用一個字元就能得知 value 是什麼類型，有 11 個字元可判斷 number：

0-9/- ? number

但是，由於我們在 lept_parse_number() 內部將會校驗輸入是否正確的值，我們可以簡單地把餘下的情況都交給lept_parse_number()：

static int lept_parse_value(lept_context* c, lept_value* v) {n switch (*c->json) {n case t: return lept_parse_true(c, v);n case f: return lept_parse_false(c, v);n case n: return lept_parse_null(c, v);n default: return lept_parse_number(c, v);n case 0: return LEPT_PARSE_EXPECT_VALUE;n }n}n

6. 總結與練習

本單元講述了 JSON 數字類型的語法，以及 leptjson 所採用的自行校驗＋strtod()轉換為 double 的方案。實際上一些 JSON 庫會採用更複雜的方案，例如支持 64 位帶符號／無符號整數，自行實現轉換。以我的個人經驗，解析／生成數字類型可以說是 RapidJSON 中最難實現的部分，也是 RapidJSON 高效性能的原因，有機會再另外撰文解釋。

此外我們談及，重構與單元測試是互相依賴的軟體開發技術，適當地運用可提升軟體的品質。之後的單元還會有相關的話題。

重構合併 lept_parse_null()、lept_parse_false()、lept_parse_true 為 lept_parse_literal()。
加入維基百科雙精度浮點數的一些邊界值至單元測試，如 min subnormal positive double、max double 等。
去掉 test_parse_invalid_value() 和 test_parse_root_not_singular 中的 #if 0 ... #endif，執行測試，證實測試失敗。按 JSON number 的語法在 lept_parse_number() 校驗，不符合標準的程況返回LEPT_PARSE_INVALID_VALUE　錯誤碼。
去掉 test_parse_number_too_big 中的 #if 0 ... #endif，執行測試，證實測試失敗。仔細閱讀 strtod()，看看怎樣從返回值得知數值是否過大，以返回 LEPT_PARSE_NUMBER_TOO_BIG 錯誤碼。（提示：這裡需要 #include 額外兩個標準庫頭文件。）

以上最重要的是第 3 條題目，就是要校驗 JSON 的數字語法。建議可使用以下兩個宏去簡化一下代碼：

#define ISDIGIT(ch) ((ch) >= 0 && (ch) <= 9)n#define ISDIGIT1TO9(ch) ((ch) >= 1 && (ch) <= 9)n

另一提示，在校驗成功以後，我們不再使用 end 指針去檢測 strtod() 的正確性，第二個參數可傳入 NULL。

如果你遇到問題，有不理解的地方，或是有建議，都歡迎在評論或 issue 中提出，讓所有人一起討論。

7. 參考

[1] Fowler, Martin. Refactoring: improving the design of existing code. Pearson Education India, 2009. 中譯本：《重構：改善既有代碼的設計》，熊節譯，人民郵電出版社，2010年。 [2] Gay, David M. "Correctly rounded binary-decimal and decimal-binary conversions." Numerical Analysis Manuscript 90-10 (1990).

8. 常見問題

為什麼要把一些測試代碼以 #if 0 ... #endif 禁用？
因為在做第 1 個練習題時，我希望能 100% 通過測試，方便做重構。另外，使用 #if 0 ... #endif 而不使用 /* ... */，是因為 C 的注釋不支持嵌套（nested），而 #if ... #endif 是支持嵌套的。代碼中已有注釋時，用 #if 0 ... #endif 去禁用代碼是一個常用技巧，而且可以把 0 改為 1 去恢復。
科學計數法的指數部分沒有對前導零作限制嗎？1E012 也是合法的嗎？
是的，這是合法的。JSON 源自於 JavaScript（ECMA-262, 3rd edition），數字語法取自 JavaScript 的十進位數字的語法（§7.8.3 Numeric Literals）。整數不容許前導零（leading zero），是因為更久的 JavaScript 版本容許以前導零來表示八進位數字，如 052 == 42，這種八進位常數表示方式來自於 C 語言。禁止前導零避免了可能出現的歧義。但是在指數里就不會出現這個問題。多謝 @Smallay 提出及協助解答這個問題。

其他常見問答將會從評論中整理。