# demo

**Repository Path**: kimkey/demo

## Basic Information

- **Project Name**: demo
- **Description**: Lepton JSON Library. 使用C89语言开发的轻量级JSON库，包含JSON解释器和JSON生成器两个部分。
- **Primary Language**: C
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-04-02
- **Last Updated**: 2022-05-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# LeptJson 项目实践 

## 前言

在经过C语言基础学习后，一直没有开始动手实践项目，导致对代码的实际掌握能力不够，以及对系统的理解能力有所欠缺。所以，后面将会记录自己动手实现 GitHub上的开源项目 [Lepton JSON](https://github.com/miloyip/json-tutorial) 的思路以及过程。

## 项目简介

JSON 文本是一种以 **`Key - Value`** 为基本形式的数据交换格式，通过文本的形式表示一个树形结构。我们期待的 **Leptjson** 是一个**轻量的 JSON库 **，包括  **JSON 解释器** 和 **JSON生成器** 两个部分。解释器要求能够读取 JSON 文本并对其进行解析，然后形成生成对应的树形结构。 **解析** 和 **树形结构的生成** 是其中的重点。生成器要求能够根据自行定义的JSON结点数据结构，生成JSON文本。

## 总体设计

### JSON 解释器

一般，JSON 文本以 **对象 **或 **数组** 的形式封装内容，将数据保存为 **键值对** 或 **值并列** 的形式。键是一个字符串，而值的类型则较多，包括字面量、数字、字符串、数组、对象。其中字面量包括 `NULL` 和布尔值（`TRUE` and `FALSE`）。在这些类型中，数组和对象可能会存在值嵌套，所以，我们要处理的内容就是从 JSON 文件中读出的字符串，对其进行解析，并以 **树形结构** 存储 JSON 数据。由于结点类型和结点值是一一对应的，所以我们可以用 `union_type` 来减少内存占用。

```c
// 64位环境

// JSON 数据的类型
typedef enum lept_type {
    LEPT_NULL = 0,  // null
    LEPT_BOOLEAN,   //合并 true 和 false 为布尔类型
    LEPT_NUMBER,    // number
    LEPT_STRING,    // string
    LEPT_ARRAY,     // array
    LEPT_OBJECT     // object
} lept_type;

typedef struct lept_value lept_value;

// JSON 对象成员
struct lept_member {
    char* key;  //8 Bytes
    size_t key_length;  // 8 Bytes
    lept_value value;  // 24 Bytes
};  // 40 Bytes

// JSON 数据节点
struct lept_value {
    lept_type type;  //节点的数据类型, 4 Bytes

    union union_struct {
        struct str_struct {
            char* string;
            size_t length;
        } str;  //16 Bytes

        double number;  //存放浮点数字, 8 Bytes
        int boolean;    //存放布尔值, 4 Bytes

        struct arr_struct {
            lept_value* elements;
            size_t size;
        } arr;  // 16 Bytes

        struct object {
            lept_member* lept_members;
            size_t size;
        } obj;  // 16 Bytes
    } union_struct;  // 16 Bytes
};  // 4 Bytes + 16 Bytes ===内存对齐===> 24 Bytes
```



此外，我们还需要让解释器能够检测 JSON 文本发生了何种错误，所以我们要定义 **返回码** （多数时候作为 **错误码** 使用）。

```c
typedef enum return_code {
    LEPT_PARSE_OK = 0,                        //解析正确
    
    LEPT_PARSE_EXPECT_VALUE,                  //只含有whitespace
    LEPT_PARSE_ROOT_NOT_SINGULAR,             // value之后的whitespace后跟有其他字符
    LEPT_PARSE_INVALID_VALUE,                 //值不属于三种字面值

    LEPT_PARSE_NUMBER_TOO_BIG,                //数字太大

    LEPT_PARSE_MISS_QUOTATION_MARK,           //字符串 quotation mark 不完整
    LEPT_PARSE_INVALID_STRING_ESCAPE,         //非法转义字符
    LEPT_PARSE_INVALID_UNICODE_SURROGATE,     //非法代理项

    LEPT_PARSE_MISS_COMMA_OR_SQUARE_BRACKET,  //数组缺乏逗号或方括号

    LEPT_PARSE_MISS_KEY,                      //对象成员的键值对中缺失键
    LEPT_PARSE_MISS_COLON,                    //对象成员键值对之间未用冒号进行分隔
    LEPT_PARSE_MISS_COMMA_RO_CURLY_BRACKET    //对象成员间未用逗号分隔，或对象缺失右花括号
} return_code;
```



选定这些基本数据格式之后，我们就可以进行进行 JSON 文本的解析。JSON 文本中会存在大量 **空白符** ，回车、换行、制表符等，这些字符只有格式化的意义，而不包含任何信息。所以在解释 JSON 时，要跳过空白符。每一种值类型都会以一些 **标志性的符号** 作为起始。

- 字面量： `NULL` 、 `TRUE` 、 `FALSE` 内容固定；
- 数字：单个 `0` 或 以 `0~9` 起始的多个数字位；
- 字符串：以双引号 `"` 开始，也以双引号结束；
- 数组：以 `[` 起始，以 `]` 结束；
- 对象：以 `{` 起始，以 `}` 结束。

这样，就可以将解析行为统一起来，从 JSON 读取到字符串后，根据不同的起始符，就可以判断应该进行哪一种数值类型的解析，然后解析其值并产生数据结点。因为数据都封装在对象中，所以从一个对象中就可以得到完整的 JSON 文本的数据。

在成功解析到一个结果后，我们应当确保不会再次读取到另一个 `value` ，也就是说，一个 JSON 文本只允许存在一个 JSON 数据，但数据允许内部嵌套其他类型。那么，我们就需要在完成最外层的 JSON 解析后，判断余下未解析的 JSON 文本不存在除 **空白字符** 外的任何字符。

```c
lept_parse_whitespace(&c);  //解析空白字符
int ret_value = lept_parse_value(&c, v);  // 解析一个数据

//若 value 解析成功，则继续解析 value 之后的所有空白，再判断是否结束。若未结束则判定为多值输入
if (ret_value == LEPT_PARSE_OK) {
    lept_parse_whitespace(&c);
    if ((ret_value == LEPT_PARSE_OK) && (*c.json != '\0')) {
        v->type = LEPT_NULL;  //多值输入，将类型强制修改为null
        lept_context_stack_free(&c);
        return LEPT_PARSE_ROOT_NOT_SINGULAR;
    }
}
```



### JSON 生成器

**JSON 生成器！！！待补充！！！**



## 详细设计

按照不同解析需求，编写对应类型的解析模块。因为字符串类型和其他嵌套类型（数组、对象）等解析时的缓冲需要，另设置缓冲模块。

### 辅助模块

#### Context 文本结构及缓冲栈

因为我们解析 JSON 文本时，需要解析出该数据中包含的 JSON 数据信息，但是多数时候我们解析得到的 JSON 数据长度未知或存在内嵌数据，若动态地申请空间就会造成很大的资源开销。所以我们希望建立一个可以 **复用** 的缓冲结构，`Context` 结构中的缓冲栈 `stack` 就是为此设计的。

具体工作方式如下：

- 我们希望缓冲栈能够**预分配一定大小的内存**。
- 当我们需要占用栈空间时，则将栈顶指针向栈顶移动对应字节数（等同于待入栈数据的大小），然后将这部分的内存的内容修改为要入栈的数据内容。若栈空间余量不足，则申请更大的栈空间，并将原有内容对应拷贝到新空间。
- 当我们需要取出栈顶的数据时，则让栈顶指针向栈底移动对应字节数（等同于待取出数据的大小），并将缩减的这部分内存的内容复制到目的内存中。

此外，因为调用不同模块时，都需要传递 **缓冲栈** 和 **未解析文本内容** ，所以我们可以将它们封装为一个 `Context` 整体，以简化模块的输入。

```c
// Context 文本结构及缓冲栈
typedef struct context {
    size_t size;  //堆栈大小
    size_t top;   //堆栈栈顶位置
    const char* json;
    char* stack;  //缓冲区堆栈
} lept_context;
```

```c
//让缓冲栈增长指定空间, 返回指向下一个可用空间的指针
void* lept_context_stack_grow(lept_context* c, size_t appended_size) {
    void* ret = NULL;
    assert(appended_size > 0);

    //若增长后会超过现有缓冲栈大小, 则必须重新为缓冲栈分配空间
    if (c->top + appended_size >= c->size) {
        //如果当前缓冲栈大小为0, 则直接分配一个初始空间即可
        if (c->size == 0) {
            c->size = LEPT_PARSE_STACK_INIT_SIZE;
        }

        //如果现有缓冲栈空间不足以支持增长, 则增长至现有空间的 1.5 倍,
        //若仍不足则继续重复增长
        while (c->top + appended_size >= c->size) {
            c->size += (c->size >> 1);
        }
    }

    char* tmp_ptr = (char*)realloc(c->stack, c->size);  //确定重新分配的大小后, 申请重新分配内存
    if (!tmp_ptr) {
        return 0;
    }
    c->stack = tmp_ptr;
    ret = c->stack + c->top;  //返回栈顶指针(未被占用的位置)
    c->top += appended_size;  //栈顶位置增长, 增量等同于 appended_size
    return ret;
}

// 向缓冲栈写入数据的宏操作
#define PUTC(context, ch)\
	do {\
        *(char*)lept_context_stack_grow(context, sizeof(char)) = (ch);\
    } while (0)

//使缓冲栈收缩
void* lept_context_stack_shrink(lept_context* c, size_t shrunk_size) {
    assert(c->size >= shrunk_size);
    c->top -= shrunk_size;
    return c->stack + c->top;
}

// 出栈操作: memcpy(&data, (char*)lept_context_stack_shrink(c, sizeof(data)), sizeof(data));
```



### JSON 解释器

#### Whitespace 空白符的解析

JSON 文本中的空白符包括空白、制表、换行、回车。因为空白符并不属于数据的实际构成部分，所以我们对空白符的解析实际上就是 **跳过空白** ，不施加任何处理。此外，因为空白符可以连续出现，所以我们需要能够跳过连续的多个空白，这是比较容易实现的。



#### Literal 字面量解析

字面量包括 3 种： `null` 、 `true` 、 `false` 。当我们读取到 JSON 文本字符串后，我们就要对其进行字面量解析，也就是判断所读到的内容是否等于三种字面量中的某一种，这样就变成了 **字符串匹配** 的问题。由于 JSON 数据类型中只存在这三种字面量，所以我们就可以根据首字母进入字面量的判断。如果首字母是 `n` 、 `t` 、 `f` 则分别对应进入 `null` 、`true` 、 `false` 的解析。如果能够**完整匹配**，则按照字面量内容修改节点数据类型，并修改共用体内的值。

```c
static int lept_parse_literal(lept_context* context, lept_value* v, const char* expect_json, 
                              lept_type expect_type) {
    const char* expect_json_head = expect_json;  //保存 预期json文本 的字符串起始

    //尝试用 *expect_json 字面量来解析 json文本
    EXPECT(context, *expect_json);
    expect_json++;
    while ((*context->json != '\0') && (*expect_json != '\0')) {
        //若中途发生不匹配的情况, 表明 json文本 提供的字面量非法
        if (*context->json != *expect_json) {
            return LEPT_PARSE_INVALID_VALUE;
        }
        context->json++;
        expect_json++;
    }

    //若未能按照 *expect_json 完成解析，表示json字符串非法
    if (*expect_json != '\0') {
        return LEPT_PARSE_INVALID_VALUE;
    }

    //通过解析, 表明字面量解析成功, 将节点类型修改为对应字面量的类型
    v->type = expect_type;  //修改字面量的类型

    //已通过解析, 如果节点类型是布尔类型, 还要修改复合类型的布尔值
    if (ISBOOLEANTYPE(v)) {
        if (ISTRUE(expect_json_head)) {
            v->union_struct.boolean = 1;
        } else {
            v->union_struct.boolean = 0;
        }
    }
    return LEPT_PARSE_OK;
}
```



#### Number 数字解析



#### String 字符串解析



#### Array 数组解析



#### Object 对象解析



### JSON 生成器