從零開始的 JSON 庫教程（六）：解析對象

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

本單元內容：

1. JSON 對象
2. 數據結構
3. 重構字元串解析
4. 實現
5. 總結與練習

（題圖 Photo by Azrul Aziz）

1. JSON 對象

此單元是本教程最後一個關於 JSON 解析器的部分。JSON 對象和 JSON 數組非常相似，區別包括 JSON 對象以花括弧 {}（U+007B、U+007D）包裹表示，另外 JSON 對象由對象成員（member）組成，而 JSON 數組由 JSON 值組成。所謂對象成員，就是鍵值對，鍵必須為 JSON 字元串，然後值是任何 JSON 值，中間以冒號 :（U+003A）分隔。完整語法如下：

member = string ws %x3A ws valueobject = %x7B ws [ member *( ws %x2C ws member ) ] ws %x7D

2. 數據結構

要表示鍵值對的集合，有很多數據結構可供選擇，例如：

• 動態數組（dynamic array）：可擴展容量的數組，如 C++ 的 std::vector。
• 有序動態數組（sorted dynamic array）：和動態數組相同，但保證元素已排序，可用二分搜尋查詢成員。
• 平衡樹（balanced tree）：平衡二叉樹可有序地遍歷成員，如紅黑樹和 C++ 的 std::map（std::multi_map 支持重複鍵）。
• 哈希表（hash table）：通過哈希函數能實現平均 O(1) 查詢，如 C++11 的 std::unordered_map（unordered_multimap 支持重複鍵）。

設一個對象有 n 個成員，數據結構的容量是 m，n ? m，那麼一些常用操作的時間／空間複雜度如下：

在 ECMA-404 標準中，並沒有規定對象中每個成員的鍵一定要唯一的，也沒有規定是否需要維持成員的次序。

為了簡單起見，我們的 leptjson 選擇用動態數組的方案。我們將在單元八才加入動態功能，所以這單元中，每個對象僅僅是成員的數組。那麼它跟上一單元的數組非常接近：

typedef struct lept_value lept_value;typedef struct lept_member lept_member;struct lept_value { union { struct { lept_member* m; size_t size; }o; struct { lept_value* e; size_t size; }a; struct { char* s; size_t len; }s; double n; }u; lept_type type;};struct lept_member { char* k; size_t klen; /* member key string, key string length */ lept_value v; /* member value */};

成員結構 lept_member 是一個 lept_value 加上鍵的字元串。如同 JSON 字元串的值，我們也需要同時保留字元串的長度，因為字元串本身可能包含空字元 u0000。

在這單元中，我們僅添加了最基本的訪問函數，用於撰寫單元測試：

size_t lept_get_object_size(const lept_value* v);const char* lept_get_object_key(const lept_value* v, size_t index);size_t lept_get_object_key_length(const lept_value* v, size_t index);lept_value* lept_get_object_value(const lept_value* v, size_t index);

在軟體開發過程中，許多時候，選擇合適的數據結構後已等於完成一半工作。沒有完美的數據結構，所以最好考慮多一些應用的場合，看看時間／空間複雜度以至相關係數是否合適。

接下來，我們就可以著手實現。

3. 重構字元串解析

在軟體工程中，代碼重構（code refactoring）是指在不改變軟體外在行為時，修改代碼以改進結構。代碼重構十分依賴於單元測試，因為我們是通過單元測試去維護代碼的正確性。有了足夠的單元測試，我們可以放膽去重構，嘗試並評估不同的改進方式，找到合乎心意而且能通過單元測試的改動，我們才提交它。

我們知道，成員的鍵也是一個 JSON 字元串，然而，我們不使用 lept_value 存儲鍵，因為這樣會浪費了當中 type 這個無用的欄位。由於 lept_parse_string() 是直接地把解析的結果寫進一個 lept_value，所以我們先用「提取方法（extract method，見下注）」的重構方式，把解析 JSON 字元串及寫入 lept_value 分拆成兩部分：

/* 解析 JSON 字元串，把結果寫入 str 和 len *//* str 指向 c->stack 中的元素，需要在 c->stack */static int lept_parse_string_raw(lept_context* c, char** str, size_t* len) { /* odo */}static int lept_parse_string(lept_context* c, lept_value* v) { int ret; char* s; size_t len; if ((ret = lept_parse_string_raw(c, &s, &len)) == LEPT_PARSE_OK) lept_set_string(v, s, len); return ret;}

