从零开始的 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 中提出，让所有人一起讨论。