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

02-03

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

1. 編寫 test_parse_array() 單元測試

這個練習純粹為了熟習數組的訪問 API。新增的第一個 JSON 只需平凡的檢測。第二個 JSON 有特定模式，第 i 個子數組的長度為 i，每個子數組的第 j 個元素是數字值 j，所以可用兩層 for 循環測試。

static void test_parse_array() {n size_t i, j;n lept_value v;nn /* ... */nn lept_init(&v);n EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "[ null , false , true , 123 , "abc" ]"));n EXPECT_EQ_INT(LEPT_ARRAY, lept_get_type(&v));n EXPECT_EQ_SIZE_T(5, lept_get_array_size(&v));n EXPECT_EQ_INT(LEPT_NULL, lept_get_type(lept_get_array_element(&v, 0)));n EXPECT_EQ_INT(LEPT_FALSE, lept_get_type(lept_get_array_element(&v, 1)));n EXPECT_EQ_INT(LEPT_TRUE, lept_get_type(lept_get_array_element(&v, 2)));n EXPECT_EQ_INT(LEPT_NUMBER, lept_get_type(lept_get_array_element(&v, 3)));n EXPECT_EQ_INT(LEPT_STRING, lept_get_type(lept_get_array_element(&v, 4)));n EXPECT_EQ_DOUBLE(123.0, lept_get_number(lept_get_array_element(&v, 3)));n EXPECT_EQ_STRING("abc", lept_get_string(lept_get_array_element(&v, 4)), lept_get_string_length(lept_get_array_element(&v, 4)));n lept_free(&v);nn lept_init(&v);n EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "[ [ ] , [ 0 ] , [ 0 , 1 ] , [ 0 , 1 , 2 ] ]"));n EXPECT_EQ_INT(LEPT_ARRAY, lept_get_type(&v));n EXPECT_EQ_SIZE_T(4, lept_get_array_size(&v));n for (i = 0; i < 4; i++) {n lept_value* a = lept_get_array_element(&v, i);n EXPECT_EQ_INT(LEPT_ARRAY, lept_get_type(a));n EXPECT_EQ_SIZE_T(i, lept_get_array_size(a));n for (j = 0; j < i; j++) {n lept_value* e = lept_get_array_element(a, j);n EXPECT_EQ_INT(LEPT_NUMBER, lept_get_type(e));n EXPECT_EQ_DOUBLE((double)j, lept_get_number(e));n }n }n lept_free(&v);n}n

2. 解析空白字元

