摘要：具體來講，就是在遇到和的子節(jié)點(diǎn)的時(shí)候要壓入棧，遇到一個(gè)的結(jié)束符的時(shí)候要彈出棧。同時(shí)還要保存棧結(jié)點(diǎn)對(duì)應(yīng)的以及其狀態(tài)信息。所以我定義了一個(gè)棧結(jié)點(diǎn)結(jié)構(gòu)其中表示當(dāng)前棧節(jié)點(diǎn)的狀態(tài)，表示其所代表的值表示其父節(jié)點(diǎn)，根節(jié)點(diǎn)的父節(jié)點(diǎn)為。

前一陣子看到了一個(gè)Golang的JSON庫go-simplejson，用來封裝與解析匿名的JSON，說白了就是用map或者slice等來解析JSON，覺得挺好玩，后來有個(gè)項(xiàng)目恰好要解析JSON，于是就試了試，不小心看了一眼源代碼，發(fā)現(xiàn)竟然是用的Golang自帶的encoding/json庫去做的解析，而其本身只是把這個(gè)庫封裝了一層，看起來更好看罷了。于是心想能不能徒手寫一個(gè)解析器，畢竟寫了這么多年代碼了，也JSON.parse，JSON.stringify了無數(shù)次。搗騰了兩天，終于成了，測試了一下，性能比自帶的庫要高很多，速度基本上在1.6到7倍之間（視JSON串的大小和結(jié)構(gòu)而定），所以決定寫這篇文章分享一下思路。

先插一個(gè)段子，作為一個(gè)已經(jīng)完完整整寫了將近三年代碼的老碼農(nóng)，前一段面試，不止一次有面試官問我：如何深拷貝一個(gè)對(duì)象（JS），我笑笑說寫一個(gè)Walk函數(shù)遞歸一下就行了啊，如果要考慮到Stackoverflow，那就用棧+迭代就好了。然后他們老是問我，有沒有更好的辦法，然后自言自語的說你可以用JSON先序列化一遍再反序列化……

項(xiàng)目取名cheapjson，意思是便宜的，因?yàn)槟悴还獠恍枰x各個(gè)struct，性能還比原生的快，所以很便宜。地址在 https://github.com/acrazing/c...，有興趣的可以看看~

首先既然是便宜的，便和反射無關(guān)了，所以void *是必需的，當(dāng)然在Golang里面是interface{}，然后需要一個(gè)結(jié)構(gòu)來保存必需的信息，進(jìn)行類型判斷以及邊界檢查。如果是C的話，數(shù)組大小，字符串長度，對(duì)象Key/Value映射都是必需的工作。不過在Golang里面就不需要了，編譯器已經(jīng)搞定了所有的工作。

在JSON當(dāng)中，一個(gè)完整的JSON應(yīng)該包含一個(gè)value，這個(gè)value的類型可能是null，true，false，number，string， array以及 object共6種。而array和object還有可能包含子value結(jié)構(gòu)。這些類型的值映射到Golang當(dāng)中，便是nil, bool, bool, int64/float64, string, []interface{}, map[string]interface{}，用一個(gè)union結(jié)構(gòu)便可以搞定。注意這里的number有可以轉(zhuǎn)換成整數(shù)或者是浮點(diǎn)數(shù)，在JavaScript中，全部用64位雙精度浮點(diǎn)數(shù)儲(chǔ)存，所以最大的精確整數(shù)也就是非規(guī)約數(shù)是尾數(shù)部分2^53 - 1，已經(jīng)遠(yuǎn)遠(yuǎn)大于int32了，所以這里將整數(shù)映射成了int64而不是int，因?yàn)樵诓糠謾C(jī)器上可能溢出，嚴(yán)格的區(qū)分一個(gè)IEEE-754格式的整數(shù)和浮點(diǎn)數(shù)并不是一件輕松的事情，這里簡化成了如果尾數(shù)中的小數(shù)部分以及指數(shù)部分均不存在，則認(rèn)為是一個(gè)整數(shù)，此外，為了簡化操作，對(duì)于任何不合法的UTF-16字符串，都認(rèn)為結(jié)構(gòu)有問題，而終止解析。為了方便，定義一個(gè)結(jié)構(gòu)來保存一個(gè)JSON的value：

