动手实现一个JSON验证器
发表时间 2017-03-20  |  浏览量:  |  分类: Go

最近做毕设的时候,有个功能需要验证JSON字符串的合法性,最简单的做法是直接用Go的第三方JSON库做一个反序列化,但这样做给我有种杀鸡用牛刀的感觉,毕竟我不需要真正的反序列化它,单纯的验证和反序列化的性能差距直观感觉上还是比较大的。

分析

既然要验证JSON的有效性,那么必然需要清楚的知道JSON格式,这个在JSON官网已经给我们画出来了:

object
array
value
string
number

从官方的图上面可以看出,JSON的组成一共有五部分:

  1. object: 以左大括号({)开头表示对象的开始。
  2. array: 以左中括号([)开头表示数组的开始。
  3. value: 数组中只能有值类型,对象中每一个键后面必跟一个值类型。
  4. string: 以英文的双引号开头表示字符串类型。
  5. number: 以减号(-)、1~9、0开头表示数值类型。

从上可以看出,每一种不同的类型都可以用不同的字符来标识,且根据这个特定的符号转移到不同类型的解析状态,显然实际上就是一个状态机,而这个状态机只需要处理五种不同类型的解析即可。

实现

常量定义

我们需要先定义一些常量来标识每个特定字符所代表的意义, 大多数常量的定义和上面的图中一一对应:

const (
    OBJ_START = '{' // 标识期望一个object解析开始
    OBJ_END   = '}' // 标识期望一个object解析结束
    ARR_START = '[' // 标识期望一个array解析开始
    ARR_END   = ']' // 标识期望一个array解析结束
    SEP_COLON = ':' // 标识期望一个键值对的value
    SEP_COMMA = ',' // 标识期望下一个键值对或者下一个value

    BOOL_T = 't' // 标识期望一个true
    BOOL_F = 'f' // 标识期望一个false

    NULL_START = 'n' // 标识期望一个null

    CONTROL_CHARACTER = 0x20 // JSON中0x20以下的控制字符是不允许出现的
)

const (
    REVERSE_SOLIDUS         = '\\' // 标识转义字符,期望接下去读的字符是反斜杠或以下8个字符中的一个,
    QUOTATION_MARK          = '"'
    SOLIDUS                 = '/'
    BACKSPACE               = 'b'
    FORMFEED                = 'f'
    NEWLINE                 = 'n'
    CARRIAGE_RETURN         = 'r'
    HORIZONTAL_TAB          = 't'
    FOUR_HEXADECIMAL_DIGITS = 'u'
)

const (
    NUMBER_DOT   = '.'
    NUMBER_e     = 'e'
    NUMBER_E     = 'E'
    NUMBER_PLUS  = '+'
    NUMBER_MINUS = '-'
    NUMBER_ZERO  = '0'
)

解析错误

将解析过程中出现的错误简单分成三种类型,并封装错误信息:

var (
    ErrInvalidJSON   = errors.New("invalid json format")
    ErrUnexpectedEOF = errors.New("unexpected end of JSON")
    ErrStringEscape  = errors.New("get an invalid escape character")
)

type ErrJSON struct {
    err        error // 标识错误的类型
    additional string // 描述错误具体信息
    part       string // 从解析错误的那个字符开始的一部分json字符串
}

func (e ErrJSON) Error() string {
    return e.String()
}

func (e ErrJSON) String() string {
    return fmt.Sprintf("error:\n\t%s\nadditional:\n\t%s\n"+
        "occur at:\n\t %s\n", e.err, e.additional, e.part)
}

JSON字节切片封装

将JSON字节切片封装一下,每次读取第X个字符或移动X个字符时都需要第本次操作的有效性用validateLen方法验证。

jsonBytes是原始JSON字符串转换成的切片表示,并且每次moveX后都会重新切片:jsonBytes = jsonBytes[...]
maxPosition是jsonBytes的最初长度,即:len(jsonBytes)
position是当前读取到的位置。

type JSON struct {
    jsonBytes   []byte
    position    uint
    maxPosition uint
}

func (j *JSON) len() int {
    return len(j.jsonBytes)
}

func (j *JSON) validateLen(x uint) {
    if j.maxPosition <= j.position {
        panic(ErrJSON{
            err:  ErrUnexpectedEOF,
            part: getPartOfJSON(j),
        })
    }
}

func (j *JSON) moveX(x uint) *JSON {
    if x == 0 {
        return j
    }

    j.validateLen(x)

    j.jsonBytes = j.jsonBytes[x:]
    j.position += x
    return j
}

func (j *JSON) moveOne() *JSON {
    return j.moveX(1)
}

func (j *JSON) byteX(x uint) byte {
    j.validateLen(x)

    return j.jsonBytes[x]
}

func (j *JSON) firstByte() byte {
    return j.byteX(0)
}

去除空白符

在JSON中,空格、回车、制表符等在非字符串中是会被直接忽略的,所以每次读取一个字节后都需要去除剩余字节数组中前面那部分的空白字节,因为读取只会是从左往右的,所以没必要浪费cpu在去除右侧的空白字符:

func TrimLeftSpace(data *JSON) *JSON {
    for idx, r := range data.jsonBytes {
        // 调用unicode包的IsSpace函数判断是否是空白字符即可
        if !unicode.IsSpace(rune(r)) {
            return data.moveX(uint(idx))
        }
    }
    return data.moveX(uint(data.len()))
}

获取JSON字符串中的一部分

在有错误发生时,我们希望不仅获得是什么样的错误,还希望能得到从错误发生的那个字符开始的一部分JSON字符串,方便定位错误发生的位置,getPartOfJSON函数会返回从错误开始发生处的接下去40个字符的字符串:

func getPartOfJSON(data *JSON) string {
    return string([]rune(string(data.jsonBytes[:160]))[:40])
}

有了这个函数,再加上上面对错误信息的封装,接下去只要遇到解析错误,就可以直接调用这样的panic:

panic(ErrJSON{
    err:        ErrInvalidJSON,
    additional: "expect a null value: null",
    part:       getPartOfJSON(data),
})

Expect函数

我们还需要这样一个函数,它用来判断JSON.jsonBytes中的第一个字节是否和目标字节相等,如果不相等则直接触发ErrInvalidJSON,这个函数是非常有用的,用在以下几个地方:

  1. 在验证object时,JSON.jsonBytes中的第一个字符必须是左大括号({) -> Expect(OBJ_START, data)
  2. 在验证object时,key验证完后必须紧跟着一个英文下的冒号(:) -> Expect(SEP_COLON, TrimLeftSpace(data))
  3. 在验证string时,JSON.jsonBytes中的第一个字符必须是英文下的双引号(") -> Expect(QUOTATION_MARK, data)
  4. 在验证array时,JSON.jsonBytes中的第一个字符必须是左中括号([) -> Expect(ARR_START, data)
func Expect(b byte, data *JSON) {
    if data.firstByte() != b {
        panic(ErrJSON{
            err:        ErrInvalidJSON,
            additional: fmt.Sprintf("expect character: %c", b),
            part:       getPartOfJSON(data),
        })
    }
    TrimLeftSpace(data.moveOne())
    return
}

入口函数

有了以上封装的数据结构和辅助函数,接下去就可以开始编写各个验证函数了,首先是入口函数Validate
JSON字符串的根节点只能是两种类型的数据: object或array,因此如果不是以 { 或者 [开头,则认为是非法JSON字符串。并且在验证完之后如果还有其他非空白字符,也认为是非法JSON字符串,因为JSON中只允许有一个根节点。:

func Validate(jsonStr string) (err error) {
    defer func() {
        if e := recover(); e != nil {
            if e, ok := e.(error); ok {
                err = e.(error)
            } else {
                panic(e)
            }
        }
    }()

    data := &JSON{[]byte(jsonStr), 0, uint(len(jsonStr))}

    TrimLeftSpace(data)
    if data.firstByte() == OBJ_START {
        ValidateObj(data)

        if TrimLeftSpace(data).len() == 0 {
            return nil
        }
    } else if data.firstByte() == ARR_START {
        ValidateArr(data)

        if TrimLeftSpace(data).len() == 0 {
            return nil
        }
    }

    return ErrJSON{
        err:        ErrInvalidJSON,
        additional: "extra characters after parsing",
        part:       getPartOfJSON(data),
    }
}

验证object

object

根据object组成,我们的验证流程如下:

  1. 第一个字符是否是{
  2. 是否是一个空对象{},如果是则跳过}并返回。
  3. 按照以下流程循环验证键值对:
    1. 验证key是否是合法字符串。
    2. key验证结束后,必须有一个:
    3. 验证一个value类型。
    4. 一个键值对验证完成后只会存在两种情况:
      1. 紧跟着一个,表明期望有下一个键值对,这种情况下循环继续。
      2. 紧跟着一个}标识这个object类型验证结束,跳过’}’符号并返回。
func ValidateObj(data *JSON) {
    Expect(OBJ_START, data)

    if TrimLeftSpace(data).firstByte() == OBJ_END {
        data.moveOne()
        return
    }

    for {
        ValidateStr(TrimLeftSpace(data))

        Expect(SEP_COLON, TrimLeftSpace(data))

        ValidateValue(TrimLeftSpace(data))

        TrimLeftSpace(data)

        if data.firstByte() == SEP_COMMA {
            data.moveOne()
        } else if data.firstByte() == OBJ_END {
            data.moveOne()
            return
        } else {
            panic(ErrJSON{
                err:        ErrInvalidJSON,
                additional: `expect any one of the following characters: ','  '}'`,
                part:       getPartOfJSON(data),
            })
        }
    }
}

验证array

array

array的组成和验证流程比object要简单一些,因为array中没有key只有value,验证流程如下:

  1. 第一个字符是否是[
  2. 是否是一个空数组[],如果是则跳过]并返回。
  3. 按照以下流程循环验证array中的value:
    1. 验证是否是一个合法的value。
    2. 一个value验证完成后只会存在两种情况:
      1. 紧跟着一个,表明期望有下一个value,这种情况下循环继续。
      2. 紧跟着一个]标识这个array类型验证结束,跳过’]’符号并返回。
func ValidateArr(data *JSON) {
    Expect(ARR_START, data)

    if TrimLeftSpace(data).firstByte() == ARR_END {
        data.moveOne()
        return
    }

    for {
        ValidateValue(TrimLeftSpace(data))

        TrimLeftSpace(data)
        if data.firstByte() == SEP_COMMA {
            data.moveOne()
        } else if data.firstByte() == ARR_END {
            data.moveOne()
            return
        } else {
            panic(ErrJSON{
                err:        ErrInvalidJSON,
                additional: `expect any one of the following characters: ','  ']'`,
                part:       getPartOfJSON(data),
            })
        }
    }
}

验证string

string

string的验证相对array和object要复杂一点,分成两个函数,一个是验证字符串的主体函数ValidateStr,一个是验证转义字符ValidateEsc
验证流程如下:

  1. 第一个字符是否是"
  2. 按照以下流程循环验证字符串中的每一个字符:
    1. 先判断needEsc是否为true,needEsc只有在前一个字符是反斜杠(\)的情况下为true,如果为true则调用ValidateEsc函数验证转义字符的合法性,并在验证通过后置needEsc为false。
    2. 如果needEsc为false,则按照以下流程验证:
      1. 如果当前字符是",则表示字符串验证结束,跳过idx个字符并返回。
      2. 如果当前字符是\,则置needEsc位true表示下一个字符期望是转义字符。
      3. 如果当前字符是控制字符( < 0x20 ),则触发panic,因为string中不允许出现控制字符。
      4. 如果上述三种情况都不是,则代表是一些合法的允许出现在string中的普通字符,直接跳过该字符。
  3. 如果for循环结束,则该JSON字符串必是非法的,因为JSON不可能以string开始也不可能以string结束。
func ValidateStr(data *JSON) {
    Expect(QUOTATION_MARK, data)

    var needEsc bool

RE_VALID:
    for idx, r := range data.jsonBytes {
        if needEsc {
            ValidateEsc(data.moveX(uint(idx)))
            needEsc = false
            goto RE_VALID
        }

        switch {
        case r == QUOTATION_MARK:
            data.moveX(uint(idx + 1))
            return
        case r == REVERSE_SOLIDUS:
            needEsc = true
        case r < CONTROL_CHARACTER:
            panic(ErrJSON{
                err:        ErrInvalidJSON,
                additional: "control characters are not allowed in string type(< 0x20)",
                part:       getPartOfJSON(data),
            })
        }
    }

    panic(ErrJSON{
        err:  ErrUnexpectedEOF,
        part: getPartOfJSON(data),
    })
}

ValidateEsc函数

string

ValidateEsc函数很简单,只有两种情况:

  1. 当前字符是否是"\/bfnrt中的一个,如果是的话则跳过当前字符并返回。
  2. 当前字符是否是u,如果是则继续以下验证:
    1. 验证接下去的4个字符是否是十六进制的表示,即在范围0~9、A~F、a~f中,如果是,则是合法转义字符,否则是非法的转义字符。
      如果以上两种都不是的话,则当前字符不符合JSON中转义字符的定义,认为是非法JSON字符串。
func ValidateEsc(data *JSON) {
    switch data.firstByte() {
    case QUOTATION_MARK, REVERSE_SOLIDUS, SOLIDUS, BACKSPACE, FORMFEED,
        NEWLINE, CARRIAGE_RETURN, HORIZONTAL_TAB:
        TrimLeftSpace(data.moveOne())
        return
    case FOUR_HEXADECIMAL_DIGITS:
        for i := 1; i <= 4; i++ {
            switch {
            case data.byteX(uint(i)) >= '0' && data.byteX(uint(i)) <= '9':
            case data.byteX(uint(i)) >= 'A' && data.byteX(uint(i)) <= 'F':
            case data.byteX(uint(i)) >= 'a' && data.byteX(uint(i)) <= 'f':
            default:
                panic(ErrJSON{
                    err:        ErrStringEscape,
                    additional: `expect to get unicode characters consisting of \u and 4 hexadecimal digits`,
                    part:       getPartOfJSON(data),
                })
            }
        }
        TrimLeftSpace(data.moveX(5))
    default:
        panic(ErrJSON{
            err:        ErrStringEscape,
            additional: `expect to get unicode characters consisting of \u and 4 hexadecimal digits, or any one of the following characters: '"'  '\'  '/'  'b'  'f'  'n'  'r'  't'`,
            part:       getPartOfJSON(data),
        })
    }
    return
}

验证value类型

value

根据valuye的组成,我们的验证流程如下:

  1. 第一个字符是否是",是的话表明该value是一个string,调用ValidateStr验证string。
  2. 第一个字符是否是{,是的话表明该value是一个object,调用ValidateObj验证object。
  3. 第一个字符是否是[,是的话表明该value是一个array,调用ValidateArr验证array。
  4. 第一个字符是否是t,是的话表明该value是true,验证接下去的三个字符是否分别为rue,如果是的话跳过true这四个字符并返回,否则触发panic。
  5. 第一个字符是否是f,是的话表明该value是false,验证接下去的四个字符是否分别为alse,如果是的话跳过false这五个字符并返回,否则触发panic。
  6. 第一个字符是否是n,是的话表明该value是null,验证接下去的三个字符是否分别位ull,如果是的话跳过null这四个字符并返回,否则触发panic。
  7. 第一个字符是否是0-或者在字符1~9之间,是的话表明该value是一个number类型,调用ValidateNumber验证number。
  8. 如果以上7种情况都不是的话,则该JSON字符串是不合法的,触发panic。
func ValidateValue(data *JSON) {
    b := data.firstByte()
    switch {
    case b == QUOTATION_MARK:
        ValidateStr(data)
    case b == OBJ_START:
        ValidateObj(data)
    case b == ARR_START:
        ValidateArr(data)
    case b == BOOL_T:
        if data.byteX(1) != 'r' || data.byteX(2) != 'u' ||
            data.byteX(3) != 'e' {
            panic(ErrJSON{
                err:        ErrInvalidJSON,
                additional: "expect a bool value: true",
                part:       getPartOfJSON(data),
            })
        }
        data.moveX(4)
    case b == BOOL_F:
        if data.byteX(1) != 'a' || data.byteX(2) != 'l' ||
            data.byteX(3) != 's' || data.byteX(4) != 'e' {
            panic(ErrJSON{
                err:        ErrInvalidJSON,
                additional: "expect a bool value: false",
                part:       getPartOfJSON(data),
            })
        }
        data.moveX(5)
    case b == NULL_START:
        if data.byteX(1) != 'u' || data.byteX(2) != 'l' ||
            data.byteX(3) != 'l' {
            panic(ErrJSON{
                err:        ErrInvalidJSON,
                additional: "expect a null value: null",
                part:       getPartOfJSON(data),
            })
        }
        data.moveX(4)
    case b == NUMBER_MINUS || b == NUMBER_ZERO || (b >= '1' && b <= '9'):
        ValidateNumber(data)
    default:
        panic(ErrJSON{
            err:        ErrInvalidJSON,
            additional: `expect any one of the following characters: '"'  '{'  '['  't'  'f'  'n'  '-'  '0'  '1'  '2'  '3'  '4'  '5'  '6'  '7'  '8'  '9'`,
            part:       getPartOfJSON(data),
        })
    }

    return
}

验证number类型

number

number的验证相对是最复杂的(其实也不复杂,就是判断多了一点),同样分成两个函数,一个是验证number的主体函数ValidateNumber,一个是验证连续整数的函数ValidateDigit
验证流程如下:

  1. 第一个字符是否是-,如果是则跳过该字符。
  2. 接着分成两种情况:
    1. 第一个字符是否是0,如果是的跳过该字符。
    2. 第一个字符是否在字符19之间,如果是的话跳过该字符并调用ValidateDigit函数验证一串连续的整数。
    3. 如果以上两种都不是的话,则该JSON字符串非法,当前字符不符合number的组成格式。
  3. 通过前面的两个验证后,接下去是否跟着一个.如果是的话继续验证小数部分,即调用ValidateDigit验证一串连续的整数。
  4. 接着验证是否跟着e或者E,是的话继续验证科学计数法的表示,否则number类型验证结束,直接return。
  5. 验证是否紧跟着+或者-,是的话跳过该字符
  6. 调用ValidateDigit验证一串连续整数。
func ValidateNumber(data *JSON) {
    if data.firstByte() == NUMBER_MINUS {
        data.moveOne()
    }

    if data.firstByte() == NUMBER_ZERO {
        data.moveOne()
        // do nothing, maybe need read continuous '0' character
    } else if data.firstByte() >= '1' || data.firstByte() <= '9' {
        data.moveOne()

        if data.firstByte() >= '0' && data.firstByte() <= '9' {
            ValidateDigit(data)
        }
    } else {
        panic(ErrJSON{
            err:        ErrInvalidJSON,
            additional: `expect any one of the following characters: '-'  '0'  '1'  '2'  '3'  '4'  '5'  '6'  '7'  '8'  '9'`,
            part:       getPartOfJSON(data),
        })
    }

    if data.firstByte() == NUMBER_DOT {
        ValidateDigit(data.moveOne())
    }

    if data.firstByte() != NUMBER_e && data.firstByte() != NUMBER_E {
        return
    }

    data.moveOne()

    if data.firstByte() == NUMBER_PLUS || data.firstByte() == NUMBER_MINUS {
        data.moveOne()
    }

    ValidateDigit(data)

    return
}

ValidateDigit函数

ValidateDigit函数会尝试读取一串连续的范围在09之间的字符,直到遇到不在范围内的字符为止,如果for循环结束还没return的话,则当前JSON字符串必是非法字符串,以为JSON不可能以整开头也不可能以整数结尾。

func ValidateDigit(data *JSON) {
    if data.firstByte() < '0' || data.firstByte() > '9' {
        panic(ErrJSON{
            err:        ErrInvalidJSON,
            additional: "expect any one of the following characters: '0'  '1'  '2'  '3'  '4'  '5'  '6'  '7'  '8'  '9'",
            part:       getPartOfJSON(data),
        })
    }

    data.moveOne()

    for idx, b := range data.jsonBytes {
        if b < '0' || b > '9' {
            data.moveX(uint(idx))
            return
        }
    }

    panic(ErrJSON{
        err:  ErrUnexpectedEOF,
        part: getPartOfJSON(data),
    })
}

结束

JSON字符串的验证比想象中的要简单很多,可以说是相当的简单,这得益于在官网上已经将各个状态的扭转、格式类型和组成图给你画好了,只要代码没写错,照着图把各个部分的验证写出来就实现了。
在写完后,我用fastjson的issue859.json测了一下性能,和调用Go的json库或其它三方json库相比,这个实现的性能要高出30%左右,因此如果有需求只验证不解析的,花点时间手撸一个验证器还是很划算的。
完整代码可以在这里找到

如果文章有什么问题,或者有其它更好的想法,欢迎留言或私信交流。

转载请注明出处: 动手实现一个JSON验证器

关闭

分类

Java 算法 Linux Git Go Feign Hystrix

标签

Java 字符串 算法 kmp Linux VPS VPN 系统界面 Git Socks5 Go json 网络 面试 后端开发 翻译 Feign Spring Cloud 日志 log4j slf4j Hystrix