徒手写一个JSON解析器(Golang)

前一阵子看到了一个Golang的JSON库go-simplejson,用来封装与解析匿名的JSON,说白了就是用map或者slice等来解析JSON,觉得挺好玩,后来有个项目恰好要解析JSON,于是就试了试,不小心看了一眼源代码,发现竟然是用的Golang自带的encoding/json库去做的解析,而其本身只是把这个库封装了一层,看起来更好看罢了。于是心想能不能徒手写一个解析器,毕竟写了这么多年代码了,也JSON.parse,JSON.stringify了无数次。捣腾了两天,终于成了,测试了一下,性能比自带的库要高很多,速度基本上在1.6到7倍之间(视JSON串的大小和结构而定),所以决定写这篇文章分享一下思路。

先插一个段子,作为一个已经完完整整写了将近三年代码的老码农,前一段面试,不止一次有面试官问我:如何深拷贝一个对象(JS),我笑笑说写一个Walk函数递归一下就行了啊,如果要考虑到Stackoverflow,那就用栈+迭代就好了。然后他们老是问我,有没有更好的办法,然后自言自语的说你可以用JSON先序列化一遍再反序列化......

项目取名cheapjson,意思是便宜的,因为你不光不需要定义各个struct,性能还比原生的快,所以很便宜。地址在 https://github.com/acrazing/c...,有兴趣的可以看看~

JSON value

首先既然是便宜的,便和反射无关了,所以void *是必需的,当然在Golang里面是interface{},然后需要一个结构来保存必需的信息,进行类型判断以及边界检查。如果是C的话,数组大小,字符串长度,对象Key/Value映射都是必需的工作。不过在Golang里面就不需要了,编译器已经搞定了所有的工作。

在JSON当中,一个完整的JSON应该包含一个value,这个value的类型可能是null,true,false,number,string, array以及 object共6种。而array和object还有可能包含子value结构。这些类型的值映射到Golang当中,便是nil, bool, bool, int64/float64, string, []interface{}, map[string]interface{},用一个union结构便可以搞定。注意这里的number有可以转换成整数或者是浮点数,在JavaScript中,全部用64位双精度浮点数储存,所以最大的精确整数也就是非规约数是尾数部分2^53 - 1,已经远远大于int32了,所以这里将整数映射成了int64而不是int,因为在部分机器上可能溢出,严格的区分一个IEEE-754格式的整数和浮点数并不是一件轻松的事情,这里简化成了如果尾数中的小数部分以及指数部分均不存在,则认为是一个整数,此外,为了简化操作,对于任何不合法的UTF-16字符串,都认为结构有问题,而终止解析。为了方便,定义一个结构来保存一个JSON的value:

type struct Value {
 value interface{}
}

结构中的value字段保存这个JSONValue的实际值,通过类型判定来确定其类型。因此会有很多的判定,赋值,以及取值函数,比如针对一个string类型的Value需要有判定是否为string的操作IsString(),赋值AsString(),以及获取真实值的操作String():

// 判定是否为string,如果是,则返回true,否则返回false
func (v *Value) IsString() bool {
 if _, ok := v.value.(string); ok {
 return true
 }
 return false
}
// 将一个Value赋值为一个string
func (v *Value) AsString(value string) {
 v.value = value
}
// 从一个string类型的Value中取出String值
func (v *Value) String() string {
 if value, ok := v.value.(string); ok {
 return value
 }
 // 如果不是一个string类型,则报错,所以需要先判定是否为string类型
 panic("not a string value")
}

针对这样的操作还有很多,可以参考 cheapjson/value.go.

JSON parser

对于string, true, false, null, number这样的值,都属于字面量,即没有深层结构,可取直接读取,并且中间不可能被空白字符切断,所以可以直接读取。而对于一个array或者object,则是一个多层的树状结构。最直接的想法肯定是用递归,但是大家都知道这是不可行的,因为在解析大JSON的时候很可能栈溢出了,所以只能用栈+迭代的办法。

学过编译原理的人都知道,做AST分析的时候首先要分析Token,然后再分析AST,在解析JSON的时候也应该这样,虽然Token比较少:只有几个字面量以及{, [, :, ], }几个界定符。可惜我并没有学过编译原理,上来就拿状态机来迭代了。因为JSON是一棵树,其解析过程是从树根一直遍历到各个叶节点再返回树根的过程。自然就会涉及到栈的压入及弹出操作。具体来讲,就是在遇到array和object的子节点的时候要压入栈,遇到一个value的结束符的时候要弹出栈。同时还要保存栈结点对应的Value以及其状态信息。所以我定义了一个栈结点结构:

type struct state {
 state int
 value *Value
 parent *state
}

其中state表示当前栈节点的状态,value表示其所代表的值parent表示其父节点,根节点的父节点为nil。当要压入栈时,只需要新建一个节点,将其parent设置为当前节点即可,要弹出时,将当前结点设置为当前结点的parent。如果当前节点为nil,则表示遍历结束,JSON自身也应该结束,除了空白字符外,不应该还包含任何字符。

