從零開始的 JSON 庫教程（五）：解析數組

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

本單元內容：

1. JSON 數組
2. 數據結構
3. 解析過程
4. 實現
5. 總結與練習

（題圖 Photo by Sean Brown）

1. JSON 數組

從零到這第五單元，我們終於要解析一個 JSON 的複合數據類型了。一個 JSON 數組可以包含零至多個元素，而這些元素也可以是數組類型。換句話說，我們可以表示嵌套（nested）的數據結構。先來看看 JSON 數組的語法：

array = %x5B ws [ value *( ws %x2C ws value ) ] ws %x5Dn

當中，%x5B 是左中括弧 [，%x2C 是逗號 ,，%x5D 是右中括弧 ] ，ws 是空白字元。一個數組可以包含零至多個值，以逗號分隔，例如 []、[1,2,true]、[[1,2],[3,4],"abc"] 都是合法的數組。但注意 JSON 不接受末端額外的逗號，例如 [1,2,] 是不合法的（許多編程語言如 C/C++、Javascript、Java、C# 都容許數組初始值包含末端逗號）。

JSON 數組的語法很簡單，實現的難點不在語法上，而是怎樣管理內存。

2. 數據結構

首先，我們需要設計存儲 JSON 數組類型的數據結構。

JSON 數組存儲零至多個元素，最簡單就是使用 C 語言的數組。數組最大的好處是能以 用索引訪問任意元素，次要好處是內存布局緊湊，省內存之餘還有高緩存一致性（cache coherence）。但數組的缺點是不能快速插入元素，而且我們在解析 JSON 數組的時候，還不知道應該分配多大的數組才合適。

另一個選擇是鏈表（linked list），它的最大優點是可快速地插入元素（開端、末端或中間），但需要以 時間去經索引取得內容。如果我們只需順序遍歷，那麼是沒有問題的。還有一個小缺點，就是相對數組而言，鏈表在存儲每個元素時有額外內存開銷（存儲下一節點的指針），而且遍歷時元素所在的內存可能不連續，令緩存不命中（cache miss）的機會上升。

我見過一些 JSON 庫選擇了鏈表，而這裡則選擇了數組。我們將會通過之前在解析字元串時實現的堆棧，來解決解析 JSON 數組時未知數組大小的問題。

決定之後，我們在 lept_value 的 union 中加入數組的結構：

typedef struct lept_value lept_value;nnstruct lept_value {n union {n struct { lept_value* e; size_t size; }a; /* array */n struct { char* s; size_t len; }s;n double n;n }u;n lept_type type;n};n

由於 lept_value 內使用了自身類型的指針，我們必須前向聲明（forward declare）此類型。

另外，注意這裡 size 是元素的個數，不是位元組單位。我們增加兩個 API 去訪問 JSON 數組類型的值：

size_t lept_get_array_size(const lept_value* v) {n assert(v != NULL && v->type == LEPT_ARRAY);n return v->u.a.size;n}nnlept_value* lept_get_array_element(const lept_value* v, size_t index) {n assert(v != NULL && v->type == LEPT_ARRAY);n assert(index < v->u.a.size);n return &v->u.a.e[index];n}n

暫時我們不考慮增刪數組元素，這些功能留待第八單元討論。

然後，我們寫一個單元測試去試用這些 API（練習需要更多測試）。

#if defined(_MSC_VER)n#define EXPECT_EQ_SIZE_T(expect, actual) EXPECT_EQ_BASE((expect) == (actual), (size_t)expect, (size_t)actual, "%Iu")n#elsen#define EXPECT_EQ_SIZE_T(expect, actual) EXPECT_EQ_BASE((expect) == (actual), (size_t)expect, (size_t)actual, "%zu")n#endifnnstatic void test_parse_array() {n lept_value v;nn lept_init(&v);n EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "[ ]"));n EXPECT_EQ_INT(LEPT_ARRAY, lept_get_type(&v));n EXPECT_EQ_SIZE_T(0, lept_get_array_size(&v));n lept_free(&v);n}n

在之前的單元中，作者已多次重申，C 語言的數組大小應該使用 size_t 類型。因為我們要驗證 lept_get_array_size() 返回值是否正確，所以再為單元測試框架添加一個宏 EXPECT_EQ_SIZE_T。麻煩之處在於，ANSI C（C89）並沒有的 size_t列印方法，在 C99 則加入了 "%zu"，但 VS2015 中才有，之前的 VC 版本使用非標準的 "%Iu"。因此，上面的代碼使用條件編譯去區分 VC 和其他編譯器。雖然這部分不跨平台也不是 ANSI C 標準，但它只在測試程序中，不太影響程序庫的跨平台性。

3. 解析過程

我們在解析 JSON 字元串時，因為在開始時不能知道字元串的長度，而又需要進行轉義，所以需要一個臨時緩衝區去存儲解析後的結果。我們為此實現了一個動態增長的堆棧，可以不斷壓入字元，最後一次性把整個字元串彈出，複製至新分配的內存之中。

對於 JSON 數組，我們也可以用相同的方法，而且，我們可以用同一個堆棧！我們只需要把每個解析好的元素壓入堆棧，解析到數組結束時，再一次性把所有元素彈出，複製至新分配的內存之中。

