跟着做一个JSON解析器（六）

跟着github上的项目json-tutorial完成一个json解析器。本文对应该项目的第四单元，重点在解析json对象类型。

👉原项目地址

一、JSON 对象

此单元是本教程最后一个关于 JSON 解析器的部分。JSON 对象和 JSON 数组非常相似，区别包括 JSON 对象以花括号 {}（U+007B、U+007D）包裹表示，另外 JSON 对象由对象成员（member）组成，而 JSON 数组由 JSON 值组成。所谓对象成员，就是键值对，键必须为 JSON 字符串，然后值是任何 JSON 值，中间以冒号 :（U+003A）分隔。完整语法如下：

1
2
member = string ws %x3A ws value
object = %x7B ws [ member *( ws %x2C ws member ) ] ws %x7D

二、数据结构

要表示键值对的集合，有很多数据结构可供选择，例如：

  • 动态数组（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，那么一些常用操作的时间／空间复杂度如下：

动态数组 有序动态数组 平衡树 哈希表
有序 否 是 是 否
自定成员次序 可 否 否 否
初始化 n 个成员 O(n) O(n log n) O(n log n) 平均 O(n)、最坏 O(n^2)
加入成员 分摊 O(1) O(n) O(log n) 平均 O(1)、最坏 O(n)
移除成员 O(n) O(n) O(log n) 平均 O(1)、最坏 O(n)
查询成员 O(n) O(log n) O(log n) 平均 O(1)、最坏 O(n)
遍历成员 O(n) O(n) O(n) O(m)
检测对象相等 O(n^2) O(n) O(n) 平均 O(n)、最坏 O(n^2)
空间 O(m) O(m) O(n) O(m)

在 ECMA-404 标准中，并没有规定对象中每个成员的键一定要唯一的，也没有规定是否需要维持成员的次序。

为了简单起见，我们的 leptjson 选择用动态数组的方案。我们将在单元八才加入动态功能，所以这单元中，每个对象仅仅是成员的数组。那么它跟上一单元的数组非常接近：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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。

在这单元中，我们仅添加了最基本的访问函数，用于撰写单元测试：

1
2
3
4
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);

在软件开发过程中，许多时候，选择合适的数据结构后已等于完成一半工作。没有完美的数据结构，所以最好考虑多一些应用的场合，看看时间／空间复杂度以至相关系数是否合适。

接下来，我们就可以着手实现。

三、重构字符串解析

在软件工程中，代码重构（code refactoring）是指在不改变软件外在行为时，修改代码以改进结构。代码重构十分依赖于单元测试，因为我们是通过单元测试去维护代码的正确性。有了足够的单元测试，我们可以放胆去重构，尝试并评估不同的改进方式，找到合乎心意而且能通过单元测试的改动，我们才提交它。

我们知道，成员的键也是一个 JSON 字符串，然而，我们不使用 lept_value 存储键，因为这样会浪费了当中 type 这个无用的字段。由于 lept_parse_string() 是直接地把解析的结果写进一个 lept_value，所以我们先用「提取方法（extract method，见下注）」的重构方式，把解析 JSON 字符串及写入 lept_value 分拆成两部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 解析 JSON 字符串，把结果写入 str 和 len */
/* str 指向 c->stack 中的元素，需要在 c->stack  */
static int lept_parse_string_raw(lept_context* c, char** str, size_t* len) {
    /* \todo */
}

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年。

四、实现

解析对象与解析数组非常相似，所以我留空了几段作为练习。在解析数组时，我们把当前的元素以 lept_value 压入栈中，而在这里，我们则是以 lept_member 压入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);
        /* \todo parse key to m.k, m.klen */
        /* \todo 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 */
        /* \todo parse ws [comma | right-curly-brace] ws */
    }
    /* \todo Pop and free members on the stack */
    return ret;
}

要注意的是，我们要为 m.k 分配内存去存储键的字符串，若在整个对象解析时发生错误，也要记得释放栈中的 lept_member 的 k。

我们为解析对象定义了几个新的错误码：

1
2
3
4
5
6
enum {
    /* ... */
    LEPT_PARSE_MISS_KEY,
    LEPT_PARSE_MISS_COLON,
    LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET
};

在此不再赘述它们的意义了，可从以下的单元测试看到例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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\":{}");
}

五、总结与练习

在本单元中，除了谈及 JSON 对象的语法、可选的数据结构、实现方式，我们也轻轻谈及了重构的概念。有赖于测试驱动开发（TDD），我们可以不断重塑软件的内部结构。

完成这次练习之后，恭喜你，你已经完整地实现了一个符合标准的 JSON 解析器了。之后我们会完成更简单的生成器及其他访问功能。

由于对象和数组的相似性，此单元留空了较多实现部分作为练习：

  1. 依第 3 节所述，重构 lept_parse_string()。重构前运行单元测试，重构后确保单元测试仍保持通过。

