1// Copyright 2010 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package json 6 7// JSON value parser state machine. 8// Just about at the limit of what is reasonable to write by hand. 9// Some parts are a bit tedious, but overall it nicely factors out the 10// otherwise common code from the multiple scanning functions 11// in this package (Compact, Indent, checkValid, nextValue, etc). 12// 13// This file starts with two simple examples using the scanner 14// before diving into the scanner itself. 15 16import "strconv" 17 18// checkValid verifies that data is valid JSON-encoded data. 19// scan is passed in for use by checkValid to avoid an allocation. 20func checkValid(data []byte, scan *scanner) error { 21 scan.reset() 22 for _, c := range data { 23 scan.bytes++ 24 if scan.step(scan, c) == scanError { 25 return scan.err 26 } 27 } 28 if scan.eof() == scanError { 29 return scan.err 30 } 31 return nil 32} 33 34// nextValue splits data after the next whole JSON value, 35// returning that value and the bytes that follow it as separate slices. 36// scan is passed in for use by nextValue to avoid an allocation. 37func nextValue(data []byte, scan *scanner) (value, rest []byte, err error) { 38 scan.reset() 39 for i, c := range data { 40 v := scan.step(scan, c) 41 if v >= scanEndObject { 42 switch v { 43 // probe the scanner with a space to determine whether we will 44 // get scanEnd on the next character. Otherwise, if the next character 45 // is not a space, scanEndTop allocates a needless error. 46 case scanEndObject, scanEndArray: 47 if scan.step(scan, ' ') == scanEnd { 48 return data[:i+1], data[i+1:], nil 49 } 50 case scanError: 51 return nil, nil, scan.err 52 case scanEnd: 53 return data[:i], data[i:], nil 54 } 55 } 56 } 57 if scan.eof() == scanError { 58 return nil, nil, scan.err 59 } 60 return data, nil, nil 61} 62 63// A SyntaxError is a description of a JSON syntax error. 64type SyntaxError struct { 65 msg string // description of error 66 Offset int64 // error occurred after reading Offset bytes 67} 68 69func (e *SyntaxError) Error() string { return e.msg } 70 71// A scanner is a JSON scanning state machine. 72// Callers call scan.reset() and then pass bytes in one at a time 73// by calling scan.step(&scan, c) for each byte. 74// The return value, referred to as an opcode, tells the 75// caller about significant parsing events like beginning 76// and ending literals, objects, and arrays, so that the 77// caller can follow along if it wishes. 78// The return value scanEnd indicates that a single top-level 79// JSON value has been completed, *before* the byte that 80// just got passed in. (The indication must be delayed in order 81// to recognize the end of numbers: is 123 a whole value or 82// the beginning of 12345e+6?). 83type scanner struct { 84 // The step is a func to be called to execute the next transition. 85 // Also tried using an integer constant and a single func 86 // with a switch, but using the func directly was 10% faster 87 // on a 64-bit Mac Mini, and it's nicer to read. 88 step func(*scanner, byte) int 89 90 // Reached end of top-level value. 91 endTop bool 92 93 // Stack of what we're in the middle of - array values, object keys, object values. 94 parseState []int 95 96 // Error that happened, if any. 97 err error 98 99 // 1-byte redo (see undo method) 100 redo bool 101 redoCode int 102 redoState func(*scanner, byte) int 103 104 // total bytes consumed, updated by decoder.Decode 105 bytes int64 106} 107 108// These values are returned by the state transition functions 109// assigned to scanner.state and the method scanner.eof. 110// They give details about the current state of the scan that 111// callers might be interested to know about. 112// It is okay to ignore the return value of any particular 113// call to scanner.state: if one call returns scanError, 114// every subsequent call will return scanError too. 115const ( 116 // Continue. 117 scanContinue = iota // uninteresting byte 118 scanBeginLiteral // end implied by next result != scanContinue 119 scanBeginObject // begin object 120 scanObjectKey // just finished object key (string) 121 scanObjectValue // just finished non-last object value 122 scanEndObject // end object (implies scanObjectValue if possible) 123 scanBeginArray // begin array 124 scanArrayValue // just finished array value 125 scanEndArray // end array (implies scanArrayValue if possible) 126 scanSkipSpace // space byte; can skip; known to be last "continue" result 127 128 // Stop. 129 scanEnd // top-level value ended *before* this byte; known to be first "stop" result 130 scanError // hit an error, scanner.err. 131) 132 133// These values are stored in the parseState stack. 134// They give the current state of a composite value 135// being scanned. If the parser is inside a nested value 136// the parseState describes the nested state, outermost at entry 0. 137const ( 138 parseObjectKey = iota // parsing object key (before colon) 139 parseObjectValue // parsing object value (after colon) 140 parseArrayValue // parsing array value 141) 142 143// reset prepares the scanner for use. 144// It must be called before calling s.step. 145func (s *scanner) reset() { 146 s.step = stateBeginValue 147 s.parseState = s.parseState[0:0] 148 s.err = nil 149 s.redo = false 150 s.endTop = false 151} 152 153// eof tells the scanner that the end of input has been reached. 154// It returns a scan status just as s.step does. 155func (s *scanner) eof() int { 156 if s.err != nil { 157 return scanError 158 } 159 if s.endTop { 160 return scanEnd 161 } 162 s.step(s, ' ') 163 if s.endTop { 164 return scanEnd 165 } 166 if s.err == nil { 167 s.err = &SyntaxError{"unexpected end of JSON input", s.bytes} 168 } 169 return scanError 170} 171 172// pushParseState pushes a new parse state p onto the parse stack. 173func (s *scanner) pushParseState(p int) { 174 s.parseState = append(s.parseState, p) 175} 176 177// popParseState pops a parse state (already obtained) off the stack 178// and updates s.step accordingly. 179func (s *scanner) popParseState() { 180 n := len(s.parseState) - 1 181 s.parseState = s.parseState[0:n] 182 s.redo = false 183 if n == 0 { 184 s.step = stateEndTop 185 s.endTop = true 186 } else { 187 s.step = stateEndValue 188 } 189} 190 191func isSpace(c byte) bool { 192 return c == ' ' || c == '\t' || c == '\r' || c == '\n' 193} 194 195// stateBeginValueOrEmpty is the state after reading `[`. 196func stateBeginValueOrEmpty(s *scanner, c byte) int { 197 if c <= ' ' && isSpace(c) { 198 return scanSkipSpace 199 } 200 if c == ']' { 201 return stateEndValue(s, c) 202 } 203 return stateBeginValue(s, c) 204} 205 206// stateBeginValue is the state at the beginning of the input. 207func stateBeginValue(s *scanner, c byte) int { 208 if c <= ' ' && isSpace(c) { 209 return scanSkipSpace 210 } 211 switch c { 212 case '{': 213 s.step = stateBeginStringOrEmpty 214 s.pushParseState(parseObjectKey) 215 return scanBeginObject 216 case '[': 217 s.step = stateBeginValueOrEmpty 218 s.pushParseState(parseArrayValue) 219 return scanBeginArray 220 case '"': 221 s.step = stateInString 222 return scanBeginLiteral 223 case '-': 224 s.step = stateNeg 225 return scanBeginLiteral 226 case '0': // beginning of 0.123 227 s.step = state0 228 return scanBeginLiteral 229 case 't': // beginning of true 230 s.step = stateT 231 return scanBeginLiteral 232 case 'f': // beginning of false 233 s.step = stateF 234 return scanBeginLiteral 235 case 'n': // beginning of null 236 s.step = stateN 237 return scanBeginLiteral 238 } 239 if '1' <= c && c <= '9' { // beginning of 1234.5 240 s.step = state1 241 return scanBeginLiteral 242 } 243 return s.error(c, "looking for beginning of value") 244} 245 246// stateBeginStringOrEmpty is the state after reading `{`. 247func stateBeginStringOrEmpty(s *scanner, c byte) int { 248 if c <= ' ' && isSpace(c) { 249 return scanSkipSpace 250 } 251 if c == '}' { 252 n := len(s.parseState) 253 s.parseState[n-1] = parseObjectValue 254 return stateEndValue(s, c) 255 } 256 return stateBeginString(s, c) 257} 258 259// stateBeginString is the state after reading `{"key": value,`. 260func stateBeginString(s *scanner, c byte) int { 261 if c <= ' ' && isSpace(c) { 262 return scanSkipSpace 263 } 264 if c == '"' { 265 s.step = stateInString 266 return scanBeginLiteral 267 } 268 return s.error(c, "looking for beginning of object key string") 269} 270 271// stateEndValue is the state after completing a value, 272// such as after reading `{}` or `true` or `["x"`. 273func stateEndValue(s *scanner, c byte) int { 274 n := len(s.parseState) 275 if n == 0 { 276 // Completed top-level before the current byte. 277 s.step = stateEndTop 278 s.endTop = true 279 return stateEndTop(s, c) 280 } 281 if c <= ' ' && isSpace(c) { 282 s.step = stateEndValue 283 return scanSkipSpace 284 } 285 ps := s.parseState[n-1] 286 switch ps { 287 case parseObjectKey: 288 if c == ':' { 289 s.parseState[n-1] = parseObjectValue 290 s.step = stateBeginValue 291 return scanObjectKey 292 } 293 return s.error(c, "after object key") 294 case parseObjectValue: 295 if c == ',' { 296 s.parseState[n-1] = parseObjectKey 297 s.step = stateBeginString 298 return scanObjectValue 299 } 300 if c == '}' { 301 s.popParseState() 302 return scanEndObject 303 } 304 return s.error(c, "after object key:value pair") 305 case parseArrayValue: 306 if c == ',' { 307 s.step = stateBeginValue 308 return scanArrayValue 309 } 310 if c == ']' { 311 s.popParseState() 312 return scanEndArray 313 } 314 return s.error(c, "after array element") 315 } 316 return s.error(c, "") 317} 318 319// stateEndTop is the state after finishing the top-level value, 320// such as after reading `{}` or `[1,2,3]`. 321// Only space characters should be seen now. 322func stateEndTop(s *scanner, c byte) int { 323 if c != ' ' && c != '\t' && c != '\r' && c != '\n' { 324 // Complain about non-space byte on next call. 325 s.error(c, "after top-level value") 326 } 327 return scanEnd 328} 329 330// stateInString is the state after reading `"`. 331func stateInString(s *scanner, c byte) int { 332 if c == '"' { 333 s.step = stateEndValue 334 return scanContinue 335 } 336 if c == '\\' { 337 s.step = stateInStringEsc 338 return scanContinue 339 } 340 if c < 0x20 { 341 return s.error(c, "in string literal") 342 } 343 return scanContinue 344} 345 346// stateInStringEsc is the state after reading `"\` during a quoted string. 347func stateInStringEsc(s *scanner, c byte) int { 348 switch c { 349 case 'b', 'f', 'n', 'r', 't', '\\', '/', '"': 350 s.step = stateInString 351 return scanContinue 352 case 'u': 353 s.step = stateInStringEscU 354 return scanContinue 355 } 356 return s.error(c, "in string escape code") 357} 358 359// stateInStringEscU is the state after reading `"\u` during a quoted string. 360func stateInStringEscU(s *scanner, c byte) int { 361 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 362 s.step = stateInStringEscU1 363 return scanContinue 364 } 365 // numbers 366 return s.error(c, "in \\u hexadecimal character escape") 367} 368 369// stateInStringEscU1 is the state after reading `"\u1` during a quoted string. 370func stateInStringEscU1(s *scanner, c byte) int { 371 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 372 s.step = stateInStringEscU12 373 return scanContinue 374 } 375 // numbers 376 return s.error(c, "in \\u hexadecimal character escape") 377} 378 379// stateInStringEscU12 is the state after reading `"\u12` during a quoted string. 380func stateInStringEscU12(s *scanner, c byte) int { 381 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 382 s.step = stateInStringEscU123 383 return scanContinue 384 } 385 // numbers 386 return s.error(c, "in \\u hexadecimal character escape") 387} 388 389// stateInStringEscU123 is the state after reading `"\u123` during a quoted string. 390func stateInStringEscU123(s *scanner, c byte) int { 391 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 392 s.step = stateInString 393 return scanContinue 394 } 395 // numbers 396 return s.error(c, "in \\u hexadecimal character escape") 397} 398 399// stateNeg is the state after reading `-` during a number. 400func stateNeg(s *scanner, c byte) int { 401 if c == '0' { 402 s.step = state0 403 return scanContinue 404 } 405 if '1' <= c && c <= '9' { 406 s.step = state1 407 return scanContinue 408 } 409 return s.error(c, "in numeric literal") 410} 411 412// state1 is the state after reading a non-zero integer during a number, 413// such as after reading `1` or `100` but not `0`. 414func state1(s *scanner, c byte) int { 415 if '0' <= c && c <= '9' { 416 s.step = state1 417 return scanContinue 418 } 419 return state0(s, c) 420} 421 422// state0 is the state after reading `0` during a number. 423func state0(s *scanner, c byte) int { 424 if c == '.' { 425 s.step = stateDot 426 return scanContinue 427 } 428 if c == 'e' || c == 'E' { 429 s.step = stateE 430 return scanContinue 431 } 432 return stateEndValue(s, c) 433} 434 435// stateDot is the state after reading the integer and decimal point in a number, 436// such as after reading `1.`. 437func stateDot(s *scanner, c byte) int { 438 if '0' <= c && c <= '9' { 439 s.step = stateDot0 440 return scanContinue 441 } 442 return s.error(c, "after decimal point in numeric literal") 443} 444 445// stateDot0 is the state after reading the integer, decimal point, and subsequent 446// digits of a number, such as after reading `3.14`. 447func stateDot0(s *scanner, c byte) int { 448 if '0' <= c && c <= '9' { 449 return scanContinue 450 } 451 if c == 'e' || c == 'E' { 452 s.step = stateE 453 return scanContinue 454 } 455 return stateEndValue(s, c) 456} 457 458// stateE is the state after reading the mantissa and e in a number, 459// such as after reading `314e` or `0.314e`. 460func stateE(s *scanner, c byte) int { 461 if c == '+' || c == '-' { 462 s.step = stateESign 463 return scanContinue 464 } 465 return stateESign(s, c) 466} 467 468// stateESign is the state after reading the mantissa, e, and sign in a number, 469// such as after reading `314e-` or `0.314e+`. 470func stateESign(s *scanner, c byte) int { 471 if '0' <= c && c <= '9' { 472 s.step = stateE0 473 return scanContinue 474 } 475 return s.error(c, "in exponent of numeric literal") 476} 477 478// stateE0 is the state after reading the mantissa, e, optional sign, 479// and at least one digit of the exponent in a number, 480// such as after reading `314e-2` or `0.314e+1` or `3.14e0`. 481func stateE0(s *scanner, c byte) int { 482 if '0' <= c && c <= '9' { 483 return scanContinue 484 } 485 return stateEndValue(s, c) 486} 487 488// stateT is the state after reading `t`. 489func stateT(s *scanner, c byte) int { 490 if c == 'r' { 491 s.step = stateTr 492 return scanContinue 493 } 494 return s.error(c, "in literal true (expecting 'r')") 495} 496 497// stateTr is the state after reading `tr`. 498func stateTr(s *scanner, c byte) int { 499 if c == 'u' { 500 s.step = stateTru 501 return scanContinue 502 } 503 return s.error(c, "in literal true (expecting 'u')") 504} 505 506// stateTru is the state after reading `tru`. 507func stateTru(s *scanner, c byte) int { 508 if c == 'e' { 509 s.step = stateEndValue 510 return scanContinue 511 } 512 return s.error(c, "in literal true (expecting 'e')") 513} 514 515// stateF is the state after reading `f`. 516func stateF(s *scanner, c byte) int { 517 if c == 'a' { 518 s.step = stateFa 519 return scanContinue 520 } 521 return s.error(c, "in literal false (expecting 'a')") 522} 523 524// stateFa is the state after reading `fa`. 525func stateFa(s *scanner, c byte) int { 526 if c == 'l' { 527 s.step = stateFal 528 return scanContinue 529 } 530 return s.error(c, "in literal false (expecting 'l')") 531} 532 533// stateFal is the state after reading `fal`. 534func stateFal(s *scanner, c byte) int { 535 if c == 's' { 536 s.step = stateFals 537 return scanContinue 538 } 539 return s.error(c, "in literal false (expecting 's')") 540} 541 542// stateFals is the state after reading `fals`. 543func stateFals(s *scanner, c byte) int { 544 if c == 'e' { 545 s.step = stateEndValue 546 return scanContinue 547 } 548 return s.error(c, "in literal false (expecting 'e')") 549} 550 551// stateN is the state after reading `n`. 552func stateN(s *scanner, c byte) int { 553 if c == 'u' { 554 s.step = stateNu 555 return scanContinue 556 } 557 return s.error(c, "in literal null (expecting 'u')") 558} 559 560// stateNu is the state after reading `nu`. 561func stateNu(s *scanner, c byte) int { 562 if c == 'l' { 563 s.step = stateNul 564 return scanContinue 565 } 566 return s.error(c, "in literal null (expecting 'l')") 567} 568 569// stateNul is the state after reading `nul`. 570func stateNul(s *scanner, c byte) int { 571 if c == 'l' { 572 s.step = stateEndValue 573 return scanContinue 574 } 575 return s.error(c, "in literal null (expecting 'l')") 576} 577 578// stateError is the state after reaching a syntax error, 579// such as after reading `[1}` or `5.1.2`. 580func stateError(s *scanner, c byte) int { 581 return scanError 582} 583 584// error records an error and switches to the error state. 585func (s *scanner) error(c byte, context string) int { 586 s.step = stateError 587 s.err = &SyntaxError{"invalid character " + quoteChar(c) + " " + context, s.bytes} 588 return scanError 589} 590 591// quoteChar formats c as a quoted character literal 592func quoteChar(c byte) string { 593 // special cases - different from quoted strings 594 if c == '\'' { 595 return `'\''` 596 } 597 if c == '"' { 598 return `'"'` 599 } 600 601 // use quoted string with different quotation marks 602 s := strconv.Quote(string(c)) 603 return "'" + s[1:len(s)-1] + "'" 604} 605 606// undo causes the scanner to return scanCode from the next state transition. 607// This gives callers a simple 1-byte undo mechanism. 608func (s *scanner) undo(scanCode int) { 609 if s.redo { 610 panic("json: invalid use of scanner") 611 } 612 s.redoCode = scanCode 613 s.redoState = s.step 614 s.step = stateRedo 615 s.redo = true 616} 617 618// stateRedo helps implement the scanner's 1-byte undo. 619func stateRedo(s *scanner, c byte) int { 620 s.redo = false 621 s.step = s.redoState 622 return s.redoCode 623} 624