• 从零开始的 JSON 库教程（五）：解析数组解答篇
    • 1. 编写 test_parse_array() 单元测试
    • 2. 解析空白字符
    • 3. 内存泄漏
    • 4. 解析错误时的内存处理
    • 5. bug 的解释
    • 6. 总结

    从零开始的 JSON 库教程（五）：解析数组解答篇

    • Milo Yip
    • 2016/10/13

    本文是《从零开始的 JSON 库教程》的第五个单元解答篇。解答代码位于 json-tutorial/tutorial05_answer。

    1. 编写 test_parse_array() 单元测试

    这个练习纯粹为了熟习数组的访问 API。新增的第一个 JSON 只需平凡的检测。第二个 JSON 有特定模式，第 i 个子数组的长度为 i，每个子数组的第 j 个元素是数字值 j，所以可用两层 for 循环测试。

    1. static void test_parse_array() {
    2.     size_t i, j;
    3.     lept_value v;
    5.     /* ... */
    7.     lept_init(&v);
    8.     EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "[ null , false , true , 123 , \"abc\" ]"));
    9.     EXPECT_EQ_INT(LEPT_ARRAY, lept_get_type(&v));
    10.     EXPECT_EQ_SIZE_T(5, lept_get_array_size(&v));
    11.     EXPECT_EQ_INT(LEPT_NULL,   lept_get_type(lept_get_array_element(&v, 0)));
    12.     EXPECT_EQ_INT(LEPT_FALSE,  lept_get_type(lept_get_array_element(&v, 1)));
    13.     EXPECT_EQ_INT(LEPT_TRUE,   lept_get_type(lept_get_array_element(&v, 2)));
    14.     EXPECT_EQ_INT(LEPT_NUMBER, lept_get_type(lept_get_array_element(&v, 3)));
    15.     EXPECT_EQ_INT(LEPT_STRING, lept_get_type(lept_get_array_element(&v, 4)));
    16.     EXPECT_EQ_DOUBLE(123.0, lept_get_number(lept_get_array_element(&v, 3)));
    17.     EXPECT_EQ_STRING("abc", lept_get_string(lept_get_array_element(&v, 4)), lept_get_string_length(lept_get_array_element(&v, 4)));
    18.     lept_free(&v);
    20.     lept_init(&v);
    21.     EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "[ [ ] , [ 0 ] , [ 0 , 1 ] , [ 0 , 1 , 2 ] ]"));
    22.     EXPECT_EQ_INT(LEPT_ARRAY, lept_get_type(&v));
    23.     EXPECT_EQ_SIZE_T(4, lept_get_array_size(&v));
    24.     for (i = 0; i < 4; i++) {
    25.         lept_value* a = lept_get_array_element(&v, i);
    26.         EXPECT_EQ_INT(LEPT_ARRAY, lept_get_type(a));
    27.         EXPECT_EQ_SIZE_T(i, lept_get_array_size(a));
    28.         for (j = 0; j < i; j++) {
    29.             lept_value* e = lept_get_array_element(a, j);
    30.             EXPECT_EQ_INT(LEPT_NUMBER, lept_get_type(e));
    31.             EXPECT_EQ_DOUBLE((double)j, lept_get_number(e));
    32.         }
    33.     }
    34.     lept_free(&v);
    35. }

    2. 解析空白字符

    按现时的 lept_parse_array() 的编写方式，需要加入 3 个 lept_parse_whitespace() 调用，分别是解析 [ 之后，元素之后，以及 , 之后：

    1. static int lept_parse_array(lept_context* c, lept_value* v) {
    2.     /* ... */
    3.     EXPECT(c, '[');
    4.     lept_parse_whitespace(c);
    5.     /* ... */
    6.     for (;;) {
    7.         /* ... */
    8.         if ((ret = lept_parse_value(c, &e)) != LEPT_PARSE_OK)
    9.             return ret;
    10.         /* ... */
    11.         lept_parse_whitespace(c);
    12.         if (*c->json == ',') {
    13.             c->json++;
    14.             lept_parse_whitespace(c);
    15.         }
    16.         /* ... */
    17.     }
    18. }

    3. 内存泄漏

    成功测试那 3 个 JSON 后，使用内存泄漏检测工具会发现 lept_parse_array() 用 malloc()分配的内存没有被释放：

    1. ==154== 124 (120 direct, 4 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 4
    2. ==154==    at 0x4C28C20: malloc (vg_replace_malloc.c:296)
    3. ==154==    by 0x409D82: lept_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)
    4. ==154==    by 0x409E91: lept_parse_value (in /json-tutorial/tutorial05/build/leptjson_test)
    5. ==154==    by 0x409F14: lept_parse (in /json-tutorial/tutorial05/build/leptjson_test)
    6. ==154==    by 0x405261: test_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)
    7. ==154==    by 0x408C72: test_parse (in /json-tutorial/tutorial05/build/leptjson_test)
    8. ==154==    by 0x40916A: main (in /json-tutorial/tutorial05/build/leptjson_test)
    9. ==154== 
    10. ==154== 240 (96 direct, 144 indirect) bytes in 1 blocks are definitely lost in loss record 4 of 4
    11. ==154==    at 0x4C28C20: malloc (vg_replace_malloc.c:296)
    12. ==154==    by 0x409D82: lept_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)
    13. ==154==    by 0x409E91: lept_parse_value (in /json-tutorial/tutorial05/build/leptjson_test)
    14. ==154==    by 0x409F14: lept_parse (in /json-tutorial/tutorial05/build/leptjson_test)
    15. ==154==    by 0x40582C: test_parse_array (in /json-tutorial/tutorial05/build/leptjson_test)
    16. ==154==    by 0x408C72: test_parse (in /json-tutorial/tutorial05/build/leptjson_test)
    17. ==154==    by 0x40916A: main (in /json-tutorial/tutorial05/build/leptjson_test)

    很明显，有 malloc() 就要有对应的 free()。正确的释放位置应该放置在 lept_free()，当值被释放时，该值拥有的内存也在那里释放。之前字符串的释放也是放在这里：

    1. void lept_free(lept_value* v) {
    2.     assert(v != NULL);
    3.     if (v->type == LEPT_STRING)
    4.         free(v->u.s.s);
    5.     v->type = LEPT_NULL;
    6. }

    但对于数组，我们应该先把数组内的元素通过递归调用 lept_free() 释放，然后才释放本身的 v->u.a.e：

    1. void lept_free(lept_value* v) {
    2.     size_t i;
    3.     assert(v != NULL);
    4.     switch (v->type) {
    5.         case LEPT_STRING:
    6.             free(v->u.s.s);
    7.             break;
    8.         case LEPT_ARRAY:
    9.             for (i = 0; i < v->u.a.size; i++)
    10.                 lept_free(&v->u.a.e[i]);
    11.             free(v->u.a.e);
    12.             break;
    13.         default: break;
    14.     }
    15.     v->type = LEPT_NULL;
    16. }

    修改之后，再运行内存泄漏检测工具，确保问题已被修正。

    4. 解析错误时的内存处理

    遇到解析错误时，我们可能在之前已压入了一些值在自定义堆栈上。如果没有处理，最后会在 lept_parse() 中发现堆栈上还有一些值，做成断言失败。所以，遇到解析错误时，我们必须弹出并释放那些值。

    在 lept_parse_array 中，原本遇到解析失败时，会直接返回错误码。我们把它改为 break 离开循环，在循环结束后的地方用 lept_free() 释放从堆栈弹出的值，然后才返回错误码：

    1. static int lept_parse_array(lept_context* c, lept_value* v) {
    2.     /* ... */
    3.     for (;;) {
    4.         /* ... */
    5.         if ((ret = lept_parse_value(c, &e)) != LEPT_PARSE_OK)
    6.             break;
    7.         /* ... */
    8.         if (*c->json == ',') {
    9.             /* ... */
    10.         }
    11.         else if (*c->json == ']') {
    12.             /* ... */
    13.         }
    14.         else {
    15.             ret = LEPT_PARSE_MISS_COMMA_OR_SQUARE_BRACKET;
    16.             break;
    17.         }
    18.     }
    19.     /* Pop and free values on the stack */
    20.     for (i = 0; i < size; i++)
    21.         lept_free((lept_value*)lept_context_pop(c, sizeof(lept_value)));
    22.     return ret;
    23. }

    5. bug 的解释

    这个 bug 源于压栈时，会获得一个指针 e，指向从堆栈分配到的空间：

    1.     for (;;) {
    2.         /* bug! */
    3.         lept_value* e = lept_context_push(c, sizeof(lept_value));
    4.         lept_init(e);
    5.         size++;
    6.         if ((ret = lept_parse_value(c, e)) != LEPT_PARSE_OK)
    7.             return ret;
    8.         /* ... */
    9.     }

    然后，我们把这个指针调用 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 改为：

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

    这样就确把数据压入栈内，避免了返回指针的生命周期问题。但我们之后会发现，原来的 API 设计在一些情况会更方便一些，例如在把字符串值转化（stringify）为 JSON 时，我们可以预先在堆栈分配字符串所需的最大空间，而当时是未有数据填充进去的。

    无论如何，我们编程时都要考虑清楚变量的生命周期，特别是指针的生命周期。

    6. 总结

    经过对数组的解析，我们也了解到如何利用递归处理复合型的数据类型解析。与一些用链表或自动扩展的动态数组的实现比较，我们利用了自定义堆栈作为缓冲区，能分配最紧凑的数组作存储之用，会比其他实现更省内存。我们完成了数组类型后，只余下对象类型了。

    如果你遇到问题，有不理解的地方，或是有建议，都欢迎在评论或 issue 中提出，让所有人一起讨论。