Source file src/pkg/encoding/json/scanner.go
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 5 package 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 16 import "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. 20 func checkValid(data []byte, scan *scanner) error { 21 scan.reset() 22 for _, c := range data { 23 scan.bytes++ 24 if scan.step(scan, int(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. 37 func nextValue(data []byte, scan *scanner) (value, rest []byte, err error) { 38 scan.reset() 39 for i, c := range data { 40 v := scan.step(scan, int(c)) 41 if v >= scanEnd { 42 switch v { 43 case scanError: 44 return nil, nil, scan.err 45 case scanEnd: 46 return data[0:i], data[i:], nil 47 } 48 } 49 } 50 if scan.eof() == scanError { 51 return nil, nil, scan.err 52 } 53 return data, nil, nil 54 } 55 56 // A SyntaxError is a description of a JSON syntax error. 57 type SyntaxError struct { 58 msg string // description of error 59 Offset int64 // error occurred after reading Offset bytes 60 } 61 62 func (e *SyntaxError) Error() string { return e.msg } 63 64 // A scanner is a JSON scanning state machine. 65 // Callers call scan.reset() and then pass bytes in one at a time 66 // by calling scan.step(&scan, c) for each byte. 67 // The return value, referred to as an opcode, tells the 68 // caller about significant parsing events like beginning 69 // and ending literals, objects, and arrays, so that the 70 // caller can follow along if it wishes. 71 // The return value scanEnd indicates that a single top-level 72 // JSON value has been completed, *before* the byte that 73 // just got passed in. (The indication must be delayed in order 74 // to recognize the end of numbers: is 123 a whole value or 75 // the beginning of 12345e+6?). 76 type scanner struct { 77 // The step is a func to be called to execute the next transition. 78 // Also tried using an integer constant and a single func 79 // with a switch, but using the func directly was 10% faster 80 // on a 64-bit Mac Mini, and it's nicer to read. 81 step func(*scanner, int) int 82 83 // Reached end of top-level value. 84 endTop bool 85 86 // Stack of what we're in the middle of - array values, object keys, object values. 87 parseState []int 88 89 // Error that happened, if any. 90 err error 91 92 // 1-byte redo (see undo method) 93 redo bool 94 redoCode int 95 redoState func(*scanner, int) int 96 97 // total bytes consumed, updated by decoder.Decode 98 bytes int64 99 } 100 101 // These values are returned by the state transition functions 102 // assigned to scanner.state and the method scanner.eof. 103 // They give details about the current state of the scan that 104 // callers might be interested to know about. 105 // It is okay to ignore the return value of any particular 106 // call to scanner.state: if one call returns scanError, 107 // every subsequent call will return scanError too. 108 const ( 109 // Continue. 110 scanContinue = iota // uninteresting byte 111 scanBeginLiteral // end implied by next result != scanContinue 112 scanBeginObject // begin object 113 scanObjectKey // just finished object key (string) 114 scanObjectValue // just finished non-last object value 115 scanEndObject // end object (implies scanObjectValue if possible) 116 scanBeginArray // begin array 117 scanArrayValue // just finished array value 118 scanEndArray // end array (implies scanArrayValue if possible) 119 scanSkipSpace // space byte; can skip; known to be last "continue" result 120 121 // Stop. 122 scanEnd // top-level value ended *before* this byte; known to be first "stop" result 123 scanError // hit an error, scanner.err. 124 ) 125 126 // These values are stored in the parseState stack. 127 // They give the current state of a composite value 128 // being scanned. If the parser is inside a nested value 129 // the parseState describes the nested state, outermost at entry 0. 130 const ( 131 parseObjectKey = iota // parsing object key (before colon) 132 parseObjectValue // parsing object value (after colon) 133 parseArrayValue // parsing array value 134 ) 135 136 // reset prepares the scanner for use. 137 // It must be called before calling s.step. 138 func (s *scanner) reset() { 139 s.step = stateBeginValue 140 s.parseState = s.parseState[0:0] 141 s.err = nil 142 s.redo = false 143 s.endTop = false 144 } 145 146 // eof tells the scanner that the end of input has been reached. 147 // It returns a scan status just as s.step does. 148 func (s *scanner) eof() int { 149 if s.err != nil { 150 return scanError 151 } 152 if s.endTop { 153 return scanEnd 154 } 155 s.step(s, ' ') 156 if s.endTop { 157 return scanEnd 158 } 159 if s.err == nil { 160 s.err = &SyntaxError{"unexpected end of JSON input", s.bytes} 161 } 162 return scanError 163 } 164 165 // pushParseState pushes a new parse state p onto the parse stack. 166 func (s *scanner) pushParseState(p int) { 167 s.parseState = append(s.parseState, p) 168 } 169 170 // popParseState pops a parse state (already obtained) off the stack 171 // and updates s.step accordingly. 172 func (s *scanner) popParseState() { 173 n := len(s.parseState) - 1 174 s.parseState = s.parseState[0:n] 175 s.redo = false 176 if n == 0 { 177 s.step = stateEndTop 178 s.endTop = true 179 } else { 180 s.step = stateEndValue 181 } 182 } 183 184 func isSpace(c rune) bool { 185 return c == ' ' || c == '\t' || c == '\r' || c == '\n' 186 } 187 188 // stateBeginValueOrEmpty is the state after reading `[`. 189 func stateBeginValueOrEmpty(s *scanner, c int) int { 190 if c <= ' ' && isSpace(rune(c)) { 191 return scanSkipSpace 192 } 193 if c == ']' { 194 return stateEndValue(s, c) 195 } 196 return stateBeginValue(s, c) 197 } 198 199 // stateBeginValue is the state at the beginning of the input. 200 func stateBeginValue(s *scanner, c int) int { 201 if c <= ' ' && isSpace(rune(c)) { 202 return scanSkipSpace 203 } 204 switch c { 205 case '{': 206 s.step = stateBeginStringOrEmpty 207 s.pushParseState(parseObjectKey) 208 return scanBeginObject 209 case '[': 210 s.step = stateBeginValueOrEmpty 211 s.pushParseState(parseArrayValue) 212 return scanBeginArray 213 case '"': 214 s.step = stateInString 215 return scanBeginLiteral 216 case '-': 217 s.step = stateNeg 218 return scanBeginLiteral 219 case '0': // beginning of 0.123 220 s.step = state0 221 return scanBeginLiteral 222 case 't': // beginning of true 223 s.step = stateT 224 return scanBeginLiteral 225 case 'f': // beginning of false 226 s.step = stateF 227 return scanBeginLiteral 228 case 'n': // beginning of null 229 s.step = stateN 230 return scanBeginLiteral 231 } 232 if '1' <= c && c <= '9' { // beginning of 1234.5 233 s.step = state1 234 return scanBeginLiteral 235 } 236 return s.error(c, "looking for beginning of value") 237 } 238 239 // stateBeginStringOrEmpty is the state after reading `{`. 240 func stateBeginStringOrEmpty(s *scanner, c int) int { 241 if c <= ' ' && isSpace(rune(c)) { 242 return scanSkipSpace 243 } 244 if c == '}' { 245 n := len(s.parseState) 246 s.parseState[n-1] = parseObjectValue 247 return stateEndValue(s, c) 248 } 249 return stateBeginString(s, c) 250 } 251 252 // stateBeginString is the state after reading `{"key": value,`. 253 func stateBeginString(s *scanner, c int) int { 254 if c <= ' ' && isSpace(rune(c)) { 255 return scanSkipSpace 256 } 257 if c == '"' { 258 s.step = stateInString 259 return scanBeginLiteral 260 } 261 return s.error(c, "looking for beginning of object key string") 262 } 263 264 // stateEndValue is the state after completing a value, 265 // such as after reading `{}` or `true` or `["x"`. 266 func stateEndValue(s *scanner, c int) int { 267 n := len(s.parseState) 268 if n == 0 { 269 // Completed top-level before the current byte. 270 s.step = stateEndTop 271 s.endTop = true 272 return stateEndTop(s, c) 273 } 274 if c <= ' ' && isSpace(rune(c)) { 275 s.step = stateEndValue 276 return scanSkipSpace 277 } 278 ps := s.parseState[n-1] 279 switch ps { 280 case parseObjectKey: 281 if c == ':' { 282 s.parseState[n-1] = parseObjectValue 283 s.step = stateBeginValue 284 return scanObjectKey 285 } 286 return s.error(c, "after object key") 287 case parseObjectValue: 288 if c == ',' { 289 s.parseState[n-1] = parseObjectKey 290 s.step = stateBeginString 291 return scanObjectValue 292 } 293 if c == '}' { 294 s.popParseState() 295 return scanEndObject 296 } 297 return s.error(c, "after object key:value pair") 298 case parseArrayValue: 299 if c == ',' { 300 s.step = stateBeginValue 301 return scanArrayValue 302 } 303 if c == ']' { 304 s.popParseState() 305 return scanEndArray 306 } 307 return s.error(c, "after array element") 308 } 309 return s.error(c, "") 310 } 311 312 // stateEndTop is the state after finishing the top-level value, 313 // such as after reading `{}` or `[1,2,3]`. 314 // Only space characters should be seen now. 315 func stateEndTop(s *scanner, c int) int { 316 if c != ' ' && c != '\t' && c != '\r' && c != '\n' { 317 // Complain about non-space byte on next call. 318 s.error(c, "after top-level value") 319 } 320 return scanEnd 321 } 322 323 // stateInString is the state after reading `"`. 324 func stateInString(s *scanner, c int) int { 325 if c == '"' { 326 s.step = stateEndValue 327 return scanContinue 328 } 329 if c == '\\' { 330 s.step = stateInStringEsc 331 return scanContinue 332 } 333 if c < 0x20 { 334 return s.error(c, "in string literal") 335 } 336 return scanContinue 337 } 338 339 // stateInStringEsc is the state after reading `"\` during a quoted string. 340 func stateInStringEsc(s *scanner, c int) int { 341 switch c { 342 case 'b', 'f', 'n', 'r', 't', '\\', '/', '"': 343 s.step = stateInString 344 return scanContinue 345 } 346 if c == 'u' { 347 s.step = stateInStringEscU 348 return scanContinue 349 } 350 return s.error(c, "in string escape code") 351 } 352 353 // stateInStringEscU is the state after reading `"\u` during a quoted string. 354 func stateInStringEscU(s *scanner, c int) int { 355 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 356 s.step = stateInStringEscU1 357 return scanContinue 358 } 359 // numbers 360 return s.error(c, "in \\u hexadecimal character escape") 361 } 362 363 // stateInStringEscU1 is the state after reading `"\u1` during a quoted string. 364 func stateInStringEscU1(s *scanner, c int) int { 365 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 366 s.step = stateInStringEscU12 367 return scanContinue 368 } 369 // numbers 370 return s.error(c, "in \\u hexadecimal character escape") 371 } 372 373 // stateInStringEscU12 is the state after reading `"\u12` during a quoted string. 374 func stateInStringEscU12(s *scanner, c int) int { 375 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 376 s.step = stateInStringEscU123 377 return scanContinue 378 } 379 // numbers 380 return s.error(c, "in \\u hexadecimal character escape") 381 } 382 383 // stateInStringEscU123 is the state after reading `"\u123` during a quoted string. 384 func stateInStringEscU123(s *scanner, c int) int { 385 if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' { 386 s.step = stateInString 387 return scanContinue 388 } 389 // numbers 390 return s.error(c, "in \\u hexadecimal character escape") 391 } 392 393 // stateInStringEscU123 is the state after reading `-` during a number. 394 func stateNeg(s *scanner, c int) int { 395 if c == '0' { 396 s.step = state0 397 return scanContinue 398 } 399 if '1' <= c && c <= '9' { 400 s.step = state1 401 return scanContinue 402 } 403 return s.error(c, "in numeric literal") 404 } 405 406 // state1 is the state after reading a non-zero integer during a number, 407 // such as after reading `1` or `100` but not `0`. 408 func state1(s *scanner, c int) int { 409 if '0' <= c && c <= '9' { 410 s.step = state1 411 return scanContinue 412 } 413 return state0(s, c) 414 } 415 416 // state0 is the state after reading `0` during a number. 417 func state0(s *scanner, c int) int { 418 if c == '.' { 419 s.step = stateDot 420 return scanContinue 421 } 422 if c == 'e' || c == 'E' { 423 s.step = stateE 424 return scanContinue 425 } 426 return stateEndValue(s, c) 427 } 428 429 // stateDot is the state after reading the integer and decimal point in a number, 430 // such as after reading `1.`. 431 func stateDot(s *scanner, c int) int { 432 if '0' <= c && c <= '9' { 433 s.step = stateDot0 434 return scanContinue 435 } 436 return s.error(c, "after decimal point in numeric literal") 437 } 438 439 // stateDot0 is the state after reading the integer, decimal point, and subsequent 440 // digits of a number, such as after reading `3.14`. 441 func stateDot0(s *scanner, c int) int { 442 if '0' <= c && c <= '9' { 443 s.step = stateDot0 444 return scanContinue 445 } 446 if c == 'e' || c == 'E' { 447 s.step = stateE 448 return scanContinue 449 } 450 return stateEndValue(s, c) 451 } 452 453 // stateE is the state after reading the mantissa and e in a number, 454 // such as after reading `314e` or `0.314e`. 455 func stateE(s *scanner, c int) int { 456 if c == '+' { 457 s.step = stateESign 458 return scanContinue 459 } 460 if c == '-' { 461 s.step = stateESign 462 return scanContinue 463 } 464 return stateESign(s, c) 465 } 466 467 // stateESign is the state after reading the mantissa, e, and sign in a number, 468 // such as after reading `314e-` or `0.314e+`. 469 func stateESign(s *scanner, c int) int { 470 if '0' <= c && c <= '9' { 471 s.step = stateE0 472 return scanContinue 473 } 474 return s.error(c, "in exponent of numeric literal") 475 } 476 477 // stateE0 is the state after reading the mantissa, e, optional sign, 478 // and at least one digit of the exponent in a number, 479 // such as after reading `314e-2` or `0.314e+1` or `3.14e0`. 480 func stateE0(s *scanner, c int) int { 481 if '0' <= c && c <= '9' { 482 s.step = stateE0 483 return scanContinue 484 } 485 return stateEndValue(s, c) 486 } 487 488 // stateT is the state after reading `t`. 489 func stateT(s *scanner, c int) 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`. 498 func stateTr(s *scanner, c int) 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`. 507 func stateTru(s *scanner, c int) 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`. 516 func stateF(s *scanner, c int) 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`. 525 func stateFa(s *scanner, c int) 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`. 534 func stateFal(s *scanner, c int) 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`. 543 func stateFals(s *scanner, c int) 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`. 552 func stateN(s *scanner, c int) 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`. 561 func stateNu(s *scanner, c int) 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`. 570 func stateNul(s *scanner, c int) 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`. 580 func stateError(s *scanner, c int) int { 581 return scanError 582 } 583 584 // error records an error and switches to the error state. 585 func (s *scanner) error(c int, 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 592 func quoteChar(c int) 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. 608 func (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. 619 func stateRedo(s *scanner, c int) int { 620 s.redo = false 621 s.step = s.redoState 622 return s.redoCode 623 }