libgo/go/scanner/scanner.go

   1 // Copyright 2009 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 // A scanner and tokenizer for UTF-8-encoded text.  Takes an io.Reader
   6 // providing the source, which then can be tokenized through repeated calls
   7 // to the Scan function.  For compatibility with existing tools, the NUL
   8 // character is not allowed (implementation restriction).
   9 //
  10 // By default, a Scanner skips white space and Go comments and recognizes all
  11 // literals as defined by the Go language specification.  It may be
  12 // customized to recognize only a subset of those literals and to recognize
  13 // different white space characters.
  14 //
  15 // Basic usage pattern:
  16 //
  17 //      var s scanner.Scanner
  18 //      s.Init(src)
  19 //      tok := s.Scan()
  20 //      for tok != scanner.EOF {
  21 //              // do something with tok
  22 //              tok = s.Scan()
  23 //      }
  24 //
  25 package scanner
  26
  27 import (
  28         "bytes"
  29         "fmt"
  30         "io"
  31         "os"
  32         "unicode"
  33         "utf8"
  34 )
  35
  36
  37 // TODO(gri): Consider changing this to use the new (token) Position package.
  38
  39 // A source position is represented by a Position value.
  40 // A position is valid if Line > 0.
  41 type Position struct {
  42         Filename string // filename, if any
  43         Offset   int    // byte offset, starting at 0
  44         Line     int    // line number, starting at 1
  45         Column   int    // column number, starting at 1 (character count per line)
  46 }
  47
  48
  49 // IsValid returns true if the position is valid.
  50 func (pos *Position) IsValid() bool { return pos.Line > 0 }
  51
  52
  53 func (pos Position) String() string {
  54         s := pos.Filename
  55         if pos.IsValid() {
  56                 if s != "" {
  57                         s += ":"
  58                 }
  59                 s += fmt.Sprintf("%d:%d", pos.Line, pos.Column)
  60         }
  61         if s == "" {
  62                 s = "???"
  63         }
  64         return s
  65 }
  66
  67
  68 // Predefined mode bits to control recognition of tokens. For instance,
  69 // to configure a Scanner such that it only recognizes (Go) identifiers,
  70 // integers, and skips comments, set the Scanner's Mode field to:
  71 //
  72 //      ScanIdents | ScanInts | SkipComments
  73 //
  74 const (
  75         ScanIdents     = 1 << -Ident
  76         ScanInts       = 1 << -Int
  77         ScanFloats     = 1 << -Float // includes Ints
  78         ScanChars      = 1 << -Char
  79         ScanStrings    = 1 << -String
  80         ScanRawStrings = 1 << -RawString
  81         ScanComments   = 1 << -Comment
  82         SkipComments   = 1 << -skipComment // if set with ScanComments, comments become white space
  83         GoTokens       = ScanIdents | ScanFloats | ScanChars | ScanStrings | ScanRawStrings | ScanComments | SkipComments
  84 )
  85
  86
  87 // The result of Scan is one of the following tokens or a Unicode character.
  88 const (
  89         EOF = -(iota + 1)
  90         Ident
  91         Int
  92         Float
  93         Char
  94         String
  95         RawString
  96         Comment
  97         skipComment
  98 )
  99
 100
 101 var tokenString = map[int]string{
 102         EOF:       "EOF",
 103         Ident:     "Ident",
 104         Int:       "Int",
 105         Float:     "Float",
 106         Char:      "Char",
 107         String:    "String",
 108         RawString: "RawString",
 109         Comment:   "Comment",
 110 }
 111
 112
 113 // TokenString returns a (visible) string for a token or Unicode character.
 114 func TokenString(tok int) string {
 115         if s, found := tokenString[tok]; found {
 116                 return s
 117         }
 118         return fmt.Sprintf("U+%04X", tok)
 119 }
 120
 121
 122 // GoWhitespace is the default value for the Scanner's Whitespace field.
 123 // Its value selects Go's white space characters.
 124 const GoWhitespace = 1<<'\t' | 1<<'\n' | 1<<'\r' | 1<<' '
 125
 126
 127 const bufLen = 1024 // at least utf8.UTFMax
 128
 129 // A Scanner implements reading of Unicode characters and tokens from an io.Reader.
 130 type Scanner struct {
 131         // Input
 132         src io.Reader
 133
 134         // Source buffer
 135         srcBuf [bufLen + 1]byte // +1 for sentinel for common case of s.next()
 136         srcPos int              // reading position (srcBuf index)
 137         srcEnd int              // source end (srcBuf index)
 138
 139         // Source position
 140         srcBufOffset int // byte offset of srcBuf[0] in source
 141         line         int // line count
 142         column       int // character count
 143         lastLineLen  int // length of last line in characters (for correct column reporting)
 144         lastCharLen  int // length of last character in bytes
 145
 146         // Token text buffer
 147         // Typically, token text is stored completely in srcBuf, but in general
 148         // the token text's head may be buffered in tokBuf while the token text's
 149         // tail is stored in srcBuf.
 150         tokBuf bytes.Buffer // token text head that is not in srcBuf anymore
 151         tokPos int          // token text tail position (srcBuf index); valid if >= 0
 152         tokEnd int          // token text tail end (srcBuf index)
 153
 154         // One character look-ahead
 155         ch int // character before current srcPos
 156
 157         // Error is called for each error encountered. If no Error
 158         // function is set, the error is reported to os.Stderr.
 159         Error func(s *Scanner, msg string)
 160
 161         // ErrorCount is incremented by one for each error encountered.
 162         ErrorCount int
 163
 164         // The Mode field controls which tokens are recognized. For instance,
 165         // to recognize Ints, set the ScanInts bit in Mode. The field may be
 166         // changed at any time.
 167         Mode uint
 168
 169         // The Whitespace field controls which characters are recognized
 170         // as white space. To recognize a character ch <= ' ' as white space,
 171         // set the ch'th bit in Whitespace (the Scanner's behavior is undefined
 172         // for values ch > ' '). The field may be changed at any time.
 173         Whitespace uint64
 174
 175         // Current token position. The Offset, Line, and Column fields
 176         // are set by Scan(); the Filename field is left untouched by the
 177         // Scanner.
 178         Position
 179 }
 180
 181
 182 // Init initializes a Scanner with a new source and returns s.
 183 // Error is set to nil, ErrorCount is set to 0, Mode is set to GoTokens,
 184 // and Whitespace is set to GoWhitespace.
 185 func (s *Scanner) Init(src io.Reader) *Scanner {
 186         s.src = src
 187
 188         // initialize source buffer
 189         // (the first call to next() will fill it by calling src.Read)
 190         s.srcBuf[0] = utf8.RuneSelf // sentinel
 191         s.srcPos = 0
 192         s.srcEnd = 0
 193
 194         // initialize source position
 195         s.srcBufOffset = 0
 196         s.line = 1
 197         s.column = 0
 198         s.lastLineLen = 0
 199         s.lastCharLen = 0
 200
 201         // initialize token text buffer
 202         // (required for first call to next()).
 203         s.tokPos = -1
 204
 205         // initialize one character look-ahead
 206         s.ch = -1 // no char read yet
 207
 208         // initialize public fields
 209         s.Error = nil
 210         s.ErrorCount = 0
 211         s.Mode = GoTokens
 212         s.Whitespace = GoWhitespace
 213
 214         return s
 215 }
 216
 217
 218 // TODO(gri): The code for next() and the internal scanner state could benefit
 219 //            from a rethink. While next() is optimized for the common ASCII
 220 //            case, the "corrections" needed for proper position tracking undo
 221 //            some of the attempts for fast-path optimization.
 222
 223 // next reads and returns the next Unicode character. It is designed such
 224 // that only a minimal amount of work needs to be done in the common ASCII
 225 // case (one test to check for both ASCII and end-of-buffer, and one test
 226 // to check for newlines).
 227 func (s *Scanner) next() int {
 228         ch, width := int(s.srcBuf[s.srcPos]), 1
 229
 230         if ch >= utf8.RuneSelf {
 231                 // uncommon case: not ASCII or not enough bytes
 232                 for s.srcPos+utf8.UTFMax > s.srcEnd && !utf8.FullRune(s.srcBuf[s.srcPos:s.srcEnd]) {
 233                         // not enough bytes: read some more, but first
 234                         // save away token text if any
 235                         if s.tokPos >= 0 {
 236                                 s.tokBuf.Write(s.srcBuf[s.tokPos:s.srcPos])
 237                                 s.tokPos = 0
 238                                 // s.tokEnd is set by Scan()
 239                         }
 240                         // move unread bytes to beginning of buffer
 241                         copy(s.srcBuf[0:], s.srcBuf[s.srcPos:s.srcEnd])
 242                         s.srcBufOffset += s.srcPos
 243                         // read more bytes
 244                         // (an io.Reader must return os.EOF when it reaches
 245                         // the end of what it is reading - simply returning
 246                         // n == 0 will make this loop retry forever; but the
 247                         // error is in the reader implementation in that case)
 248                         i := s.srcEnd - s.srcPos
 249                         n, err := s.src.Read(s.srcBuf[i:bufLen])
 250                         s.srcPos = 0
 251                         s.srcEnd = i + n
 252                         s.srcBuf[s.srcEnd] = utf8.RuneSelf // sentinel
 253                         if err != nil {
 254                                 if s.srcEnd == 0 {
 255                                         if s.lastCharLen > 0 {
 256                                                 // previous character was not EOF
 257                                                 s.column++
 258                                         }
 259                                         s.lastCharLen = 0
 260                                         return EOF
 261                                 }
 262                                 if err != os.EOF {
 263                                         s.error(err.String())
 264                                 }
 265                                 // If err == EOF, we won't be getting more
 266                                 // bytes; break to avoid infinite loop. If
 267                                 // err is something else, we don't know if
 268                                 // we can get more bytes; thus also break.
 269                                 break
 270                         }
 271                 }
 272                 // at least one byte
 273                 ch = int(s.srcBuf[s.srcPos])
 274                 if ch >= utf8.RuneSelf {
 275                         // uncommon case: not ASCII
 276                         ch, width = utf8.DecodeRune(s.srcBuf[s.srcPos:s.srcEnd])
 277                         if ch == utf8.RuneError && width == 1 {
 278                                 s.error("illegal UTF-8 encoding")
 279                         }
 280                 }
 281         }
 282
 283         // advance
 284         s.srcPos += width
 285         s.lastCharLen = width
 286         s.column++
 287
 288         // special situations
 289         switch ch {
 290         case 0:
 291                 // implementation restriction for compatibility with other tools
 292                 s.error("illegal character NUL")
 293         case '\n':
 294                 s.line++
 295                 s.lastLineLen = s.column
 296                 s.column = 0
 297         }
 298
 299         return ch
 300 }
 301
 302
 303 // Next reads and returns the next Unicode character.
 304 // It returns EOF at the end of the source. It reports
 305 // a read error by calling s.Error, if not nil; otherwise
 306 // it prints an error message to os.Stderr. Next does not
 307 // update the Scanner's Position field; use Pos() to
 308 // get the current position.
 309 func (s *Scanner) Next() int {
 310         s.tokPos = -1 // don't collect token text
 311         ch := s.Peek()
 312         s.ch = s.next()
 313         return ch
 314 }
 315
 316
 317 // Peek returns the next Unicode character in the source without advancing
 318 // the scanner. It returns EOF if the scanner's position is at the last
 319 // character of the source.
 320 func (s *Scanner) Peek() int {
 321         if s.ch < 0 {
 322                 s.ch = s.next()
 323         }
 324         return s.ch
 325 }
 326
 327
 328 func (s *Scanner) error(msg string) {
 329         s.ErrorCount++
 330         if s.Error != nil {
 331                 s.Error(s, msg)
 332                 return
 333         }
 334         fmt.Fprintf(os.Stderr, "%s: %s", s.Position, msg)
 335 }
 336
 337
 338 func (s *Scanner) scanIdentifier() int {
 339         ch := s.next() // read character after first '_' or letter
 340         for ch == '_' || unicode.IsLetter(ch) || unicode.IsDigit(ch) {
 341                 ch = s.next()
 342         }
 343         return ch
 344 }
 345
 346
 347 func digitVal(ch int) int {
 348         switch {
 349         case '0' <= ch && ch <= '9':
 350                 return ch - '0'
 351         case 'a' <= ch && ch <= 'f':
 352                 return ch - 'a' + 10
 353         case 'A' <= ch && ch <= 'F':
 354                 return ch - 'A' + 10
 355         }
 356         return 16 // larger than any legal digit val
 357 }
 358
 359
 360 func isDecimal(ch int) bool { return '0' <= ch && ch <= '9' }
 361
 362
 363 func (s *Scanner) scanMantissa(ch int) int {
 364         for isDecimal(ch) {
 365                 ch = s.next()
 366         }
 367         return ch
 368 }
 369
 370
 371 func (s *Scanner) scanFraction(ch int) int {
 372         if ch == '.' {
 373                 ch = s.scanMantissa(s.next())
 374         }
 375         return ch
 376 }
 377
 378
 379 func (s *Scanner) scanExponent(ch int) int {
 380         if ch == 'e' || ch == 'E' {
 381                 ch = s.next()
 382                 if ch == '-' || ch == '+' {
 383                         ch = s.next()
 384                 }
 385                 ch = s.scanMantissa(ch)
 386         }
 387         return ch
 388 }
 389
 390
 391 func (s *Scanner) scanNumber(ch int) (int, int) {
 392         // isDecimal(ch)
 393         if ch == '0' {
 394                 // int or float
 395                 ch = s.next()
 396                 if ch == 'x' || ch == 'X' {
 397                         // hexadecimal int
 398                         ch = s.next()
 399                         for digitVal(ch) < 16 {
 400                                 ch = s.next()
 401                         }
 402                 } else {
 403                         // octal int or float
 404                         seenDecimalDigit := false
 405                         for isDecimal(ch) {
 406                                 if ch > '7' {
 407                                         seenDecimalDigit = true
 408                                 }
 409                                 ch = s.next()
 410                         }
 411                         if s.Mode&ScanFloats != 0 && (ch == '.' || ch == 'e' || ch == 'E') {
 412                                 // float
 413                                 ch = s.scanFraction(ch)
 414                                 ch = s.scanExponent(ch)
 415                                 return Float, ch
 416                         }
 417                         // octal int
 418                         if seenDecimalDigit {
 419                                 s.error("illegal octal number")
 420                         }
 421                 }
 422                 return Int, ch
 423         }
 424         // decimal int or float
 425         ch = s.scanMantissa(ch)
 426         if s.Mode&ScanFloats != 0 && (ch == '.' || ch == 'e' || ch == 'E') {
 427                 // float
 428                 ch = s.scanFraction(ch)
 429                 ch = s.scanExponent(ch)
 430                 return Float, ch
 431         }
 432         return Int, ch
 433 }
 434
 435
 436 func (s *Scanner) scanDigits(ch, base, n int) int {
 437         for n > 0 && digitVal(ch) < base {
 438                 ch = s.next()
 439                 n--
 440         }
 441         if n > 0 {
 442                 s.error("illegal char escape")
 443         }
 444         return ch
 445 }
 446
 447
 448 func (s *Scanner) scanEscape(quote int) int {
 449         ch := s.next() // read character after '/'
 450         switch ch {
 451         case 'a', 'b', 'f', 'n', 'r', 't', 'v', '\\', quote:
 452                 // nothing to do
 453                 ch = s.next()
 454         case '0', '1', '2', '3', '4', '5', '6', '7':
 455                 ch = s.scanDigits(ch, 8, 3)
 456         case 'x':
 457                 ch = s.scanDigits(s.next(), 16, 2)
 458         case 'u':
 459                 ch = s.scanDigits(s.next(), 16, 4)
 460         case 'U':
 461                 ch = s.scanDigits(s.next(), 16, 8)
 462         default:
 463                 s.error("illegal char escape")
 464         }
 465         return ch
 466 }
 467
 468
 469 func (s *Scanner) scanString(quote int) (n int) {
 470         ch := s.next() // read character after quote
 471         for ch != quote {
 472                 if ch == '\n' || ch < 0 {
 473                         s.error("literal not terminated")
 474                         return
 475                 }
 476                 if ch == '\\' {
 477                         ch = s.scanEscape(quote)
 478                 } else {
 479                         ch = s.next()
 480                 }
 481                 n++
 482         }
 483         return
 484 }
 485
 486
 487 func (s *Scanner) scanRawString() {
 488         ch := s.next() // read character after '`'
 489         for ch != '`' {
 490                 if ch < 0 {
 491                         s.error("literal not terminated")
 492                         return
 493                 }
 494                 ch = s.next()
 495         }
 496 }
 497
 498
 499 func (s *Scanner) scanChar() {
 500         if s.scanString('\'') != 1 {
 501                 s.error("illegal char literal")
 502         }
 503 }
 504
 505
 506 func (s *Scanner) scanLineComment() {
 507         ch := s.next() // read character after "//"
 508         for ch != '\n' {
 509                 if ch < 0 {
 510                         s.error("comment not terminated")
 511                         return
 512                 }
 513                 ch = s.next()
 514         }
 515 }
 516
 517
 518 func (s *Scanner) scanGeneralComment() {
 519         ch := s.next() // read character after "/*"
 520         for {
 521                 if ch < 0 {
 522                         s.error("comment not terminated")
 523                         return
 524                 }
 525                 ch0 := ch
 526                 ch = s.next()
 527                 if ch0 == '*' && ch == '/' {
 528                         break
 529                 }
 530         }
 531 }
 532
 533
 534 func (s *Scanner) scanComment(ch int) {
 535         // ch == '/' || ch == '*'
 536         if ch == '/' {
 537                 s.scanLineComment()
 538                 return
 539         }
 540         s.scanGeneralComment()
 541 }
 542
 543
 544 // Scan reads the next token or Unicode character from source and returns it.
 545 // It only recognizes tokens t for which the respective Mode bit (1<<-t) is set.
 546 // It returns EOF at the end of the source. It reports scanner errors (read and
 547 // token errors) by calling s.Error, if not nil; otherwise it prints an error
 548 // message to os.Stderr.
 549 func (s *Scanner) Scan() int {
 550         ch := s.Peek()
 551
 552         // reset token text position
 553         s.tokPos = -1
 554
 555 redo:
 556         // skip white space
 557         for s.Whitespace&(1<<uint(ch)) != 0 {
 558                 ch = s.next()
 559         }
 560
 561         // start collecting token text
 562         s.tokBuf.Reset()
 563         s.tokPos = s.srcPos - s.lastCharLen
 564
 565         // set token position
 566         // (this is a slightly optimized version of the code in Pos())
 567         s.Offset = s.srcBufOffset + s.tokPos
 568         if s.column > 0 {
 569                 // common case: last character was not a '\n'
 570                 s.Line = s.line
 571                 s.Column = s.column
 572         } else {
 573                 // last character was a '\n'
 574                 // (we cannot be at the beginning of the source
 575                 // since we have called next() at least once)
 576                 s.Line = s.line - 1
 577                 s.Column = s.lastLineLen
 578         }
 579
 580         // determine token value
 581         tok := ch
 582         switch {
 583         case unicode.IsLetter(ch) || ch == '_':
 584                 if s.Mode&ScanIdents != 0 {
 585                         tok = Ident
 586                         ch = s.scanIdentifier()
 587                 } else {
 588                         ch = s.next()
 589                 }
 590         case isDecimal(ch):
 591                 if s.Mode&(ScanInts|ScanFloats) != 0 {
 592                         tok, ch = s.scanNumber(ch)
 593                 } else {
 594                         ch = s.next()
 595                 }
 596         default:
 597                 switch ch {
 598                 case '"':
 599                         if s.Mode&ScanStrings != 0 {
 600                                 s.scanString('"')
 601                                 tok = String
 602                         }
 603                         ch = s.next()
 604                 case '\'':
 605                         if s.Mode&ScanChars != 0 {
 606                                 s.scanChar()
 607                                 tok = Char
 608                         }
 609                         ch = s.next()
 610                 case '.':
 611                         ch = s.next()
 612                         if isDecimal(ch) && s.Mode&ScanFloats != 0 {
 613                                 tok = Float
 614                                 ch = s.scanMantissa(ch)
 615                                 ch = s.scanExponent(ch)
 616                         }
 617                 case '/':
 618                         ch = s.next()
 619                         if (ch == '/' || ch == '*') && s.Mode&ScanComments != 0 {
 620                                 if s.Mode&SkipComments != 0 {
 621                                         s.tokPos = -1 // don't collect token text
 622                                         s.scanComment(ch)
 623                                         ch = s.next()
 624                                         goto redo
 625                                 }
 626                                 s.scanComment(ch)
 627                                 tok = Comment
 628                                 ch = s.next()
 629                         }
 630                 case '`':
 631                         if s.Mode&ScanRawStrings != 0 {
 632                                 s.scanRawString()
 633                                 tok = String
 634                         }
 635                         ch = s.next()
 636                 default:
 637                         ch = s.next()
 638                 }
 639         }
 640
 641         // end of token text
 642         s.tokEnd = s.srcPos - s.lastCharLen
 643
 644         s.ch = ch
 645         return tok
 646 }
 647
 648
 649 // Pos returns the position of the character immediately after
 650 // the character or token returned by the last call to Next or Scan.
 651 func (s *Scanner) Pos() (pos Position) {
 652         pos.Filename = s.Filename
 653         pos.Offset = s.srcBufOffset + s.srcPos - s.lastCharLen
 654         switch {
 655         case s.column > 0:
 656                 // common case: last character was not a '\n'
 657                 pos.Line = s.line
 658                 pos.Column = s.column
 659         case s.lastLineLen > 0:
 660                 // last character was a '\n'
 661                 pos.Line = s.line - 1
 662                 pos.Column = s.lastLineLen
 663         default:
 664                 // at the beginning of the source
 665                 pos.Line = 1
 666                 pos.Column = 1
 667         }
 668         return
 669 }
 670
 671
 672 // TokenText returns the string corresponding to the most recently scanned token.
 673 // Valid after calling Scan().
 674 func (s *Scanner) TokenText() string {
 675         if s.tokPos < 0 {
 676                 // no token text
 677                 return ""
 678         }
 679
 680         if s.tokEnd < 0 {
 681                 // if EOF was reached, s.tokEnd is set to -1 (s.srcPos == 0)
 682                 s.tokEnd = s.tokPos
 683         }
 684
 685         if s.tokBuf.Len() == 0 {
 686                 // common case: the entire token text is still in srcBuf
 687                 return string(s.srcBuf[s.tokPos:s.tokEnd])
 688         }
 689
 690         // part of the token text was saved in tokBuf: save the rest in
 691         // tokBuf as well and return its content
 692         s.tokBuf.Write(s.srcBuf[s.tokPos:s.tokEnd])
 693         s.tokPos = s.tokEnd // ensure idempotency of TokenText() call
 694         return s.tokBuf.String()
 695 }