摘要：具體來講，就是在遇到和的子節點的時候要壓入棧，遇到一個的結束符的時候要彈出棧。同時還要保存棧結點對應的以及其狀態信息。所以我定義了一個棧結點結構其中表示當前棧節點的狀態，表示其所代表的值表示其父節點，根節點的父節點為。

前一陣子看到了一個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...，有興趣的可以看看~

首先既然是便宜的，便和反射無關了，所以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.

對于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 "	", "
", "
", " ":
      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節點這一點，還有數組的動態擴容等。

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