这个「提取方法」重构练习很简单，只需要把原来调用 lept_set_string 的地方，改为写入参数变量。因此，原来的 lept_parse_string() 和 答案中的 lept_parse_string_raw() 的 diff 仅是两处：

1
2
3
4
5
6
7
8
9
10
11
12
130,131c130,131
< static int lept_parse_string(lept_context* c, lept_value* v) {
<     size_t head = c->top, len;
---
> static int lept_parse_string_raw(lept_context* c, char** str, size_t* len) {
>     size_t head = c->top;
140,141c140,141
<                 len = c->top - head;
<                 lept_set_string(v, (const char*)lept_context_pop(c, len), len);
---
>                 *len = c->top - head;
>                 *str = lept_context_pop(c, *len);

以 TDD 方式开发软件，因为有单元测试确保软件的正确性，面对新需求可以安心重构，改善软件架构。

  1. 打开 test.c 中两个 #if 0，运行单元测试，证实单元测试不通过。然后实现 lept_parse_object() 中的 \todo 部分。验证实现能通过单元测试。

有了 lept_parse_array() 的经验，实现 lept_parse_object() 几乎是一样的，分别只是每个迭代要多处理一个键和冒号。我们把这个实现过程分为 5 步曲。

第 1 步是利用刚才重构出来的 lept_parse_string_raw() 去解析键的字符串。由于 lept_parse_string_raw() 假设第一个字符为 "，我们要先作校检，失败则要返回 LEPT_PARSE_MISS_KEY 错误。若字符串解析成功，它会把结果存储在我们的栈之中，需要把结果写入临时 lept_member 的 k 和 klen 字段中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static int lept_parse_object(lept_context* c, lept_value* v) {
    size_t i, size;
    lept_member m;
    int ret;
    /* ... */
    m.k = NULL;
    size = 0;
    for (;;) {
        char* str;
        lept_init(&m.v);
        /* 1. parse key */
        if (*c->json != '"') {
            ret = LEPT_PARSE_MISS_KEY;
            break;
        }
        if ((ret = lept_parse_string_raw(c, &str, &m.klen)) != LEPT_PARSE_OK)
            break;
        memcpy(m.k = (char*)malloc(m.klen + 1), str, m.klen);
        m.k[m.klen] = '\0';
        /* 2. parse ws colon ws */
        /* ... */
    }
    /* 5. Pop and free members on the stack */
    /* ... */
}

第 2 步是解析冒号，冒号前后可有空白字符：

1
2
3
4
5
6
7
8
/* 2. parse ws colon ws */
lept_parse_whitespace(c);
if (*c->json != ':') {
    ret = LEPT_PARSE_MISS_COLON;
    break;
}
c->json++;
lept_parse_whitespace(c);

第 3 步是解析任意的 JSON 值。这部分与解析数组一样，递归调用 lept_parse_value()，把结果写入临时 lept_member 的 v 字段，然后把整个 lept_member 压入栈：

1
2
3
4
5
6
/* 3. 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 */

但有一点要注意，如果之前缺乏冒号，或是这里解析值失败，在函数返回前我们要释放 m.k。如果我们成功地解析整个成员，那么就要把 m.k 设为空指针，其意义是说明该键的字符串的拥有权已转移至栈，之后如遇到错误，我们不会重覆释放栈里成员的键和这个临时成员的键。

第 4 步，解析逗号或右花括号。遇上右花括号的话，当前的 JSON 对象就解析完结了，我们把栈上的成员复制至结果，并直接返回：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 4. parse ws [comma | right-curly-brace] ws */
lept_parse_whitespace(c);
if (*c->json == ',') {
    c->json++;
    lept_parse_whitespace(c);
}
else if (*c->json == '}') {
    size_t s = sizeof(lept_member) * size;
    c->json++;
    v->type = LEPT_OBJECT;
    v->u.o.size = size;
    memcpy(v->u.o.m = (lept_member*)malloc(s), lept_context_pop(c, s), s);
    return LEPT_PARSE_OK;
}
else {
    ret = LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET;
    break;
}

最后，当 for (;;) 中遇到任何错误便会到达这第 5 步，要释放临时的 key 字符串及栈上的成员：

1
2
3
4
5
6
7
8
9
/* 5. Pop and free members on the stack */
free(m.k);
for (i = 0; i < size; i++) {
    lept_member* m = (lept_member*)lept_context_pop(c, sizeof(lept_member));
    free(m->k);
    lept_free(&m->v);
}
v->type = LEPT_NULL;
return ret;

注意我们不需要先检查 m.k != NULL，因为 free(NULL) 是完全合法的。

  1. 使用工具检测内存泄漏，解决它们。

使用工具检测内存泄漏时，我们会发现以下这行代码造成内存泄漏：

1
memcpy(v->u.o.m = (lept_member*)malloc(s), lept_context_pop(c, s), s);

类似数组，我们也需要在 lept_free() 释放 JSON 对象的成员（包括键及值）：

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

留言

⬆︎TOP