按現時的 lept_parse_array() 的編寫方式，需要加入 3 個 lept_parse_whitespace() 調用，分別是解析 [ 之後，元素之後，以及 , 之後：

static int lept_parse_array(lept_context* c, lept_value* v) {n /* ... */n EXPECT(c, [);n lept_parse_whitespace(c);n /* ... */n for (;;) {n /* ... */n if ((ret = lept_parse_value(c, &e)) != LEPT_PARSE_OK)n return ret;n /* ... */n lept_parse_whitespace(c);n if (*c->json == ,) {n c->json++;n lept_parse_whitespace(c);n }n /* ... */n }n}n

3. 內存泄漏

成功測試那 3 個 JSON 後，使用內存泄漏檢測工具會發現 lept_parse_array() 用 malloc()分配的內存沒有被釋放：

==154== 124 (120 direct, 4 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 4n==154== at 0x4C28C20: malloc (vg_replace_malloc.c:296)n==154== by 0x409D82: lept_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x409E91: lept_parse_value (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x409F14: lept_parse (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x405261: test_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x408C72: test_parse (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x40916A: main (in /json-tutorial/tutorial05/build/leptjson_test)n==154== n==154== 240 (96 direct, 144 indirect) bytes in 1 blocks are definitely lost in loss record 4 of 4n==154== at 0x4C28C20: malloc (vg_replace_malloc.c:296)n==154== by 0x409D82: lept_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x409E91: lept_parse_value (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x409F14: lept_parse (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x40582C: test_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x408C72: test_parse (in /json-tutorial/tutorial05/build/leptjson_test)n==154== by 0x40916A: main (in /json-tutorial/tutorial05/build/leptjson_test)n

很明顯，有 malloc() 就要有對應的 free()。正確的釋放位置應該放置在 lept_free()，當值被釋放時，該值擁有的內存也在那裡釋放。之前字元串的釋放也是放在這裡：

void lept_free(lept_value* v) {n assert(v != NULL);n if (v->type == LEPT_STRING)n free(v->u.s.s);n v->type = LEPT_NULL;n}n

但對於數組，我們應該先把數組內的元素通過遞歸調用 lept_free() 釋放，然後才釋放本身的 v->u.a.e：

void lept_free(lept_value* v) {n size_t i;n assert(v != NULL);n switch (v->type) {n case LEPT_STRING:n free(v->u.s.s);n break;n case LEPT_ARRAY:n for (i = 0; i < v->u.a.size; i++)n lept_free(&v->u.a.e[i]);n free(v->u.a.e);n break;n default: break;n }n v->type = LEPT_NULL;n}n

修改之後，再運行內存泄漏檢測工具，確保問題已被修正。

4. 解析錯誤時的內存處理

遇到解析錯誤時，我們可能在之前已壓入了一些值在自定堆棧上。如果沒有處理，最後會在 lept_parse() 中發現堆棧上還有一些值，做成斷言失敗。所以，遇到解析錯誤時，我們必須彈出並釋放那些值。

在 lept_parse_array 中，原本遇到解析失敗時，會直接返回錯誤碼。我們把它改為 break 離開循環，在循環結束後的地方用 lept_free() 釋放從堆棧彈出的值，然後才返回錯誤碼：

static int lept_parse_array(lept_context* c, lept_value* v) {n /* ... */n for (;;) {n /* ... */n if ((ret = lept_parse_value(c, &e)) != LEPT_PARSE_OK)n break;n /* ... */n if (*c->json == ,) {n /* ... */n }n else if (*c->json == ]) {n /* ... */n }n else {n ret = LEPT_PARSE_MISS_COMMA_OR_SQUARE_BRACKET;n break;n }n }n /* Pop and free values on the stack */n for (i = 0; i < size; i++)n lept_free((lept_value*)lept_context_pop(c, sizeof(lept_value)));n return ret;n}n

5. bug 的解釋

這個 bug 源於壓棧時，會獲得一個指針 e，指向從堆棧分配到的空間：

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

然後，我們把這個指針調用 lept_parse_value(c, e)，這裡會出現問題，因為 lept_parse_value() 及之下的函數都需要調用 lept_context_push()，而 lept_context_push() 在發現棧滿了的時候會用 realloc() 擴容。這時候，我們上層的e 就會失效，變成一個懸掛指針（dangling pointer），而且 lept_parse_value(c, e) 會通過這個指針寫入解析結果，造成非法訪問。

在使用 C++ 容器時，也會遇到類似的問題。從容器中取得的迭代器（iterator）後，如果改動容器內容，之前的迭代器會失效。這裡的懸掛指針問題也是相同的。

但這種 bug 有時可能在簡單測試中不能自動發現，因為問題只有堆棧滿了才會出現。從測試的角度看，我們需要一些壓力測試（stress test），測試更大更複雜的數據。但從編程的角度看，我們要謹慎考慮變數的生命周期，盡量從編程階段避免出現問題。例如把 lept_context_push() 的 API 改為：

static void lept_context_push(n lept_context* c, const void* data, size_t size);n

這樣就確把數據壓入棧內，避免了返回指針的生命周期問題。但我們之後會發現，原來的 API 設計在一些情況會更方便一些，例如在把字元串值轉化（stringify）為 JSON 時，我們可以預先在堆棧分配字元串所需的最大空間，而當時是未有數據填充進去的。

無論如何，我們編程時都要考慮清楚變數的生命周期，特別是指針的生命周期。

6. 總結

經過對數組的解析，我們也了解到如何利用遞歸處理複合型的數據類型解析。與一些用鏈表或自動擴展的動態數組的實現比較，我們利用了自定義堆棧作為緩衝區，能分配最緊湊的數組作存儲之用，會比其他實現更省內存。我們完成了數組類型後，只餘下對象類型了。

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