...
Run Format

Source file src/bufio/scan.go

     1	// Copyright 2013 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 bufio
     6	
     7	import (
     8		"bytes"
     9		"errors"
    10		"io"
    11		"unicode/utf8"
    12	)
    13	
    14	// Scanner provides a convenient interface for reading data such as
    15	// a file of newline-delimited lines of text. Successive calls to
    16	// the Scan method will step through the 'tokens' of a file, skipping
    17	// the bytes between the tokens. The specification of a token is
    18	// defined by a split function of type SplitFunc; the default split
    19	// function breaks the input into lines with line termination stripped. Split
    20	// functions are defined in this package for scanning a file into
    21	// lines, bytes, UTF-8-encoded runes, and space-delimited words. The
    22	// client may instead provide a custom split function.
    23	//
    24	// Scanning stops unrecoverably at EOF, the first I/O error, or a token too
    25	// large to fit in the buffer. When a scan stops, the reader may have
    26	// advanced arbitrarily far past the last token. Programs that need more
    27	// control over error handling or large tokens, or must run sequential scans
    28	// on a reader, should use bufio.Reader instead.
    29	//
    30	type Scanner struct {
    31		r            io.Reader // The reader provided by the client.
    32		split        SplitFunc // The function to split the tokens.
    33		maxTokenSize int       // Maximum size of a token; modified by tests.
    34		token        []byte    // Last token returned by split.
    35		buf          []byte    // Buffer used as argument to split.
    36		start        int       // First non-processed byte in buf.
    37		end          int       // End of data in buf.
    38		err          error     // Sticky error.
    39		empties      int       // Count of successive empty tokens.
    40		scanCalled   bool      // Scan has been called; buffer is in use.
    41		done         bool      // Scan has finished.
    42	}
    43	
    44	// SplitFunc is the signature of the split function used to tokenize the
    45	// input. The arguments are an initial substring of the remaining unprocessed
    46	// data and a flag, atEOF, that reports whether the Reader has no more data
    47	// to give. The return values are the number of bytes to advance the input
    48	// and the next token to return to the user, plus an error, if any. If the
    49	// data does not yet hold a complete token, for instance if it has no newline
    50	// while scanning lines, SplitFunc can return (0, nil, nil) to signal the
    51	// Scanner to read more data into the slice and try again with a longer slice
    52	// starting at the same point in the input.
    53	//
    54	// If the returned error is non-nil, scanning stops and the error
    55	// is returned to the client.
    56	//
    57	// The function is never called with an empty data slice unless atEOF
    58	// is true. If atEOF is true, however, data may be non-empty and,
    59	// as always, holds unprocessed text.
    60	type SplitFunc func(data []byte, atEOF bool) (advance int, token []byte, err error)
    61	
    62	// Errors returned by Scanner.
    63	var (
    64		ErrTooLong         = errors.New("bufio.Scanner: token too long")
    65		ErrNegativeAdvance = errors.New("bufio.Scanner: SplitFunc returns negative advance count")
    66		ErrAdvanceTooFar   = errors.New("bufio.Scanner: SplitFunc returns advance count beyond input")
    67	)
    68	
    69	const (
    70		// MaxScanTokenSize is the maximum size used to buffer a token
    71		// unless the user provides an explicit buffer with Scan.Buffer.
    72		// The actual maximum token size may be smaller as the buffer
    73		// may need to include, for instance, a newline.
    74		MaxScanTokenSize = 64 * 1024
    75	
    76		startBufSize = 4096 // Size of initial allocation for buffer.
    77	)
    78	
    79	// NewScanner returns a new Scanner to read from r.
    80	// The split function defaults to ScanLines.
    81	func NewScanner(r io.Reader) *Scanner {
    82		return &Scanner{
    83			r:            r,
    84			split:        ScanLines,
    85			maxTokenSize: MaxScanTokenSize,
    86		}
    87	}
    88	
    89	// Err returns the first non-EOF error that was encountered by the Scanner.
    90	func (s *Scanner) Err() error {
    91		if s.err == io.EOF {
    92			return nil
    93		}
    94		return s.err
    95	}
    96	
    97	// Bytes returns the most recent token generated by a call to Scan.
    98	// The underlying array may point to data that will be overwritten
    99	// by a subsequent call to Scan. It does no allocation.
   100	func (s *Scanner) Bytes() []byte {
   101		return s.token
   102	}
   103	
   104	// Text returns the most recent token generated by a call to Scan
   105	// as a newly allocated string holding its bytes.
   106	func (s *Scanner) Text() string {
   107		return string(s.token)
   108	}
   109	
   110	// ErrFinalToken is a special sentinel error value. It is intended to be
   111	// returned by a Split function to indicate that the token being delivered
   112	// with the error is the last token and scanning should stop after this one.
   113	// After ErrFinalToken is received by Scan, scanning stops with no error.
   114	// The value is useful to stop processing early or when it is necessary to
   115	// deliver a final empty token. One could achieve the same behavior
   116	// with a custom error value but providing one here is tidier.
   117	// See the emptyFinalToken example for a use of this value.
   118	var ErrFinalToken = errors.New("final token")
   119	
   120	// Scan advances the Scanner to the next token, which will then be
   121	// available through the Bytes or Text method. It returns false when the
   122	// scan stops, either by reaching the end of the input or an error.
   123	// After Scan returns false, the Err method will return any error that
   124	// occurred during scanning, except that if it was io.EOF, Err
   125	// will return nil.
   126	// Scan panics if the split function returns 100 empty tokens without
   127	// advancing the input. This is a common error mode for scanners.
   128	func (s *Scanner) Scan() bool {
   129		if s.done {
   130			return false
   131		}
   132		s.scanCalled = true
   133		// Loop until we have a token.
   134		for {
   135			// See if we can get a token with what we already have.
   136			// If we've run out of data but have an error, give the split function
   137			// a chance to recover any remaining, possibly empty token.
   138			if s.end > s.start || s.err != nil {
   139				advance, token, err := s.split(s.buf[s.start:s.end], s.err != nil)
   140				if err != nil {
   141					if err == ErrFinalToken {
   142						s.token = token
   143						s.done = true
   144						return true
   145					}
   146					s.setErr(err)
   147					return false
   148				}
   149				if !s.advance(advance) {
   150					return false
   151				}
   152				s.token = token
   153				if token != nil {
   154					if s.err == nil || advance > 0 {
   155						s.empties = 0
   156					} else {
   157						// Returning tokens not advancing input at EOF.
   158						s.empties++
   159						if s.empties > 100 {
   160							panic("bufio.Scan: 100 empty tokens without progressing")
   161						}
   162					}
   163					return true
   164				}
   165			}
   166			// We cannot generate a token with what we are holding.
   167			// If we've already hit EOF or an I/O error, we are done.
   168			if s.err != nil {
   169				// Shut it down.
   170				s.start = 0
   171				s.end = 0
   172				return false
   173			}
   174			// Must read more data.
   175			// First, shift data to beginning of buffer if there's lots of empty space
   176			// or space is needed.
   177			if s.start > 0 && (s.end == len(s.buf) || s.start > len(s.buf)/2) {
   178				copy(s.buf, s.buf[s.start:s.end])
   179				s.end -= s.start
   180				s.start = 0
   181			}
   182			// Is the buffer full? If so, resize.
   183			if s.end == len(s.buf) {
   184				// Guarantee no overflow in the multiplication below.
   185				const maxInt = int(^uint(0) >> 1)
   186				if len(s.buf) >= s.maxTokenSize || len(s.buf) > maxInt/2 {
   187					s.setErr(ErrTooLong)
   188					return false
   189				}
   190				newSize := len(s.buf) * 2
   191				if newSize == 0 {
   192					newSize = startBufSize
   193				}
   194				if newSize > s.maxTokenSize {
   195					newSize = s.maxTokenSize
   196				}
   197				newBuf := make([]byte, newSize)
   198				copy(newBuf, s.buf[s.start:s.end])
   199				s.buf = newBuf
   200				s.end -= s.start
   201				s.start = 0
   202			}
   203			// Finally we can read some input. Make sure we don't get stuck with
   204			// a misbehaving Reader. Officially we don't need to do this, but let's
   205			// be extra careful: Scanner is for safe, simple jobs.
   206			for loop := 0; ; {
   207				n, err := s.r.Read(s.buf[s.end:len(s.buf)])
   208				s.end += n
   209				if err != nil {
   210					s.setErr(err)
   211					break
   212				}
   213				if n > 0 {
   214					s.empties = 0
   215					break
   216				}
   217				loop++
   218				if loop > maxConsecutiveEmptyReads {
   219					s.setErr(io.ErrNoProgress)
   220					break
   221				}
   222			}
   223		}
   224	}
   225	
   226	// advance consumes n bytes of the buffer. It reports whether the advance was legal.
   227	func (s *Scanner) advance(n int) bool {
   228		if n < 0 {
   229			s.setErr(ErrNegativeAdvance)
   230			return false
   231		}
   232		if n > s.end-s.start {
   233			s.setErr(ErrAdvanceTooFar)
   234			return false
   235		}
   236		s.start += n
   237		return true
   238	}
   239	
   240	// setErr records the first error encountered.
   241	func (s *Scanner) setErr(err error) {
   242		if s.err == nil || s.err == io.EOF {
   243			s.err = err
   244		}
   245	}
   246	
   247	// Buffer sets the initial buffer to use when scanning and the maximum
   248	// size of buffer that may be allocated during scanning. The maximum
   249	// token size is the larger of max and cap(buf). If max <= cap(buf),
   250	// Scan will use this buffer only and do no allocation.
   251	//
   252	// By default, Scan uses an internal buffer and sets the
   253	// maximum token size to MaxScanTokenSize.
   254	//
   255	// Buffer panics if it is called after scanning has started.
   256	func (s *Scanner) Buffer(buf []byte, max int) {
   257		if s.scanCalled {
   258			panic("Buffer called after Scan")
   259		}
   260		s.buf = buf[0:cap(buf)]
   261		s.maxTokenSize = max
   262	}
   263	
   264	// Split sets the split function for the Scanner.
   265	// The default split function is ScanLines.
   266	//
   267	// Split panics if it is called after scanning has started.
   268	func (s *Scanner) Split(split SplitFunc) {
   269		if s.scanCalled {
   270			panic("Split called after Scan")
   271		}
   272		s.split = split
   273	}
   274	
   275	// Split functions
   276	
   277	// ScanBytes is a split function for a Scanner that returns each byte as a token.
   278	func ScanBytes(data []byte, atEOF bool) (advance int, token []byte, err error) {
   279		if atEOF && len(data) == 0 {
   280			return 0, nil, nil
   281		}
   282		return 1, data[0:1], nil
   283	}
   284	
   285	var errorRune = []byte(string(utf8.RuneError))
   286	
   287	// ScanRunes is a split function for a Scanner that returns each
   288	// UTF-8-encoded rune as a token. The sequence of runes returned is
   289	// equivalent to that from a range loop over the input as a string, which
   290	// means that erroneous UTF-8 encodings translate to U+FFFD = "\xef\xbf\xbd".
   291	// Because of the Scan interface, this makes it impossible for the client to
   292	// distinguish correctly encoded replacement runes from encoding errors.
   293	func ScanRunes(data []byte, atEOF bool) (advance int, token []byte, err error) {
   294		if atEOF && len(data) == 0 {
   295			return 0, nil, nil
   296		}
   297	
   298		// Fast path 1: ASCII.
   299		if data[0] < utf8.RuneSelf {
   300			return 1, data[0:1], nil
   301		}
   302	
   303		// Fast path 2: Correct UTF-8 decode without error.
   304		_, width := utf8.DecodeRune(data)
   305		if width > 1 {
   306			// It's a valid encoding. Width cannot be one for a correctly encoded
   307			// non-ASCII rune.
   308			return width, data[0:width], nil
   309		}
   310	
   311		// We know it's an error: we have width==1 and implicitly r==utf8.RuneError.
   312		// Is the error because there wasn't a full rune to be decoded?
   313		// FullRune distinguishes correctly between erroneous and incomplete encodings.
   314		if !atEOF && !utf8.FullRune(data) {
   315			// Incomplete; get more bytes.
   316			return 0, nil, nil
   317		}
   318	
   319		// We have a real UTF-8 encoding error. Return a properly encoded error rune
   320		// but advance only one byte. This matches the behavior of a range loop over
   321		// an incorrectly encoded string.
   322		return 1, errorRune, nil
   323	}
   324	
   325	// dropCR drops a terminal \r from the data.
   326	func dropCR(data []byte) []byte {
   327		if len(data) > 0 && data[len(data)-1] == '\r' {
   328			return data[0 : len(data)-1]
   329		}
   330		return data
   331	}
   332	
   333	// ScanLines is a split function for a Scanner that returns each line of
   334	// text, stripped of any trailing end-of-line marker. The returned line may
   335	// be empty. The end-of-line marker is one optional carriage return followed
   336	// by one mandatory newline. In regular expression notation, it is `\r?\n`.
   337	// The last non-empty line of input will be returned even if it has no
   338	// newline.
   339	func ScanLines(data []byte, atEOF bool) (advance int, token []byte, err error) {
   340		if atEOF && len(data) == 0 {
   341			return 0, nil, nil
   342		}
   343		if i := bytes.IndexByte(data, '\n'); i >= 0 {
   344			// We have a full newline-terminated line.
   345			return i + 1, dropCR(data[0:i]), nil
   346		}
   347		// If we're at EOF, we have a final, non-terminated line. Return it.
   348		if atEOF {
   349			return len(data), dropCR(data), nil
   350		}
   351		// Request more data.
   352		return 0, nil, nil
   353	}
   354	
   355	// isSpace reports whether the character is a Unicode white space character.
   356	// We avoid dependency on the unicode package, but check validity of the implementation
   357	// in the tests.
   358	func isSpace(r rune) bool {
   359		if r <= '\u00FF' {
   360			// Obvious ASCII ones: \t through \r plus space. Plus two Latin-1 oddballs.
   361			switch r {
   362			case ' ', '\t', '\n', '\v', '\f', '\r':
   363				return true
   364			case '\u0085', '\u00A0':
   365				return true
   366			}
   367			return false
   368		}
   369		// High-valued ones.
   370		if '\u2000' <= r && r <= '\u200a' {
   371			return true
   372		}
   373		switch r {
   374		case '\u1680', '\u2028', '\u2029', '\u202f', '\u205f', '\u3000':
   375			return true
   376		}
   377		return false
   378	}
   379	
   380	// ScanWords is a split function for a Scanner that returns each
   381	// space-separated word of text, with surrounding spaces deleted. It will
   382	// never return an empty string. The definition of space is set by
   383	// unicode.IsSpace.
   384	func ScanWords(data []byte, atEOF bool) (advance int, token []byte, err error) {
   385		// Skip leading spaces.
   386		start := 0
   387		for width := 0; start < len(data); start += width {
   388			var r rune
   389			r, width = utf8.DecodeRune(data[start:])
   390			if !isSpace(r) {
   391				break
   392			}
   393		}
   394		// Scan until space, marking end of word.
   395		for width, i := 0, start; i < len(data); i += width {
   396			var r rune
   397			r, width = utf8.DecodeRune(data[i:])
   398			if isSpace(r) {
   399				return i + width, data[start:i], nil
   400			}
   401		}
   402		// If we're at EOF, we have a final, non-empty, non-terminated word. Return it.
   403		if atEOF && len(data) > start {
   404			return len(data), data[start:], nil
   405		}
   406		// Request more data.
   407		return start, nil, nil
   408	}
   409	

View as plain text