這樣的話，我們實現對象的解析時，就可以使用 lept_parse_string_raw()　來解析 JSON 字元串，然後把結果複製至 lept_member 的 k 和 klen 欄位。

註：在 Fowler 的經典著作 [1] 中，把各種重構方式分門別類，每個方式都有詳細的步驟說明。由於書中以 Java 為例子，所以方式的名稱使用了 Java 的述語，例如方法（method）。在 C 語言中，「提取方法」其實應該稱為「提取函數」。

[1] Fowler, Martin. Refactoring: improving the design of existing code. Pearson Education India, 2009. 中譯本：熊節譯，《重構——改善既有代碼的設計》，人民郵電出版社，2010年。

4. 實現

解析對象與解析數組非常相似，所以我留空了幾段作為練習。在解析數組時，我們把當前的元素以 lept_value 壓入棧中，而在這裡，我們則是以 lept_member 壓入：

static int lept_parse_object(lept_context* c, lept_value* v) { size_t size; lept_member m; int ret; EXPECT(c, {); lept_parse_whitespace(c); if (*c->json == }) { c->json++; v->type = LEPT_OBJECT; v->u.o.m = 0; v->u.o.size = 0; return LEPT_PARSE_OK; } m.k = NULL; size = 0; for (;;) { lept_init(&m.v); /* odo parse key to m.k, m.klen */ /* odo parse ws colon ws */ /* parse value */ if ((ret = lept_parse_value(c, &m.v)) != LEPT_PARSE_OK) break; memcpy(lept_context_push(c, sizeof(lept_member)), &m, sizeof(lept_member)); size++; m.k = NULL; /* ownership is transferred to member on stack */ /* odo parse ws [comma | right-curly-brace] ws */ } /* odo Pop and free members on the stack */ return ret;}

要注意的是，我們要為 m.k 分配內存去存儲鍵的字元串，若在整個對象解析時發生錯誤，也要記得釋放棧中的 lept_member 的 k。

我們為解析對象定義了幾個新的錯誤碼：

enum { /* ... */ LEPT_PARSE_MISS_KEY, LEPT_PARSE_MISS_COLON, LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET};

在此不再贅述它們的意義了，可從以下的單元測試看到例子：

static void test_parse_miss_key() { TEST_ERROR(LEPT_PARSE_MISS_KEY, "{:1,"); TEST_ERROR(LEPT_PARSE_MISS_KEY, "{1:1,"); TEST_ERROR(LEPT_PARSE_MISS_KEY, "{true:1,"); TEST_ERROR(LEPT_PARSE_MISS_KEY, "{false:1,"); TEST_ERROR(LEPT_PARSE_MISS_KEY, "{null:1,"); TEST_ERROR(LEPT_PARSE_MISS_KEY, "{[]:1,"); TEST_ERROR(LEPT_PARSE_MISS_KEY, "{{}:1,"); TEST_ERROR(LEPT_PARSE_MISS_KEY, "{"a":1,");}static void test_parse_miss_colon() { TEST_ERROR(LEPT_PARSE_MISS_COLON, "{"a"}"); TEST_ERROR(LEPT_PARSE_MISS_COLON, "{"a","b"}");}static void test_parse_miss_comma_or_curly_bracket() { TEST_ERROR(LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET, "{"a":1"); TEST_ERROR(LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET, "{"a":1]"); TEST_ERROR(LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET, "{"a":1 "b""); TEST_ERROR(LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET, "{"a":{}");}

5. 總結與練習

在本單元中，除了談及 JSON 對象的語法、可選的數據結構、實現方式，我們也輕輕談及了重構的概念。有賴於測試驅動開發（TDD），我們可以不斷重塑軟體的內部結構。

完成這次練習之後，恭喜你，你已經完整地實現了一個符合標準的 JSON 解析器了。之後我們會完成更簡單的生成器及其他訪問功能。

由於對象和數組的相似性，此單元留空了較多實現部分作為練習：

1. 依第 3 節所述，重構 lept_parse_string()。重構前運行單元測試，重構後確保單元測試仍保持通過。
2. 打開 test.c 中兩個 #if 0，運行單元測試，證實單元測試不通過。然後實現 lept_parse_object() 中的 odo 部分。驗證實現能通過單元測試。
3. 使用工具檢測內存泄漏，解決它們。

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