scanner.go raw
1 // Copyright 2016 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 // This file implements scanner, a lexical tokenizer for
6 // Go source. After initialization, consecutive calls of
7 // next advance the scanner one token at a time.
8 //
9 // This file, source.go, tokens.go, and token_string.go are self-contained
10 // (`go tool compile scanner.go source.go tokens.go token_string.go` compiles)
11 // and thus could be made into their own package.
12
13 package syntax
14
15 import (
16 "fmt"
17 "io"
18 "unicode"
19 "unicode/utf8"
20 )
21
22 // The mode flags below control which comments are reported
23 // by calling the error handler. If no flag is set, comments
24 // are ignored.
25 const (
26 comments uint = 1 << iota // call handler for all comments
27 directives // call handler for directives only
28 )
29
30 type Scanner struct {
31 Source
32 mode uint
33 nlsemi bool // if set '\n' and EOF translate to ';'
34
35 // current token, valid after calling next()
36 Line, Col uint32
37 Blank bool // line is blank up to col
38 Tok Token
39 Lit string // valid if tok is _Name, _Literal, or _Semi ("semicolon", "newline", or "EOF"); may be malformed if bad is true
40 Bad bool // valid if tok is _Literal, true if a syntax error occurred, lit may be malformed
41 Kind LitKind // valid if tok is _Literal
42 Op Operator // valid if tok is _Operator, _Star, _AssignOp, or _IncOp
43 Prec int32 // valid if tok is _Operator, _Star, _AssignOp, or _IncOp
44 }
45
46 func (s *Scanner) Init(src io.Reader, errh func(line, col uint32, msg string), mode uint) {
47 s.Source.init(src, errh)
48 s.mode = mode
49 s.nlsemi = false
50 }
51
52 // errorf reports an error at the most recently read character position.
53 func (s *Scanner) Errorf(format string, args ...interface{}) {
54 s.error(fmt.Sprintf(format, args...))
55 }
56
57 // errorAtf reports an error at a byte column offset relative to the current token start.
58 func (s *Scanner) ErrorAtf(offset int32, format string, args ...interface{}) {
59 s.errh(s.line, s.col+uint32(offset), fmt.Sprintf(format, args...))
60 }
61
62 // setLit sets the scanner state for a recognized _Literal token.
63 func (s *Scanner) SetLit(kind LitKind, ok bool) {
64 s.nlsemi = true
65 s.Tok = Literal
66 s.Lit = string(s.segment())
67 s.Bad = !ok
68 s.Kind = kind
69 }
70
71 // next advances the scanner by reading the next token.
72 //
73 // If a read, source encoding, or lexical error occurs, next calls
74 // the installed error handler with the respective error position
75 // and message. The error message is guaranteed to be non-empty and
76 // never starts with a '/'. The error handler must exist.
77 //
78 // If the scanner mode includes the comments flag and a comment
79 // (including comments containing directives) is encountered, the
80 // error handler is also called with each comment position and text
81 // (including opening /* or // and closing */, but without a newline
82 // at the end of line comments). Comment text always starts with a /
83 // which can be used to distinguish these handler calls from errors.
84 //
85 // If the scanner mode includes the directives (but not the comments)
86 // flag, only comments containing a //line, /*line, or //go: directive
87 // are reported, in the same way as regular comments.
88 func (s *Scanner) Next() {
89 nlsemi := s.nlsemi
90 s.nlsemi = false
91
92 redo:
93 // skip white space
94 s.stop()
95 startLine, startCol := s.pos()
96 for s.ch == ' ' || s.ch == '\t' || s.ch == '\n' && !nlsemi || s.ch == '\r' {
97 s.nextch()
98 }
99
100 // token start
101 s.Line, s.Col = s.pos()
102 s.Blank = s.line > startLine || startCol == Colbase
103 s.start()
104 if IsLetter(s.ch) || s.ch >= utf8.RuneSelf && s.AtIdentChar(true) {
105 s.nextch()
106 s.Ident()
107 return
108 }
109
110 switch s.ch {
111 case -1:
112 if nlsemi {
113 s.Lit = "EOF"
114 s.Tok = Semi
115 break
116 }
117 s.Tok =EOF
118
119 case '\n':
120 s.nextch()
121 s.Lit = "newline"
122 s.Tok = Semi
123
124 case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
125 s.Number(false)
126
127 case '"':
128 s.stdString()
129
130 case '`':
131 s.rawString()
132
133 case '\'':
134 s.rune()
135
136 case '(':
137 s.nextch()
138 s.Tok = Lparen
139
140 case '[':
141 s.nextch()
142 s.Tok = Lbrack
143
144 case '{':
145 s.nextch()
146 s.Tok = Lbrace
147
148 case ',':
149 s.nextch()
150 s.Tok = Comma
151
152 case ';':
153 s.nextch()
154 s.Lit = "semicolon"
155 s.Tok = Semi
156
157 case ')':
158 s.nextch()
159 s.nlsemi = true
160 s.Tok = Rparen
161
162 case ']':
163 s.nextch()
164 s.nlsemi = true
165 s.Tok = Rbrack
166
167 case '}':
168 s.nextch()
169 s.nlsemi = true
170 s.Tok = Rbrace
171
172 case ':':
173 s.nextch()
174 if s.ch == '=' {
175 s.nextch()
176 s.Tok = Define
177 break
178 }
179 s.Tok = Colon
180
181 case '.':
182 s.nextch()
183 if IsDecimal(s.ch) {
184 s.Number(true)
185 break
186 }
187 if s.ch == '.' {
188 s.nextch()
189 if s.ch == '.' {
190 s.nextch()
191 s.Tok = DotDotDot
192 break
193 }
194 s.rewind() // now s.ch holds 1st '.'
195 s.nextch() // consume 1st '.' again
196 }
197 s.Tok = Dot
198
199 case '+':
200 s.nextch()
201 s.Op, s.Prec = Add, PrecAdd
202 if s.ch != '+' {
203 goto assignop
204 }
205 s.nextch()
206 s.nlsemi = true
207 s.Tok = IncOp
208
209 case '-':
210 s.nextch()
211 s.Op, s.Prec = Sub, PrecAdd
212 if s.ch != '-' {
213 goto assignop
214 }
215 s.nextch()
216 s.nlsemi = true
217 s.Tok = IncOp
218
219 case '*':
220 s.nextch()
221 s.Op, s.Prec = Mul, PrecMul
222 // don't goto assignop - want _Star token
223 if s.ch == '=' {
224 s.nextch()
225 s.Tok = AssignOp
226 break
227 }
228 s.Tok = Star
229
230 case '/':
231 s.nextch()
232 if s.ch == '/' {
233 s.nextch()
234 s.lineComment()
235 goto redo
236 }
237 if s.ch == '*' {
238 s.nextch()
239 s.fullComment()
240 if line, _ := s.pos(); line > s.Line && nlsemi {
241 // A multi-line comment acts like a newline;
242 // it translates to a ';' if nlsemi is set.
243 s.Lit = "newline"
244 s.Tok = Semi
245 break
246 }
247 goto redo
248 }
249 s.Op, s.Prec = Div, PrecMul
250 goto assignop
251
252 case '%':
253 s.nextch()
254 s.Op, s.Prec = Rem, PrecMul
255 goto assignop
256
257 case '&':
258 s.nextch()
259 if s.ch == '&' {
260 s.nextch()
261 s.Op, s.Prec = AndAnd, PrecAndAnd
262 s.Tok = OperatorType
263 break
264 }
265 s.Op, s.Prec = And, PrecMul
266 if s.ch == '^' {
267 s.nextch()
268 s.Op = AndNot
269 }
270 goto assignop
271
272 case '|':
273 s.nextch()
274 if s.ch == '|' {
275 s.nextch()
276 s.Op, s.Prec = OrOr, PrecOrOr
277 s.Tok = OperatorType
278 break
279 }
280 s.Op, s.Prec = Or, PrecAdd
281 goto assignop
282
283 case '^':
284 s.nextch()
285 s.Op, s.Prec = Xor, PrecAdd
286 goto assignop
287
288 case '<':
289 s.nextch()
290 if s.ch == '=' {
291 s.nextch()
292 s.Op, s.Prec = Leq, PrecCmp
293 s.Tok = OperatorType
294 break
295 }
296 if s.ch == '<' {
297 s.nextch()
298 s.Op, s.Prec = Shl, PrecMul
299 goto assignop
300 }
301 if s.ch == '-' {
302 s.nextch()
303 s.Tok = Arrow
304 break
305 }
306 s.Op, s.Prec = Lss, PrecCmp
307 s.Tok = OperatorType
308
309 case '>':
310 s.nextch()
311 if s.ch == '=' {
312 s.nextch()
313 s.Op, s.Prec = Geq, PrecCmp
314 s.Tok =OperatorType
315 break
316 }
317 if s.ch == '>' {
318 s.nextch()
319 s.Op, s.Prec = Shr, PrecMul
320 goto assignop
321 }
322 s.Op, s.Prec = Gtr, PrecCmp
323 s.Tok = OperatorType
324
325 case '=':
326 s.nextch()
327 if s.ch == '=' {
328 s.nextch()
329 s.Op, s.Prec = Eql, PrecCmp
330 s.Tok = OperatorType
331 break
332 }
333 s.Tok = Assign
334
335 case '!':
336 s.nextch()
337 if s.ch == '=' {
338 s.nextch()
339 s.Op, s.Prec = Neq, PrecCmp
340 s.Tok = OperatorType
341 break
342 }
343 s.Op, s.Prec = Not, 0
344 s.Tok = OperatorType
345
346 case '~':
347 s.nextch()
348 s.Op, s.Prec = Tilde, 0
349 s.Tok = OperatorType
350
351 case '#':
352 // Moxie: # export prefix for non-Latin identifiers.
353 // #foo is the same identifier as foo, but marks it as stable API.
354 s.nextch()
355 if IsLetter(s.ch) || s.ch >= utf8.RuneSelf && s.AtIdentChar(true) {
356 s.nextch()
357 s.Ident()
358 // Prefix the scanned identifier with #.
359 s.Lit = "#" + s.Lit
360 return
361 }
362 s.Errorf("# must be followed by an identifier")
363 goto redo
364
365 default:
366 s.Errorf("invalid character %#U", s.ch)
367 s.nextch()
368 goto redo
369 }
370
371 return
372
373 assignop:
374 if s.ch == '=' {
375 s.nextch()
376 s.Tok = AssignOp
377 return
378 }
379 s.Tok = OperatorType
380 }
381
382 func (s *Scanner) Ident() {
383 // accelerate common case (7bit ASCII)
384 for IsLetter(s.ch) || IsDecimal(s.ch) {
385 s.nextch()
386 }
387
388 // general case
389 if s.ch >= utf8.RuneSelf {
390 for s.AtIdentChar(false) {
391 s.nextch()
392 }
393 }
394
395 // possibly a keyword
396 lit := s.segment()
397 if len(lit) >= 2 {
398 if tok := keywordMap[Hash(lit)]; tok != 0 && TokStrFast(tok) == string(lit) {
399 s.nlsemi = contains(1<<Break|1<<Continue|1<<Fallthrough|1<<Return, tok)
400 s.Tok = tok
401 return
402 }
403 }
404
405 s.nlsemi = true
406 s.Lit = string(lit)
407 s.Tok = NameType
408 }
409
410 // tokStrFast is a faster version of token.String, which assumes that tok
411 // is one of the valid tokens - and can thus skip bounds checks.
412 func TokStrFast(tok Token) string {
413 return token_name[token_index[tok-1]:token_index[tok]]
414 }
415
416 func (s *Scanner) AtIdentChar(first bool) bool {
417 switch {
418 case unicode.IsLetter(s.ch) || s.ch == '_':
419 // ok
420 case unicode.IsDigit(s.ch):
421 if first {
422 s.Errorf("identifier cannot begin with digit %#U", s.ch)
423 }
424 case s.ch >= utf8.RuneSelf:
425 s.Errorf("invalid character %#U in identifier", s.ch)
426 default:
427 return false
428 }
429 return true
430 }
431
432 // hash is a perfect hash function for keywords.
433 // It assumes that s has at least length 2.
434 func Hash(s []byte) uint {
435 return (uint(s[0])<<4 ^ uint(s[1]) + uint(len(s))) & uint(len(keywordMap)-1)
436 }
437
438 var keywordMap [1 << 6]Token // size must be power of two
439
440 func init() { Init() }
441
442 func Init() {
443 // populate keywordMap
444 for tok := Break; tok <= Var; tok++ {
445 h := Hash([]byte(tok.String()))
446 if keywordMap[h] != 0 {
447 panic("imperfect hash")
448 }
449 keywordMap[h] = tok
450 }
451 }
452
453 func Lower(ch rune) rune { return ('a' - 'A') | ch } // returns lower-case ch iff ch is ASCII letter
454 func IsLetter(ch rune) bool { return 'a' <= Lower(ch) && Lower(ch) <= 'z' || ch == '_' }
455 func IsDecimal(ch rune) bool { return '0' <= ch && ch <= '9' }
456 func IsHex(ch rune) bool { return '0' <= ch && ch <= '9' || 'a' <= Lower(ch) && Lower(ch) <= 'f' }
457
458 // Digits accepts the sequence { digit | '_' }.
459 // If base <= 10, Digits accepts any decimal digit but records
460 // the index (relative to the literal start) of a digit >= base
461 // in *invalid, if *invalid < 0.
462 // Digits returns a bitset describing whether the sequence contained
463 // Digits (bit 0 is set), or separators '_' (bit 1 is set).
464 func (s *Scanner) Digits(base int32, invalid *int32) (digsep int32) {
465 if base <= 10 {
466 max := rune('0' + base)
467 for IsDecimal(s.ch) || s.ch == '_' {
468 ds := int32(1)
469 if s.ch == '_' {
470 ds = 2
471 } else if s.ch >= max && *invalid < 0 {
472 _, col := s.pos()
473 *invalid = int32(col - s.col)
474 }
475 digsep |= ds
476 s.nextch()
477 }
478 } else {
479 for IsHex(s.ch) || s.ch == '_' {
480 ds := int32(1)
481 if s.ch == '_' {
482 ds = 2
483 }
484 digsep |= ds
485 s.nextch()
486 }
487 }
488 return
489 }
490
491 func (s *Scanner) Number(seenPoint bool) {
492 ok := true
493 kind := IntLit
494 base := int32(10) // number base
495 prefix := rune(0) // one of 0 (decimal), '0' (0-octal), 'x', 'o', or 'b'
496 digsep := int32(0) // bit 0: digit present, bit 1: '_' present
497 invalid := int32(-1) // index of invalid digit in literal, or < 0
498
499 // integer part
500 if !seenPoint {
501 if s.ch == '0' {
502 s.nextch()
503 switch Lower(s.ch) {
504 case 'x':
505 s.nextch()
506 base, prefix = 16, 'x'
507 case 'o':
508 s.nextch()
509 base, prefix = 8, 'o'
510 case 'b':
511 s.nextch()
512 base, prefix = 2, 'b'
513 default:
514 base, prefix = 8, '0'
515 digsep = 1 // leading 0
516 }
517 }
518 digsep |= s.Digits(base, &invalid)
519 if s.ch == '.' {
520 if prefix == 'o' || prefix == 'b' {
521 s.Errorf("invalid radix point in %s literal", baseName(base))
522 ok = false
523 }
524 s.nextch()
525 seenPoint = true
526 }
527 }
528
529 // fractional part
530 if seenPoint {
531 kind = FloatLit
532 digsep |= s.Digits(base, &invalid)
533 }
534
535 if digsep&1 == 0 && ok {
536 s.Errorf("%s literal has no digits", baseName(base))
537 ok = false
538 }
539
540 // exponent
541 if e := Lower(s.ch); e == 'e' || e == 'p' {
542 if ok {
543 switch {
544 case e == 'e' && prefix != 0 && prefix != '0':
545 s.Errorf("%q exponent requires decimal mantissa", s.ch)
546 ok = false
547 case e == 'p' && prefix != 'x':
548 s.Errorf("%q exponent requires hexadecimal mantissa", s.ch)
549 ok = false
550 }
551 }
552 s.nextch()
553 kind = FloatLit
554 if s.ch == '+' || s.ch == '-' {
555 s.nextch()
556 }
557 digsep = s.Digits(10, nil) | digsep&2 // don't lose sep bit
558 if digsep&1 == 0 && ok {
559 s.Errorf("exponent has no digits")
560 ok = false
561 }
562 } else if prefix == 'x' && kind == FloatLit && ok {
563 s.Errorf("hexadecimal mantissa requires a 'p' exponent")
564 ok = false
565 }
566
567 // suffix 'i'
568 if s.ch == 'i' {
569 kind = ImagLit
570 s.nextch()
571 }
572
573 s.SetLit(kind, ok) // do this now so we can use s.lit below
574
575 if kind == IntLit && invalid >= 0 && ok {
576 s.ErrorAtf(invalid, "invalid digit %q in %s literal", s.Lit[invalid], baseName(base))
577 ok = false
578 }
579
580 if digsep&2 != 0 && ok {
581 if i := invalidSep(s.Lit); i >= 0 {
582 s.ErrorAtf(i, "'_' must separate successive digits")
583 ok = false
584 }
585 }
586
587 s.Bad = !ok // correct s.bad
588 }
589
590 func baseName(base int32) string {
591 switch base {
592 case 2:
593 return "binary"
594 case 8:
595 return "octal"
596 case 10:
597 return "decimal"
598 case 16:
599 return "hexadecimal"
600 }
601 panic("invalid base")
602 }
603
604 // invalidSep returns the index of the first invalid separator in x, or -1.
605 func invalidSep(x string) int32 {
606 x1 := ' ' // prefix char, we only care if it's 'x'
607 d := '.' // digit, one of '_', '0' (a digit), or '.' (anything else)
608 i := int32(0)
609
610 // a prefix counts as a digit
611 if len(x) >= 2 && x[0] == '0' {
612 x1 = Lower(rune(x[1]))
613 if x1 == 'x' || x1 == 'o' || x1 == 'b' {
614 d = '0'
615 i = 2
616 }
617 }
618
619 // mantissa and exponent
620 for ; i < int32(len(x)); i++ {
621 p := d // previous digit
622 d = rune(x[i])
623 switch {
624 case d == '_':
625 if p != '0' {
626 return i
627 }
628 case IsDecimal(d) || x1 == 'x' && IsHex(d):
629 d = '0'
630 default:
631 if p == '_' {
632 return i - 1
633 }
634 d = '.'
635 }
636 }
637 if d == '_' {
638 return int32(len(x)) - 1
639 }
640
641 return -1
642 }
643
644 func (s *Scanner) rune() {
645 ok := true
646 s.nextch()
647
648 n := 0
649 for ; ; n++ {
650 if s.ch == '\'' {
651 if ok {
652 if n == 0 {
653 s.Errorf("empty rune literal or unescaped '")
654 ok = false
655 } else if n != 1 {
656 s.ErrorAtf(0, "more than one character in rune literal")
657 ok = false
658 }
659 }
660 s.nextch()
661 break
662 }
663 if s.ch == '\\' {
664 s.nextch()
665 if !s.escape('\'') {
666 ok = false
667 }
668 continue
669 }
670 if s.ch == '\n' {
671 if ok {
672 s.Errorf("newline in rune literal")
673 ok = false
674 }
675 break
676 }
677 if s.ch < 0 {
678 if ok {
679 s.ErrorAtf(0, "rune literal not terminated")
680 ok = false
681 }
682 break
683 }
684 s.nextch()
685 }
686
687 s.SetLit(RuneLit, ok)
688 }
689
690 func (s *Scanner) stdString() {
691 ok := true
692 s.nextch()
693
694 for {
695 if s.ch == '"' {
696 s.nextch()
697 break
698 }
699 if s.ch == '\\' {
700 s.nextch()
701 if !s.escape('"') {
702 ok = false
703 }
704 continue
705 }
706 if s.ch == '\n' {
707 s.Errorf("newline in string")
708 ok = false
709 break
710 }
711 if s.ch < 0 {
712 s.ErrorAtf(0, "string not terminated")
713 ok = false
714 break
715 }
716 s.nextch()
717 }
718
719 s.SetLit(StringLit, ok)
720 }
721
722 func (s *Scanner) rawString() {
723 ok := true
724 s.nextch()
725
726 for {
727 if s.ch == '`' {
728 s.nextch()
729 break
730 }
731 if s.ch < 0 {
732 s.ErrorAtf(0, "string not terminated")
733 ok = false
734 break
735 }
736 s.nextch()
737 }
738 // We leave CRs in the string since they are part of the
739 // literal (even though they are not part of the literal
740 // value).
741
742 s.SetLit(StringLit, ok)
743 }
744
745 func (s *Scanner) comment(text string) {
746 s.ErrorAtf(0, "%s", text)
747 }
748
749 func (s *Scanner) skipLine() {
750 // don't consume '\n' - needed for nlsemi logic
751 for s.ch >= 0 && s.ch != '\n' {
752 s.nextch()
753 }
754 }
755
756 func (s *Scanner) lineComment() {
757 // opening has already been consumed
758
759 if s.mode&comments != 0 {
760 s.skipLine()
761 s.comment(string(s.segment()))
762 return
763 }
764
765 // are we saving directives? or is this definitely not a directive?
766 if s.mode&directives == 0 || (s.ch != 'g' && s.ch != 'l') {
767 s.stop()
768 s.skipLine()
769 return
770 }
771
772 // recognize go: or line directives
773 prefix := "go:"
774 if s.ch == 'l' {
775 prefix = "line "
776 }
777
778 for _, r := range prefix {
779 if s.ch != r { s.stop(); s.skipLine(); return }
780 s.nextch()
781 }
782 // directive text
783 s.skipLine()
784 s.comment(string(s.segment()))
785 }
786
787 func (s *Scanner) skipComment() bool {
788 for s.ch >= 0 {
789 for s.ch == '*' {
790 s.nextch()
791 if s.ch == '/' {
792 s.nextch()
793 return true
794 }
795 }
796 s.nextch()
797 }
798 s.ErrorAtf(0, "comment not terminated")
799 return false
800 }
801
802 func (s *Scanner) fullComment() {
803 /* opening has already been consumed */
804
805 if s.mode&comments != 0 {
806 if s.skipComment() {
807 s.comment(string(s.segment()))
808 }
809 return
810 }
811
812 if s.mode&directives == 0 || s.ch != 'l' {
813 s.stop()
814 s.skipComment()
815 return
816 }
817
818 // recognize line directive
819 const prefix = "line "
820
821 for _, r := range prefix {
822 if s.ch != r { s.stop(); s.skipComment(); return }
823 s.nextch()
824 }
825 // directive text
826 if s.skipComment() {
827 s.comment(string(s.segment()))
828 }
829 }
830
831 func (s *Scanner) escape(quote rune) bool {
832 var n int32
833 var base, max uint32
834
835 switch s.ch {
836 case quote, 'a', 'b', 'f', 'n', 'r', 't', 'v', '\\':
837 s.nextch()
838 return true
839 case '0', '1', '2', '3', '4', '5', '6', '7':
840 n, base, max = 3, 8, 255
841 case 'x':
842 s.nextch()
843 n, base, max = 2, 16, 255
844 case 'u':
845 s.nextch()
846 n, base, max = 4, 16, unicode.MaxRune
847 case 'U':
848 s.nextch()
849 n, base, max = 8, 16, unicode.MaxRune
850 default:
851 if s.ch < 0 {
852 return true // complain in caller about EOF
853 }
854 s.Errorf("unknown escape")
855 return false
856 }
857
858 var x uint32
859 for i := n; i > 0; i-- {
860 if s.ch < 0 {
861 return true // complain in caller about EOF
862 }
863 d := base
864 if IsDecimal(s.ch) {
865 d = uint32(s.ch) - '0'
866 } else if 'a' <= Lower(s.ch) && Lower(s.ch) <= 'f' {
867 d = uint32(Lower(s.ch)) - 'a' + 10
868 }
869 if d >= base {
870 s.Errorf("invalid character %q in %s escape", s.ch, baseName(int32(base)))
871 return false
872 }
873 // d < base
874 x = x*base + d
875 s.nextch()
876 }
877
878 if x > max && base == 8 {
879 s.Errorf("octal escape value %d > 255", x)
880 return false
881 }
882
883 if x > max || 0xD800 <= x && x < 0xE000 /* surrogate range */ {
884 s.Errorf("escape is invalid Unicode code point %#U", x)
885 return false
886 }
887
888 return true
889 }
890