但和字元串有點不一樣，如果把 JSON 當作一棵樹的數據結構，JSON 字元串是葉節點，而 JSON 數組是中間節點。在葉節點的解析函數中，我們怎樣使用那個堆棧也可以，只要最後還原就好了。但對於數組這樣的中間節點，共用這個堆棧沒問題么？

答案是：只要在解析函數結束時還原堆棧的狀態，就沒有問題。為了直觀地了解這個解析過程，我們用連環圖去展示 ["abc",[1,2],3] 的解析過程。

首先，我們遇到 [，進入 lept_parse_array()：

生成一個臨時的 lept_value，用於存儲之後的元素。我們再調用 lept_parse_value() 去解析這個元素值，因為遇到 " 進入 lept_parse_string()：

在 lept_parse_string() 中，不斷解析字元直至遇到 "，過程中把每個字元壓棧：

最後在 lept_parse_string() 中，把棧上 3 個字元彈出，分配內存，生成字元串值：

返回上一層 lept_parse_array()，把臨時元素壓棧：

然後我們再遇到 [，進入另一個 lept_parse_array()。它發現第一個元素是數字類型，所認調用 lept_parse_number()，生成一個臨時的元素值：

之後把該臨時的元素值壓棧：

接著再解析第二個元素。我們遇到了 ]，從棧上彈出 2 個元素，分配內存，生成數組（虛線代表是連續的內存）：

那個數組是上層數組的元素，我們把它壓棧。現時棧內已有兩個元素，我們再繼續解析下一個元素：

最後，遇到了 ]，可以彈出棧內 3 個元素，分配內存，生成數組：

4. 實現

經過這個詳細的圖解，實現 lept_parse_array() 應該沒有難度。以下是半製成品：

static int lept_parse_value(lept_context* c, lept_value* v);/*前向聲明*/nnstatic int lept_parse_array(lept_context* c, lept_value* v) {n size_t size = 0;n int ret;n EXPECT(c, [);n if (*c->json == ]) {n c->json++;n v->type = LEPT_ARRAY;n v->u.a.size = 0;n v->u.a.e = NULL;n return LEPT_PARSE_OK;n }n for (;;) {n lept_value e;n lept_init(&e);n if ((ret = lept_parse_value(c, &e)) != LEPT_PARSE_OK)n return ret;n memcpy(lept_context_push(c, sizeof(lept_value)), &e, sizeof(lept_value));n size++;n if (*c->json == ,)n c->json++;n else if (*c->json == ]) {n c->json++;n v->type = LEPT_ARRAY;n v->u.a.size = size;n size *= sizeof(lept_value);n memcpy(v->u.a.e = (lept_value*)malloc(size), lept_context_pop(c, size), size);n return LEPT_PARSE_OK;n }n elsen return LEPT_PARSE_MISS_COMMA_OR_SQUARE_BRACKET;n }n}nnstatic int lept_parse_value(lept_context* c, lept_value* v) {n switch (*c->json) {n /* ... */n case [: return lept_parse_array(c, v);n }n}n

簡單說明的話，就是在循環中建立一個臨時值（lept_value e），然後調用 lept_parse_value() 去把元素解析至這個臨時值，完成後把臨時值壓棧。當遇到 ]，把棧內的元素彈出，分配內存，生成數組值。

注意到，lept_parse_value() 會調用 lept_parse_array()，而 lept_parse_array() 又會調用 lept_parse_value()，這是互相引用，所以必須要加入函數前向聲明。

最後，我想告訴同學，實現這個函數時，我曾經製造一個不明顯的 bug。這個函數有兩個 memcpy()，第一個「似乎」是可以避免的，先壓棧取得元素的指針，給 lept_parse_value：

for (;;) {n /* bug! */n lept_value* e = lept_context_push(c, sizeof(lept_value));n lept_init(e);n size++;n if ((ret = lept_parse_value(c, e)) != LEPT_PARSE_OK)n return ret;n /* ... */n }n

這種寫法為什麼會有 bug？這是第 5 條練習題。

5. 總結與練習

1. 編寫 test_parse_array() 單元測試，解析以下 2 個 JSON。由於數組是複合的類型，不能使用一個宏去測試結果，請使用各個 API 檢查解析後的內容。
   [ null , false , true , 123 , "abc" ]

   [ [ ] , [ 0 ] , [ 0 , 1 ] , [ 0 , 1 , 2 ] ]

2. 現時的測試結果應該是失敗的，因為 lept_parse_array() 里沒有處理空白字元，加進合適的lept_parse_whitespace() 令測試通過。

3. 使用第三單元解答篇介紹的檢測內存泄漏工具，會發現測試中有內存泄漏。很明顯在 lept_parse_array() 中使用到malloc() 分配內存，但卻沒有對應的 free()。應該在哪裡釋放內存？修改代碼，使工具不再檢測到相關的內存泄漏。

4. 開啟 test.c 中兩處被 #if 0 ... #endif 關閉的測試，本來 test_parse_array() 已經能處理這些測試。然而，運行時會發現 Assertion failed: (c.top == 0) 斷言失敗。這是由於，當錯誤發生時，仍然有一些臨時值在堆棧里，既沒有放進數組，也沒有被釋放。修改 test_parse_array()，當遇到錯誤時，從堆棧中彈出並釋放那些臨時值，然後才返回錯誤碼。

5. 第 4 節那段代碼為什麼會有 bug？

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