type struct Value {
  value interface{}
}

結(jié)構(gòu)中的value字段保存這個(gè)JSONValue的實(shí)際值，通過類型判定來確定其類型。因此會(huì)有很多的判定，賦值，以及取值函數(shù)，比如針對(duì)一個(gè)string類型的Value需要有判定是否為string的操作IsString()，賦值AsString()，以及獲取真實(shí)值的操作String()：

// 判定是否為string，如果是，則返回true，否則返回false
func (v *Value) IsString() bool {
  if _, ok := v.value.(string); ok {
    return true
  }
  return false
}

// 將一個(gè)Value賦值為一個(gè)string
func (v *Value) AsString(value string) {
  v.value = value
}

// 從一個(gè)string類型的Value中取出String值
func (v *Value) String() string {
  if value, ok := v.value.(string); ok {
    return value
  }
  // 如果不是一個(gè)string類型，則報(bào)錯(cuò)，所以需要先判定是否為string類型
  panic("not a string value")
}

針對(duì)這樣的操作還有很多，可以參考 cheapjson/value.go.

對(duì)于string, true, false, null, number這樣的值，都屬于字面量，即沒有深層結(jié)構(gòu)，可取直接讀取，并且中間不可能被空白字符切斷，所以可以直接讀取。而對(duì)于一個(gè)array或者object，則是一個(gè)多層的樹狀結(jié)構(gòu)。最直接的想法肯定是用遞歸，但是大家都知道這是不可行的，因?yàn)樵诮馕龃驤SON的時(shí)候很可能棧溢出了，所以只能用棧+迭代的辦法。

學(xué)過編譯原理的人都知道，做AST分析的時(shí)候首先要分析Token，然后再分析AST，在解析JSON的時(shí)候也應(yīng)該這樣，雖然Token比較少：只有幾個(gè)字面量以及{, [, :, ], }幾個(gè)界定符?？上也]有學(xué)過編譯原理，上來就拿狀態(tài)機(jī)來迭代了。因?yàn)镴SON是一棵樹，其解析過程是從樹根一直遍歷到各個(gè)葉節(jié)點(diǎn)再返回樹根的過程。自然就會(huì)涉及到棧的壓入及彈出操作。具體來講，就是在遇到array和object的子節(jié)點(diǎn)的時(shí)候要壓入棧，遇到一個(gè)value的結(jié)束符的時(shí)候要彈出棧。同時(shí)還要保存棧結(jié)點(diǎn)對(duì)應(yīng)的Value以及其狀態(tài)信息。所以我定義了一個(gè)棧結(jié)點(diǎn)結(jié)構(gòu)：

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

其中state表示當(dāng)前棧節(jié)點(diǎn)的狀態(tài)，value表示其所代表的值parent表示其父節(jié)點(diǎn)，根節(jié)點(diǎn)的父節(jié)點(diǎn)為nil。當(dāng)要壓入棧時(shí)，只需要新建一個(gè)節(jié)點(diǎn)，將其parent設(shè)置為當(dāng)前節(jié)點(diǎn)即可，要彈出時(shí)，將當(dāng)前結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)的parent。如果當(dāng)前節(jié)點(diǎn)為nil，則表示遍歷結(jié)束，JSON自身也應(yīng)該結(jié)束，除了空白字符外，不應(yīng)該還包含任何字符。

一個(gè)節(jié)點(diǎn)可能的狀態(tài)有：

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
)

