1// Copyright 2018 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 text 6 7import ( 8 "bytes" 9 "fmt" 10 "io" 11 "strconv" 12 "unicode/utf8" 13 14 "google.golang.org/protobuf/internal/errors" 15) 16 17// Decoder is a token-based textproto decoder. 18type Decoder struct { 19 // lastCall is last method called, either readCall or peekCall. 20 // Initial value is readCall. 21 lastCall call 22 23 // lastToken contains the last read token. 24 lastToken Token 25 26 // lastErr contains the last read error. 27 lastErr error 28 29 // openStack is a stack containing the byte characters for MessageOpen and 30 // ListOpen kinds. The top of stack represents the message or the list that 31 // the current token is nested in. An empty stack means the current token is 32 // at the top level message. The characters '{' and '<' both represent the 33 // MessageOpen kind. 34 openStack []byte 35 36 // orig is used in reporting line and column. 37 orig []byte 38 // in contains the unconsumed input. 39 in []byte 40} 41 42// NewDecoder returns a Decoder to read the given []byte. 43func NewDecoder(b []byte) *Decoder { 44 return &Decoder{orig: b, in: b} 45} 46 47// ErrUnexpectedEOF means that EOF was encountered in the middle of the input. 48var ErrUnexpectedEOF = errors.New("%v", io.ErrUnexpectedEOF) 49 50// call specifies which Decoder method was invoked. 51type call uint8 52 53const ( 54 readCall call = iota 55 peekCall 56) 57 58// Peek looks ahead and returns the next token and error without advancing a read. 59func (d *Decoder) Peek() (Token, error) { 60 defer func() { d.lastCall = peekCall }() 61 if d.lastCall == readCall { 62 d.lastToken, d.lastErr = d.Read() 63 } 64 return d.lastToken, d.lastErr 65} 66 67// Read returns the next token. 68// It will return an error if there is no valid token. 69func (d *Decoder) Read() (Token, error) { 70 defer func() { d.lastCall = readCall }() 71 if d.lastCall == peekCall { 72 return d.lastToken, d.lastErr 73 } 74 75 tok, err := d.parseNext(d.lastToken.kind) 76 if err != nil { 77 return Token{}, err 78 } 79 80 switch tok.kind { 81 case comma, semicolon: 82 tok, err = d.parseNext(tok.kind) 83 if err != nil { 84 return Token{}, err 85 } 86 } 87 d.lastToken = tok 88 return tok, nil 89} 90 91const ( 92 mismatchedFmt = "mismatched close character %q" 93 unexpectedFmt = "unexpected character %q" 94) 95 96// parseNext parses the next Token based on given last kind. 97func (d *Decoder) parseNext(lastKind Kind) (Token, error) { 98 // Trim leading spaces. 99 d.consume(0) 100 isEOF := false 101 if len(d.in) == 0 { 102 isEOF = true 103 } 104 105 switch lastKind { 106 case EOF: 107 return d.consumeToken(EOF, 0, 0), nil 108 109 case bof: 110 // Start of top level message. Next token can be EOF or Name. 111 if isEOF { 112 return d.consumeToken(EOF, 0, 0), nil 113 } 114 return d.parseFieldName() 115 116 case Name: 117 // Next token can be MessageOpen, ListOpen or Scalar. 118 if isEOF { 119 return Token{}, ErrUnexpectedEOF 120 } 121 switch ch := d.in[0]; ch { 122 case '{', '<': 123 d.pushOpenStack(ch) 124 return d.consumeToken(MessageOpen, 1, 0), nil 125 case '[': 126 d.pushOpenStack(ch) 127 return d.consumeToken(ListOpen, 1, 0), nil 128 default: 129 return d.parseScalar() 130 } 131 132 case Scalar: 133 openKind, closeCh := d.currentOpenKind() 134 switch openKind { 135 case bof: 136 // Top level message. 137 // Next token can be EOF, comma, semicolon or Name. 138 if isEOF { 139 return d.consumeToken(EOF, 0, 0), nil 140 } 141 switch d.in[0] { 142 case ',': 143 return d.consumeToken(comma, 1, 0), nil 144 case ';': 145 return d.consumeToken(semicolon, 1, 0), nil 146 default: 147 return d.parseFieldName() 148 } 149 150 case MessageOpen: 151 // Next token can be MessageClose, comma, semicolon or Name. 152 if isEOF { 153 return Token{}, ErrUnexpectedEOF 154 } 155 switch ch := d.in[0]; ch { 156 case closeCh: 157 d.popOpenStack() 158 return d.consumeToken(MessageClose, 1, 0), nil 159 case otherCloseChar[closeCh]: 160 return Token{}, d.newSyntaxError(mismatchedFmt, ch) 161 case ',': 162 return d.consumeToken(comma, 1, 0), nil 163 case ';': 164 return d.consumeToken(semicolon, 1, 0), nil 165 default: 166 return d.parseFieldName() 167 } 168 169 case ListOpen: 170 // Next token can be ListClose or comma. 171 if isEOF { 172 return Token{}, ErrUnexpectedEOF 173 } 174 switch ch := d.in[0]; ch { 175 case ']': 176 d.popOpenStack() 177 return d.consumeToken(ListClose, 1, 0), nil 178 case ',': 179 return d.consumeToken(comma, 1, 0), nil 180 default: 181 return Token{}, d.newSyntaxError(unexpectedFmt, ch) 182 } 183 } 184 185 case MessageOpen: 186 // Next token can be MessageClose or Name. 187 if isEOF { 188 return Token{}, ErrUnexpectedEOF 189 } 190 _, closeCh := d.currentOpenKind() 191 switch ch := d.in[0]; ch { 192 case closeCh: 193 d.popOpenStack() 194 return d.consumeToken(MessageClose, 1, 0), nil 195 case otherCloseChar[closeCh]: 196 return Token{}, d.newSyntaxError(mismatchedFmt, ch) 197 default: 198 return d.parseFieldName() 199 } 200 201 case MessageClose: 202 openKind, closeCh := d.currentOpenKind() 203 switch openKind { 204 case bof: 205 // Top level message. 206 // Next token can be EOF, comma, semicolon or Name. 207 if isEOF { 208 return d.consumeToken(EOF, 0, 0), nil 209 } 210 switch ch := d.in[0]; ch { 211 case ',': 212 return d.consumeToken(comma, 1, 0), nil 213 case ';': 214 return d.consumeToken(semicolon, 1, 0), nil 215 default: 216 return d.parseFieldName() 217 } 218 219 case MessageOpen: 220 // Next token can be MessageClose, comma, semicolon or Name. 221 if isEOF { 222 return Token{}, ErrUnexpectedEOF 223 } 224 switch ch := d.in[0]; ch { 225 case closeCh: 226 d.popOpenStack() 227 return d.consumeToken(MessageClose, 1, 0), nil 228 case otherCloseChar[closeCh]: 229 return Token{}, d.newSyntaxError(mismatchedFmt, ch) 230 case ',': 231 return d.consumeToken(comma, 1, 0), nil 232 case ';': 233 return d.consumeToken(semicolon, 1, 0), nil 234 default: 235 return d.parseFieldName() 236 } 237 238 case ListOpen: 239 // Next token can be ListClose or comma 240 if isEOF { 241 return Token{}, ErrUnexpectedEOF 242 } 243 switch ch := d.in[0]; ch { 244 case closeCh: 245 d.popOpenStack() 246 return d.consumeToken(ListClose, 1, 0), nil 247 case ',': 248 return d.consumeToken(comma, 1, 0), nil 249 default: 250 return Token{}, d.newSyntaxError(unexpectedFmt, ch) 251 } 252 } 253 254 case ListOpen: 255 // Next token can be ListClose, MessageStart or Scalar. 256 if isEOF { 257 return Token{}, ErrUnexpectedEOF 258 } 259 switch ch := d.in[0]; ch { 260 case ']': 261 d.popOpenStack() 262 return d.consumeToken(ListClose, 1, 0), nil 263 case '{', '<': 264 d.pushOpenStack(ch) 265 return d.consumeToken(MessageOpen, 1, 0), nil 266 default: 267 return d.parseScalar() 268 } 269 270 case ListClose: 271 openKind, closeCh := d.currentOpenKind() 272 switch openKind { 273 case bof: 274 // Top level message. 275 // Next token can be EOF, comma, semicolon or Name. 276 if isEOF { 277 return d.consumeToken(EOF, 0, 0), nil 278 } 279 switch ch := d.in[0]; ch { 280 case ',': 281 return d.consumeToken(comma, 1, 0), nil 282 case ';': 283 return d.consumeToken(semicolon, 1, 0), nil 284 default: 285 return d.parseFieldName() 286 } 287 288 case MessageOpen: 289 // Next token can be MessageClose, comma, semicolon or Name. 290 if isEOF { 291 return Token{}, ErrUnexpectedEOF 292 } 293 switch ch := d.in[0]; ch { 294 case closeCh: 295 d.popOpenStack() 296 return d.consumeToken(MessageClose, 1, 0), nil 297 case otherCloseChar[closeCh]: 298 return Token{}, d.newSyntaxError(mismatchedFmt, ch) 299 case ',': 300 return d.consumeToken(comma, 1, 0), nil 301 case ';': 302 return d.consumeToken(semicolon, 1, 0), nil 303 default: 304 return d.parseFieldName() 305 } 306 307 default: 308 // It is not possible to have this case. Let it panic below. 309 } 310 311 case comma, semicolon: 312 openKind, closeCh := d.currentOpenKind() 313 switch openKind { 314 case bof: 315 // Top level message. Next token can be EOF or Name. 316 if isEOF { 317 return d.consumeToken(EOF, 0, 0), nil 318 } 319 return d.parseFieldName() 320 321 case MessageOpen: 322 // Next token can be MessageClose or Name. 323 if isEOF { 324 return Token{}, ErrUnexpectedEOF 325 } 326 switch ch := d.in[0]; ch { 327 case closeCh: 328 d.popOpenStack() 329 return d.consumeToken(MessageClose, 1, 0), nil 330 case otherCloseChar[closeCh]: 331 return Token{}, d.newSyntaxError(mismatchedFmt, ch) 332 default: 333 return d.parseFieldName() 334 } 335 336 case ListOpen: 337 if lastKind == semicolon { 338 // It is not be possible to have this case as logic here 339 // should not have produced a semicolon Token when inside a 340 // list. Let it panic below. 341 break 342 } 343 // Next token can be MessageOpen or Scalar. 344 if isEOF { 345 return Token{}, ErrUnexpectedEOF 346 } 347 switch ch := d.in[0]; ch { 348 case '{', '<': 349 d.pushOpenStack(ch) 350 return d.consumeToken(MessageOpen, 1, 0), nil 351 default: 352 return d.parseScalar() 353 } 354 } 355 } 356 357 line, column := d.Position(len(d.orig) - len(d.in)) 358 panic(fmt.Sprintf("Decoder.parseNext: bug at handling line %d:%d with lastKind=%v", line, column, lastKind)) 359} 360 361var otherCloseChar = map[byte]byte{ 362 '}': '>', 363 '>': '}', 364} 365 366// currentOpenKind indicates whether current position is inside a message, list 367// or top-level message by returning MessageOpen, ListOpen or bof respectively. 368// If the returned kind is either a MessageOpen or ListOpen, it also returns the 369// corresponding closing character. 370func (d *Decoder) currentOpenKind() (Kind, byte) { 371 if len(d.openStack) == 0 { 372 return bof, 0 373 } 374 openCh := d.openStack[len(d.openStack)-1] 375 switch openCh { 376 case '{': 377 return MessageOpen, '}' 378 case '<': 379 return MessageOpen, '>' 380 case '[': 381 return ListOpen, ']' 382 } 383 panic(fmt.Sprintf("Decoder: openStack contains invalid byte %c", openCh)) 384} 385 386func (d *Decoder) pushOpenStack(ch byte) { 387 d.openStack = append(d.openStack, ch) 388} 389 390func (d *Decoder) popOpenStack() { 391 d.openStack = d.openStack[:len(d.openStack)-1] 392} 393 394// parseFieldName parses field name and separator. 395func (d *Decoder) parseFieldName() (tok Token, err error) { 396 defer func() { 397 if err == nil && d.tryConsumeChar(':') { 398 tok.attrs |= hasSeparator 399 } 400 }() 401 402 // Extension or Any type URL. 403 if d.in[0] == '[' { 404 return d.parseTypeName() 405 } 406 407 // Identifier. 408 if size := parseIdent(d.in, false); size > 0 { 409 return d.consumeToken(Name, size, uint8(IdentName)), nil 410 } 411 412 // Field number. Identify if input is a valid number that is not negative 413 // and is decimal integer within 32-bit range. 414 if num := parseNumber(d.in); num.size > 0 { 415 str := num.string(d.in) 416 if !num.neg && num.kind == numDec { 417 if _, err := strconv.ParseInt(str, 10, 32); err == nil { 418 return d.consumeToken(Name, num.size, uint8(FieldNumber)), nil 419 } 420 } 421 return Token{}, d.newSyntaxError("invalid field number: %s", str) 422 } 423 424 return Token{}, d.newSyntaxError("invalid field name: %s", errId(d.in)) 425} 426 427// parseTypeName parses Any type URL or extension field name. The name is 428// enclosed in [ and ] characters. The C++ parser does not handle many legal URL 429// strings. This implementation is more liberal and allows for the pattern 430// ^[-_a-zA-Z0-9]+([./][-_a-zA-Z0-9]+)*`). Whitespaces and comments are allowed 431// in between [ ], '.', '/' and the sub names. 432func (d *Decoder) parseTypeName() (Token, error) { 433 startPos := len(d.orig) - len(d.in) 434 // Use alias s to advance first in order to use d.in for error handling. 435 // Caller already checks for [ as first character. 436 s := consume(d.in[1:], 0) 437 if len(s) == 0 { 438 return Token{}, ErrUnexpectedEOF 439 } 440 441 var name []byte 442 for len(s) > 0 && isTypeNameChar(s[0]) { 443 name = append(name, s[0]) 444 s = s[1:] 445 } 446 s = consume(s, 0) 447 448 var closed bool 449 for len(s) > 0 && !closed { 450 switch { 451 case s[0] == ']': 452 s = s[1:] 453 closed = true 454 455 case s[0] == '/', s[0] == '.': 456 if len(name) > 0 && (name[len(name)-1] == '/' || name[len(name)-1] == '.') { 457 return Token{}, d.newSyntaxError("invalid type URL/extension field name: %s", 458 d.orig[startPos:len(d.orig)-len(s)+1]) 459 } 460 name = append(name, s[0]) 461 s = s[1:] 462 s = consume(s, 0) 463 for len(s) > 0 && isTypeNameChar(s[0]) { 464 name = append(name, s[0]) 465 s = s[1:] 466 } 467 s = consume(s, 0) 468 469 default: 470 return Token{}, d.newSyntaxError( 471 "invalid type URL/extension field name: %s", d.orig[startPos:len(d.orig)-len(s)+1]) 472 } 473 } 474 475 if !closed { 476 return Token{}, ErrUnexpectedEOF 477 } 478 479 // First character cannot be '.'. Last character cannot be '.' or '/'. 480 size := len(name) 481 if size == 0 || name[0] == '.' || name[size-1] == '.' || name[size-1] == '/' { 482 return Token{}, d.newSyntaxError("invalid type URL/extension field name: %s", 483 d.orig[startPos:len(d.orig)-len(s)]) 484 } 485 486 d.in = s 487 endPos := len(d.orig) - len(d.in) 488 d.consume(0) 489 490 return Token{ 491 kind: Name, 492 attrs: uint8(TypeName), 493 pos: startPos, 494 raw: d.orig[startPos:endPos], 495 str: string(name), 496 }, nil 497} 498 499func isTypeNameChar(b byte) bool { 500 return (b == '-' || b == '_' || 501 ('0' <= b && b <= '9') || 502 ('a' <= b && b <= 'z') || 503 ('A' <= b && b <= 'Z')) 504} 505 506func isWhiteSpace(b byte) bool { 507 switch b { 508 case ' ', '\n', '\r', '\t': 509 return true 510 default: 511 return false 512 } 513} 514 515// parseIdent parses an unquoted proto identifier and returns size. 516// If allowNeg is true, it allows '-' to be the first character in the 517// identifier. This is used when parsing literal values like -infinity, etc. 518// Regular expression matches an identifier: `^[_a-zA-Z][_a-zA-Z0-9]*` 519func parseIdent(input []byte, allowNeg bool) int { 520 var size int 521 522 s := input 523 if len(s) == 0 { 524 return 0 525 } 526 527 if allowNeg && s[0] == '-' { 528 s = s[1:] 529 size++ 530 if len(s) == 0 { 531 return 0 532 } 533 } 534 535 switch { 536 case s[0] == '_', 537 'a' <= s[0] && s[0] <= 'z', 538 'A' <= s[0] && s[0] <= 'Z': 539 s = s[1:] 540 size++ 541 default: 542 return 0 543 } 544 545 for len(s) > 0 && (s[0] == '_' || 546 'a' <= s[0] && s[0] <= 'z' || 547 'A' <= s[0] && s[0] <= 'Z' || 548 '0' <= s[0] && s[0] <= '9') { 549 s = s[1:] 550 size++ 551 } 552 553 if len(s) > 0 && !isDelim(s[0]) { 554 return 0 555 } 556 557 return size 558} 559 560// parseScalar parses for a string, literal or number value. 561func (d *Decoder) parseScalar() (Token, error) { 562 if d.in[0] == '"' || d.in[0] == '\'' { 563 return d.parseStringValue() 564 } 565 566 if tok, ok := d.parseLiteralValue(); ok { 567 return tok, nil 568 } 569 570 if tok, ok := d.parseNumberValue(); ok { 571 return tok, nil 572 } 573 574 return Token{}, d.newSyntaxError("invalid scalar value: %s", errId(d.in)) 575} 576 577// parseLiteralValue parses a literal value. A literal value is used for 578// bools, special floats and enums. This function simply identifies that the 579// field value is a literal. 580func (d *Decoder) parseLiteralValue() (Token, bool) { 581 size := parseIdent(d.in, true) 582 if size == 0 { 583 return Token{}, false 584 } 585 return d.consumeToken(Scalar, size, literalValue), true 586} 587 588// consumeToken constructs a Token for given Kind from d.in and consumes given 589// size-length from it. 590func (d *Decoder) consumeToken(kind Kind, size int, attrs uint8) Token { 591 // Important to compute raw and pos before consuming. 592 tok := Token{ 593 kind: kind, 594 attrs: attrs, 595 pos: len(d.orig) - len(d.in), 596 raw: d.in[:size], 597 } 598 d.consume(size) 599 return tok 600} 601 602// newSyntaxError returns a syntax error with line and column information for 603// current position. 604func (d *Decoder) newSyntaxError(f string, x ...interface{}) error { 605 e := errors.New(f, x...) 606 line, column := d.Position(len(d.orig) - len(d.in)) 607 return errors.New("syntax error (line %d:%d): %v", line, column, e) 608} 609 610// Position returns line and column number of given index of the original input. 611// It will panic if index is out of range. 612func (d *Decoder) Position(idx int) (line int, column int) { 613 b := d.orig[:idx] 614 line = bytes.Count(b, []byte("\n")) + 1 615 if i := bytes.LastIndexByte(b, '\n'); i >= 0 { 616 b = b[i+1:] 617 } 618 column = utf8.RuneCount(b) + 1 // ignore multi-rune characters 619 return line, column 620} 621 622func (d *Decoder) tryConsumeChar(c byte) bool { 623 if len(d.in) > 0 && d.in[0] == c { 624 d.consume(1) 625 return true 626 } 627 return false 628} 629 630// consume consumes n bytes of input and any subsequent whitespace or comments. 631func (d *Decoder) consume(n int) { 632 d.in = consume(d.in, n) 633 return 634} 635 636// consume consumes n bytes of input and any subsequent whitespace or comments. 637func consume(b []byte, n int) []byte { 638 b = b[n:] 639 for len(b) > 0 { 640 switch b[0] { 641 case ' ', '\n', '\r', '\t': 642 b = b[1:] 643 case '#': 644 if i := bytes.IndexByte(b, '\n'); i >= 0 { 645 b = b[i+len("\n"):] 646 } else { 647 b = nil 648 } 649 default: 650 return b 651 } 652 } 653 return b 654} 655 656// errId extracts a byte sequence that looks like an invalid ID 657// (for the purposes of error reporting). 658func errId(seq []byte) []byte { 659 const maxLen = 32 660 for i := 0; i < len(seq); { 661 if i > maxLen { 662 return append(seq[:i:i], "…"...) 663 } 664 r, size := utf8.DecodeRune(seq[i:]) 665 if r > utf8.RuneSelf || (r != '/' && isDelim(byte(r))) { 666 if i == 0 { 667 // Either the first byte is invalid UTF-8 or a 668 // delimiter, or the first rune is non-ASCII. 669 // Return it as-is. 670 i = size 671 } 672 return seq[:i:i] 673 } 674 i += size 675 } 676 // No delimiter found. 677 return seq 678} 679 680// isDelim returns true if given byte is a delimiter character. 681func isDelim(c byte) bool { 682 return !(c == '-' || c == '+' || c == '.' || c == '_' || 683 ('a' <= c && c <= 'z') || 684 ('A' <= c && c <= 'Z') || 685 ('0' <= c && c <= '9')) 686} 687