| // Copyright 2010 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package json |
| |
| // JSON value parser state machine. |
| // Just about at the limit of what is reasonable to write by hand. |
| // Some parts are a bit tedious, but overall it nicely factors out the |
| // otherwise common code from the multiple scanning functions |
| // in this package (Compact, Indent, checkValid, nextValue, etc). |
| // |
| // This file starts with two simple examples using the scanner |
| // before diving into the scanner itself. |
| |
| import ( |
| "os" |
| "strconv" |
| ) |
| |
| // checkValid verifies that data is valid JSON-encoded data. |
| // scan is passed in for use by checkValid to avoid an allocation. |
| func checkValid(data []byte, scan *scanner) os.Error { |
| scan.reset() |
| for _, c := range data { |
| if scan.step(scan, int(c)) == scanError { |
| return scan.err |
| } |
| } |
| if scan.eof() == scanError { |
| return scan.err |
| } |
| return nil |
| } |
| |
| // nextValue splits data after the next whole JSON value, |
| // returning that value and the bytes that follow it as separate slices. |
| // scan is passed in for use by nextValue to avoid an allocation. |
| func nextValue(data []byte, scan *scanner) (value, rest []byte, err os.Error) { |
| scan.reset() |
| for i, c := range data { |
| v := scan.step(scan, int(c)) |
| if v >= scanEnd { |
| switch v { |
| case scanError: |
| return nil, nil, scan.err |
| case scanEnd: |
| return data[0:i], data[i:], nil |
| } |
| } |
| } |
| if scan.eof() == scanError { |
| return nil, nil, scan.err |
| } |
| return data, nil, nil |
| } |
| |
| // A SyntaxError is a description of a JSON syntax error. |
| type SyntaxError string |
| |
| func (e SyntaxError) String() string { return string(e) } |
| |
| |
| // A scanner is a JSON scanning state machine. |
| // Callers call scan.reset() and then pass bytes in one at a time |
| // by calling scan.step(&scan, c) for each byte. |
| // The return value, referred to as an opcode, tells the |
| // caller about significant parsing events like beginning |
| // and ending literals, objects, and arrays, so that the |
| // caller can follow along if it wishes. |
| // The return value scanEnd indicates that a single top-level |
| // JSON value has been completed, *before* the byte that |
| // just got passed in. (The indication must be delayed in order |
| // to recognize the end of numbers: is 123 a whole value or |
| // the beginning of 12345e+6?). |
| type scanner struct { |
| // The step is a func to be called to execute the next transition. |
| // Also tried using an integer constant and a single func |
| // with a switch, but using the func directly was 10% faster |
| // on a 64-bit Mac Mini, and it's nicer to read. |
| step func(*scanner, int) int |
| |
| // Stack of what we're in the middle of - array values, object keys, object values. |
| parseState []int |
| |
| // Error that happened, if any. |
| err os.Error |
| |
| // 1-byte redo (see undo method) |
| redoCode int |
| redoState func(*scanner, int) int |
| } |
| |
| // These values are returned by the state transition functions |
| // assigned to scanner.state and the method scanner.eof. |
| // They give details about the current state of the scan that |
| // callers might be interested to know about. |
| // It is okay to ignore the return value of any particular |
| // call to scanner.state: if one call returns scanError, |
| // every subsequent call will return scanError too. |
| const ( |
| // Continue. |
| scanContinue = iota // uninteresting byte |
| scanBeginLiteral // end implied by next result != scanContinue |
| scanBeginObject // begin object |
| scanObjectKey // just finished object key (string) |
| scanObjectValue // just finished non-last object value |
| scanEndObject // end object (implies scanObjectValue if possible) |
| scanBeginArray // begin array |
| scanArrayValue // just finished array value |
| scanEndArray // end array (implies scanArrayValue if possible) |
| scanSkipSpace // space byte; can skip; known to be last "continue" result |
| |
| // Stop. |
| scanEnd // top-level value ended *before* this byte; known to be first "stop" result |
| scanError // hit an error, scanner.err. |
| ) |
| |
| // These values are stored in the parseState stack. |
| // They give the current state of a composite value |
| // being scanned. If the parser is inside a nested value |
| // the parseState describes the nested state, outermost at entry 0. |
| const ( |
| parseObjectKey = iota // parsing object key (before colon) |
| parseObjectValue // parsing object value (after colon) |
| parseArrayValue // parsing array value |
| ) |
| |
| // reset prepares the scanner for use. |
| // It must be called before calling s.step. |
| func (s *scanner) reset() { |
| s.step = stateBeginValue |
| s.parseState = s.parseState[0:0] |
| s.err = nil |
| } |
| |
| // eof tells the scanner that the end of input has been reached. |
| // It returns a scan status just as s.step does. |
| func (s *scanner) eof() int { |
| if s.err != nil { |
| return scanError |
| } |
| if s.step == stateEndTop { |
| return scanEnd |
| } |
| s.step(s, ' ') |
| if s.step == stateEndTop { |
| return scanEnd |
| } |
| if s.err == nil { |
| s.err = SyntaxError("unexpected end of JSON input") |
| } |
| return scanError |
| } |
| |
| // pushParseState pushes a new parse state p onto the parse stack. |
| func (s *scanner) pushParseState(p int) { |
| s.parseState = append(s.parseState, p) |
| } |
| |
| // popParseState pops a parse state (already obtained) off the stack |
| // and updates s.step accordingly. |
| func (s *scanner) popParseState() { |
| n := len(s.parseState) - 1 |
| s.parseState = s.parseState[0:n] |
| if n == 0 { |
| s.step = stateEndTop |
| } else { |
| s.step = stateEndValue |
| } |
| } |
| |
| func isSpace(c int) bool { |
| return c == ' ' || c == '\t' || c == '\r' || c == '\n' |
| } |
| |
| // NOTE(rsc): The various instances of |
| // |
| // if c <= ' ' && (c == ' ' || c == '\t' || c == '\r' || c == '\n') |
| // |
| // below should all be if c <= ' ' && isSpace(c), but inlining |
| // the checks makes a significant difference (>10%) in tight loops |
| // such as nextValue. These should be rewritten with the clearer |
| // function call once 6g knows to inline the call. |
| |
| // stateBeginValueOrEmpty is the state after reading `[`. |
| func stateBeginValueOrEmpty(s *scanner, c int) int { |
| if c <= ' ' && (c == ' ' || c == '\t' || c == '\r' || c == '\n') { |
| return scanSkipSpace |
| } |
| if c == ']' { |
| return stateEndValue(s, c) |
| } |
| return stateBeginValue(s, c) |
| } |
| |
| // stateBeginValue is the state at the beginning of the input. |
| func stateBeginValue(s *scanner, c int) int { |
| if c <= ' ' && (c == ' ' || c == '\t' || c == '\r' || c == '\n') { |
| return scanSkipSpace |
| } |
| switch c { |
| case '{': |
| s.step = stateBeginStringOrEmpty |
| s.pushParseState(parseObjectKey) |
| return scanBeginObject |
| case '[': |
| s.step = stateBeginValueOrEmpty |
| s.pushParseState(parseArrayValue) |
| return scanBeginArray |
| case '"': |
| s.step = stateInString |
| return scanBeginLiteral |
| case '-': |
| s.step = stateNeg |
| return scanBeginLiteral |
| case '0': // beginning of 0.123 |
| s.step = state0 |
| return scanBeginLiteral |
| case 't': // beginning of true |
| s.step = stateT |
| return scanBeginLiteral |
| case 'f': // beginning of false |
| s.step = stateF |
| return scanBeginLiteral |
| case 'n': // beginning of null |
| s.step = stateN |
| return scanBeginLiteral |
| } |
| if '1' <= c && c <= '9' { // beginning of 1234.5 |
| s.step = state1 |
| return scanBeginLiteral |
| } |
| return s.error(c, "looking for beginning of value") |
| } |
| |
| // stateBeginStringOrEmpty is the state after reading `{`. |
| func stateBeginStringOrEmpty(s *scanner, c int) int { |
| if c <= ' ' && (c == ' ' || c == '\t' || c == '\r' || c == '\n') { |
| return scanSkipSpace |
| } |
| if c == '}' { |
| n := len(s.parseState) |
| s.parseState[n-1] = parseObjectValue |
| return stateEndValue(s, c) |
| } |
| return stateBeginString(s, c) |
| } |
| |
| // stateBeginString is the state after reading `{"key": value,`. |
| func stateBeginString(s *scanner, c int) int { |
| if c <= ' ' && (c == ' ' || c == '\t' || c == '\r' || c == '\n') { |
| return scanSkipSpace |
| } |
| if c == '"' { |
| s.step = stateInString |
| return scanBeginLiteral |
| } |
| return s.error(c, "looking for beginning of object key string") |
| } |
| |
| // stateEndValue is the state after completing a value, |
| // such as after reading `{}` or `true` or `["x"`. |
| func stateEndValue(s *scanner, c int) int { |
| n := len(s.parseState) |
| if n == 0 { |
| // Completed top-level before the current byte. |
| s.step = stateEndTop |
| return stateEndTop(s, c) |
| } |
| if c <= ' ' && (c == ' ' || c == '\t' || c == '\r' || c == '\n') { |
| s.step = stateEndValue |
| return scanSkipSpace |
| } |
| ps := s.parseState[n-1] |
| switch ps { |
| case parseObjectKey: |
| if c == ':' { |
| s.parseState[n-1] = parseObjectValue |
| s.step = stateBeginValue |
| return scanObjectKey |
| } |
| return s.error(c, "after object key") |
| case parseObjectValue: |
| if c == ',' { |
| s.parseState[n-1] = parseObjectKey |
| s.step = stateBeginString |
| return scanObjectValue |
| } |
| if c == '}' { |
| s.popParseState() |
| return scanEndObject |
| } |
| return s.error(c, "after object key:value pair") |
| case parseArrayValue: |
| if c == ',' { |
| s.step = stateBeginValue |
| return scanArrayValue |
| } |
| if c == ']' { |
| s.popParseState() |
| return scanEndArray |
| } |
| return s.error(c, "after array element") |
| } |
| return s.error(c, "") |
| } |
| |
| // stateEndTop is the state after finishing the top-level value, |
| // such as after reading `{}` or `[1,2,3]`. |
| // Only space characters should be seen now. |
| func stateEndTop(s *scanner, c int) int { |
| if c != ' ' && c != '\t' && c != '\r' && c != '\n' { |
| // Complain about non-space byte on next call. |
| s.error(c, "after top-level value") |
| } |
| return scanEnd |
| } |
| |
| // stateInString is the state after reading `"`. |
| func stateInString(s *scanner, c int) int { |
| if c == '"' { |
| s.step = stateEndValue |
| return scanContinue |
| } |
| if c == '\\' { |
| s.step = stateInStringEsc |
| return scanContinue |
| } |
| if c < 0x20 { |
| return s.error(c, "in string literal") |
| } |
| return scanContinue |
| } |
| |
| // stateInStringEsc is the state after reading `"\` during a quoted string. |
| func stateInStringEsc(s *scanner, c int) int { |
| switch c { |
| case 'b', 'f', 'n', 'r', 't', '\\', '/', '"': |
| s.step = stateInString |
| return scanContinue |
| } |
| if c == 'u' { |
| s.step = stateInStringEscU |
| return scanContinue |
| } |
| return s.error(c, "in string escape code") |
| } |
| |
| // stateInStringEscU is the state after reading `"\u` during a quoted string. |
| func stateInStringEscU(s *scanner, c int) int { |
| if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { |
| s.step = stateInStringEscU1 |
| return scanContinue |
| } |
| // numbers |
| return s.error(c, "in \\u hexadecimal character escape") |
| } |
| |
| // stateInStringEscU1 is the state after reading `"\u1` during a quoted string. |
| func stateInStringEscU1(s *scanner, c int) int { |
| if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { |
| s.step = stateInStringEscU12 |
| return scanContinue |
| } |
| // numbers |
| return s.error(c, "in \\u hexadecimal character escape") |
| } |
| |
| // stateInStringEscU12 is the state after reading `"\u12` during a quoted string. |
| func stateInStringEscU12(s *scanner, c int) int { |
| if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { |
| s.step = stateInStringEscU123 |
| return scanContinue |
| } |
| // numbers |
| return s.error(c, "in \\u hexadecimal character escape") |
| } |
| |
| // stateInStringEscU123 is the state after reading `"\u123` during a quoted string. |
| func stateInStringEscU123(s *scanner, c int) int { |
| if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { |
| s.step = stateInString |
| return scanContinue |
| } |
| // numbers |
| return s.error(c, "in \\u hexadecimal character escape") |
| } |
| |
| // stateInStringEscU123 is the state after reading `-` during a number. |
| func stateNeg(s *scanner, c int) int { |
| if c == '0' { |
| s.step = state0 |
| return scanContinue |
| } |
| if '1' <= c && c <= '9' { |
| s.step = state1 |
| return scanContinue |
| } |
| return s.error(c, "in numeric literal") |
| } |
| |
| // state1 is the state after reading a non-zero integer during a number, |
| // such as after reading `1` or `100` but not `0`. |
| func state1(s *scanner, c int) int { |
| if '0' <= c && c <= '9' { |
| s.step = state1 |
| return scanContinue |
| } |
| return state0(s, c) |
| } |
| |
| // state0 is the state after reading `0` during a number. |
| func state0(s *scanner, c int) int { |
| if c == '.' { |
| s.step = stateDot |
| return scanContinue |
| } |
| if c == 'e' || c == 'E' { |
| s.step = stateE |
| return scanContinue |
| } |
| return stateEndValue(s, c) |
| } |
| |
| // stateDot is the state after reading the integer and decimal point in a number, |
| // such as after reading `1.`. |
| func stateDot(s *scanner, c int) int { |
| if '0' <= c && c <= '9' { |
| s.step = stateDot0 |
| return scanContinue |
| } |
| return s.error(c, "after decimal point in numeric literal") |
| } |
| |
| // stateDot0 is the state after reading the integer, decimal point, and subsequent |
| // digits of a number, such as after reading `3.14`. |
| func stateDot0(s *scanner, c int) int { |
| if '0' <= c && c <= '9' { |
| s.step = stateDot0 |
| return scanContinue |
| } |
| if c == 'e' || c == 'E' { |
| s.step = stateE |
| return scanContinue |
| } |
| return stateEndValue(s, c) |
| } |
| |
| // stateE is the state after reading the mantissa and e in a number, |
| // such as after reading `314e` or `0.314e`. |
| func stateE(s *scanner, c int) int { |
| if c == '+' { |
| s.step = stateESign |
| return scanContinue |
| } |
| if c == '-' { |
| s.step = stateESign |
| return scanContinue |
| } |
| return stateESign(s, c) |
| } |
| |
| // stateESign is the state after reading the mantissa, e, and sign in a number, |
| // such as after reading `314e-` or `0.314e+`. |
| func stateESign(s *scanner, c int) int { |
| if '0' <= c && c <= '9' { |
| s.step = stateE0 |
| return scanContinue |
| } |
| return s.error(c, "in exponent of numeric literal") |
| } |
| |
| // stateE0 is the state after reading the mantissa, e, optional sign, |
| // and at least one digit of the exponent in a number, |
| // such as after reading `314e-2` or `0.314e+1` or `3.14e0`. |
| func stateE0(s *scanner, c int) int { |
| if '0' <= c && c <= '9' { |
| s.step = stateE0 |
| return scanContinue |
| } |
| return stateEndValue(s, c) |
| } |
| |
| // stateT is the state after reading `t`. |
| func stateT(s *scanner, c int) int { |
| if c == 'r' { |
| s.step = stateTr |
| return scanContinue |
| } |
| return s.error(c, "in literal true (expecting 'r')") |
| } |
| |
| // stateTr is the state after reading `tr`. |
| func stateTr(s *scanner, c int) int { |
| if c == 'u' { |
| s.step = stateTru |
| return scanContinue |
| } |
| return s.error(c, "in literal true (expecting 'u')") |
| } |
| |
| // stateTru is the state after reading `tru`. |
| func stateTru(s *scanner, c int) int { |
| if c == 'e' { |
| s.step = stateEndValue |
| return scanContinue |
| } |
| return s.error(c, "in literal true (expecting 'e')") |
| } |
| |
| // stateF is the state after reading `f`. |
| func stateF(s *scanner, c int) int { |
| if c == 'a' { |
| s.step = stateFa |
| return scanContinue |
| } |
| return s.error(c, "in literal false (expecting 'a')") |
| } |
| |
| // stateFa is the state after reading `fa`. |
| func stateFa(s *scanner, c int) int { |
| if c == 'l' { |
| s.step = stateFal |
| return scanContinue |
| } |
| return s.error(c, "in literal false (expecting 'l')") |
| } |
| |
| // stateFal is the state after reading `fal`. |
| func stateFal(s *scanner, c int) int { |
| if c == 's' { |
| s.step = stateFals |
| return scanContinue |
| } |
| return s.error(c, "in literal false (expecting 's')") |
| } |
| |
| // stateFals is the state after reading `fals`. |
| func stateFals(s *scanner, c int) int { |
| if c == 'e' { |
| s.step = stateEndValue |
| return scanContinue |
| } |
| return s.error(c, "in literal false (expecting 'e')") |
| } |
| |
| // stateN is the state after reading `n`. |
| func stateN(s *scanner, c int) int { |
| if c == 'u' { |
| s.step = stateNu |
| return scanContinue |
| } |
| return s.error(c, "in literal null (expecting 'u')") |
| } |
| |
| // stateNu is the state after reading `nu`. |
| func stateNu(s *scanner, c int) int { |
| if c == 'l' { |
| s.step = stateNul |
| return scanContinue |
| } |
| return s.error(c, "in literal null (expecting 'l')") |
| } |
| |
| // stateNul is the state after reading `nul`. |
| func stateNul(s *scanner, c int) int { |
| if c == 'l' { |
| s.step = stateEndValue |
| return scanContinue |
| } |
| return s.error(c, "in literal null (expecting 'l')") |
| } |
| |
| // stateError is the state after reaching a syntax error, |
| // such as after reading `[1}` or `5.1.2`. |
| func stateError(s *scanner, c int) int { |
| return scanError |
| } |
| |
| // error records an error and switches to the error state. |
| func (s *scanner) error(c int, context string) int { |
| s.step = stateError |
| s.err = SyntaxError("invalid character " + quoteChar(c) + " " + context) |
| return scanError |
| } |
| |
| // quoteChar formats c as a quoted character literal |
| func quoteChar(c int) string { |
| // special cases - different from quoted strings |
| if c == '\'' { |
| return `'\''` |
| } |
| if c == '"' { |
| return `'"'` |
| } |
| |
| // use quoted string with different quotation marks |
| s := strconv.Quote(string(c)) |
| return "'" + s[1:len(s)-1] + "'" |
| } |
| |
| // undo causes the scanner to return scanCode from the next state transition. |
| // This gives callers a simple 1-byte undo mechanism. |
| func (s *scanner) undo(scanCode int) { |
| if s.step == stateRedo { |
| panic("invalid use of scanner") |
| } |
| s.redoCode = scanCode |
| s.redoState = s.step |
| s.step = stateRedo |
| } |
| |
| // stateRedo helps implement the scanner's 1-byte undo. |
| func stateRedo(s *scanner, c int) int { |
| s.step = s.redoState |
| return s.redoCode |
| } |