一个节点可能的状态有:

const (
 // start of a value
 stateNone = iota
 stateString
 // after [ must be a value or ]
 stateArrayValueOrEnd
 // after a value, must be a , or ]
 stateArrayEndOrComma
 // after a {, must be a key string or }
 stateObjectKeyOrEnd
 // after a key string must be a :
 stateObjectColon
 // after a : must be a value
 // after a value, must be , or }
 stateObjectEndOrComma
 // after a , must be key string
 stateObjectKey
)

状态的含义和字面意思一样,比如对于状态stateArrayValueOrEnd表示当前栈节点遇到了一个array的起始标志[,在等待一个子Value或者一个array的结束符],而状态stateArrayEndOrComma表示一个array已经遇到了子Value,在等待结束符]或者Value的分隔符,。因此,在解析一个数组的时候,完整的栈操作过程是:遇到[,将当前结点的状态设置为stateArrayValueOrEnd,然后过滤空白字符,判定第一个字符是]还是其它字符,如果是],则array结束,弹出栈,如果不是,则将自身状态修改为stateArrayEndOrComma,并压入一个新栈结点,将其状态设置为stateNone,重新开始解析,此结点解析完成之后,弹出此结点,判定是,还是],如果是],则结束弹出,如果是,则不改变自身状态,并重新一个新栈结点,开始新的循环。完事的状态机如下:

其含义如下:

首先初始化一个空节点,状态设置为stateNone,然后判断第一个非空字符,如果是t/f/n/[-0-9],则直接解析字面量,然后弹出,如果是[,则将状态设置为stateArrayValueOrEnd,然后判定第一个字符,如果是],则结束弹出,否则压入新栈,并将自身状态设置为stateArrayEndOrComma,开始新的循环,如果是{,则将状态设置为stateObjectKeyOrEnd,如果下一个非空字符为},则结束弹出,否则解析key,完成之后,压入新栈,并将自身状态设置为stateObjectEndOrComma。

比较特殊的是stateString,按道理其也是一个字面量,不需要到一个新的循环里面去解析。但是因为一个object的key也是一个string,为了复用代码,并避免调用函数产生的性能开销,将string类型和object的key当作同一类型来处理,具体如下:

root := &state{&Value{nil}, stateNone, nil}
curr := root
for {
 // ignore whitespace
 // check curr is nil or not
 switch curr.state {
 case stateNone:
 switch data[offset] {
 case '"':
 // go to new loop
 curr.state = stateString
 continue
 }
 case stateObjectKey, stateString:
 // parse string
 if curr.state == stateObjectKey {
 // create new stack node
 } else {
 // pop stack
 }
 }
}

此外比较特殊的是在解析完一个object的key之后,立即压入了一个新栈结点,并将其状态设置为stateObjectColon,同时将自身的状态设置为stateObjectEndOrComma,在解析完colon之后再这个节点的状态设置为stateNone,开始新的循环,具体来说:

if curr.state == stateObjectKey {
 curr.state = stateObjectEndOrComma
 curr = &state{&Value{nil}, stateObjectColon, nil}
 continue
}

这是因为在:之前和之后都可能有空白字符,这里是为了复用代码逻辑:即在每一次迭代开始之时都把所有的空白过滤掉。

for {
 LOOP_WS:
 for ; offset < len(data); offset++ {
 switch data[offset] {
 case '\t', '\r', '\n', ' ':
 continue
 default:
 break LOOP_WS
 }
 // do staff
}

在过滤掉空白后,如果当前栈为nil,则不应该有字符存在,整个解析结束,否则一定有字符,并且需要进行解析:

for {
 // ignore whitespace
 if curr == nil {
 if offset == len(data) {
 return
 } else {
 // unexpected char data[offset] at offset
 }
 } else if offset == len(data) {
 // unexpected EOF at offset
 }
 // do staff
}

随后便是根据当前状态来进行相应的解析了。

后记

从目前的开源项目上来看,性能上应该还有优化的空间,毕竟有人已经做到号称2-4x的速度,而且现在已经有很多项目在搞将Golang的Struct先编译一遍,再调用生成的函数针对特定的结构进行解析,速度更快,不过既然就预先编译了,干嘛还要用JSON啊,直接PB/MsgPack得了。特别是djson这个库,解析小JSON的时候速度是原生的3-4倍,但是大的时候只有2倍,而cheapjson则在解析大JSON的时候性能几乎是原生的7倍,相当搞笑。而从测试结果上来看,整体上性能和内存都还可以,但是在解析数组的时候比原生的还要差。所以值得改进,尤其是频繁的创建和销毁state节点这一点,还有数组的动态扩容等。

以后有空再慢慢搞吧,我不想白头发越来越多了。

本文来自:Segmentfault

感谢作者:nadass

查看原文:徒手写一个JSON解析器(Golang)

• 编辑
• 预览