狀態(tài)的含義和字面意思一樣，比如對(duì)于狀態(tài)stateArrayValueOrEnd表示當(dāng)前棧節(jié)點(diǎn)遇到了一個(gè)array的起始標(biāo)志[，在等待一個(gè)子Value或者一個(gè)array的結(jié)束符]，而狀態(tài)stateArrayEndOrComma表示一個(gè)array已經(jīng)遇到了子Value，在等待結(jié)束符]或者Value的分隔符,。因此，在解析一個(gè)數(shù)組的時(shí)候，完整的棧操作過程是：遇到[，將當(dāng)前結(jié)點(diǎn)的狀態(tài)設(shè)置為stateArrayValueOrEnd，然后過濾空白字符，判定第一個(gè)字符是]還是其它字符，如果是]，則array結(jié)束，彈出棧，如果不是，則將自身狀態(tài)修改為stateArrayEndOrComma，并壓入一個(gè)新棧結(jié)點(diǎn)，將其狀態(tài)設(shè)置為stateNone，重新開始解析，此結(jié)點(diǎn)解析完成之后，彈出此結(jié)點(diǎn)，判定是,還是]，如果是]，則結(jié)束彈出，如果是,則不改變自身狀態(tài)，并重新一個(gè)新棧結(jié)點(diǎn)，開始新的循環(huán)。完事的狀態(tài)機(jī)如下：

其含義如下：

首先初始化一個(gè)空節(jié)點(diǎn)，狀態(tài)設(shè)置為stateNone，然后判斷第一個(gè)非空字符，如果是t/f/n/[-0-9]，則直接解析字面量，然后彈出，如果是[，則將狀態(tài)設(shè)置為stateArrayValueOrEnd，然后判定第一個(gè)字符，如果是]，則結(jié)束彈出，否則壓入新棧，并將自身狀態(tài)設(shè)置為stateArrayEndOrComma，開始新的循環(huán)，如果是{，則將狀態(tài)設(shè)置為stateObjectKeyOrEnd，如果下一個(gè)非空字符為}，則結(jié)束彈出，否則解析key，完成之后，壓入新棧，并將自身狀態(tài)設(shè)置為stateObjectEndOrComma。

比較特殊的是stateString，按道理其也是一個(gè)字面量，不需要到一個(gè)新的循環(huán)里面去解析。但是因?yàn)橐粋€(gè)object的key也是一個(gè)string，為了復(fù)用代碼，并避免調(diào)用函數(shù)產(chǎn)生的性能開銷，將string類型和object的key當(dāng)作同一類型來處理，具體如下：

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
      }
  }
}

此外比較特殊的是在解析完一個(gè)object的key之后，立即壓入了一個(gè)新棧結(jié)點(diǎn)，并將其狀態(tài)設(shè)置為stateObjectColon，同時(shí)將自身的狀態(tài)設(shè)置為stateObjectEndOrComma，在解析完colon之后再這個(gè)節(jié)點(diǎn)的狀態(tài)設(shè)置為stateNone，開始新的循環(huán)，具體來說：

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

這是因?yàn)樵?b>:之前和之后都可能有空白字符，這里是為了復(fù)用代碼邏輯：即在每一次迭代開始之時(shí)都把所有的空白過濾掉。

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

在過濾掉空白后，如果當(dāng)前棧為nil，則不應(yīng)該有字符存在，整個(gè)解析結(jié)束，否則一定有字符，并且需要進(jìn)行解析：

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
}

隨后便是根據(jù)當(dāng)前狀態(tài)來進(jìn)行相應(yīng)的解析了。

從目前的開源項(xiàng)目上來看，性能上應(yīng)該還有優(yōu)化的空間，畢竟有人已經(jīng)做到號(hào)稱2-4x的速度，而且現(xiàn)在已經(jīng)有很多項(xiàng)目在搞將Golang的Struct先編譯一遍，再調(diào)用生成的函數(shù)針對(duì)特定的結(jié)構(gòu)進(jìn)行解析，速度更快，不過既然就預(yù)先編譯了，干嘛還要用JSON啊，直接PB/MsgPack得了。特別是djson這個(gè)庫，解析小JSON的時(shí)候速度是原生的3-4倍，但是大的時(shí)候只有2倍，而cheapjson則在解析大JSON的時(shí)候性能幾乎是原生的7倍，相當(dāng)搞笑。而從測試結(jié)果上來看，整體上性能和內(nèi)存都還可以，但是在解析數(shù)組的時(shí)候比原生的還要差。所以值得改進(jìn)，尤其是頻繁的創(chuàng)建和銷毀state節(jié)點(diǎn)這一點(diǎn)，還有數(shù)組的動(dòng)態(tài)擴(kuò)容等。

以后有空再慢慢搞吧，我不想白頭發(fā)越來越多了。