Source file src/regexp/regexp.go

Documentation: regexp

		 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  // Package regexp implements regular expression search.
		 6  //
		 7  // The syntax of the regular expressions accepted is the same
		 8  // general syntax used by Perl, Python, and other languages.
		 9  // More precisely, it is the syntax accepted by RE2 and described at
		10  // https://golang.org/s/re2syntax, except for \C.
		11  // For an overview of the syntax, run
		12  //	 go doc regexp/syntax
		13  //
		14  // The regexp implementation provided by this package is
		15  // guaranteed to run in time linear in the size of the input.
		16  // (This is a property not guaranteed by most open source
		17  // implementations of regular expressions.) For more information
		18  // about this property, see
		19  //	https://swtch.com/~rsc/regexp/regexp1.html
		20  // or any book about automata theory.
		21  //
		22  // All characters are UTF-8-encoded code points.
		23  //
		24  // There are 16 methods of Regexp that match a regular expression and identify
		25  // the matched text. Their names are matched by this regular expression:
		26  //
		27  //	Find(All)?(String)?(Submatch)?(Index)?
		28  //
		29  // If 'All' is present, the routine matches successive non-overlapping
		30  // matches of the entire expression. Empty matches abutting a preceding
		31  // match are ignored. The return value is a slice containing the successive
		32  // return values of the corresponding non-'All' routine. These routines take
		33  // an extra integer argument, n. If n >= 0, the function returns at most n
		34  // matches/submatches; otherwise, it returns all of them.
		35  //
		36  // If 'String' is present, the argument is a string; otherwise it is a slice
		37  // of bytes; return values are adjusted as appropriate.
		38  //
		39  // If 'Submatch' is present, the return value is a slice identifying the
		40  // successive submatches of the expression. Submatches are matches of
		41  // parenthesized subexpressions (also known as capturing groups) within the
		42  // regular expression, numbered from left to right in order of opening
		43  // parenthesis. Submatch 0 is the match of the entire expression, submatch 1
		44  // the match of the first parenthesized subexpression, and so on.
		45  //
		46  // If 'Index' is present, matches and submatches are identified by byte index
		47  // pairs within the input string: result[2*n:2*n+1] identifies the indexes of
		48  // the nth submatch. The pair for n==0 identifies the match of the entire
		49  // expression. If 'Index' is not present, the match is identified by the text
		50  // of the match/submatch. If an index is negative or text is nil, it means that
		51  // subexpression did not match any string in the input. For 'String' versions
		52  // an empty string means either no match or an empty match.
		53  //
		54  // There is also a subset of the methods that can be applied to text read
		55  // from a RuneReader:
		56  //
		57  //	MatchReader, FindReaderIndex, FindReaderSubmatchIndex
		58  //
		59  // This set may grow. Note that regular expression matches may need to
		60  // examine text beyond the text returned by a match, so the methods that
		61  // match text from a RuneReader may read arbitrarily far into the input
		62  // before returning.
		63  //
		64  // (There are a few other methods that do not match this pattern.)
		65  //
		66  package regexp
		67  
		68  import (
		69  	"bytes"
		70  	"io"
		71  	"regexp/syntax"
		72  	"strconv"
		73  	"strings"
		74  	"sync"
		75  	"unicode"
		76  	"unicode/utf8"
		77  )
		78  
		79  // Regexp is the representation of a compiled regular expression.
		80  // A Regexp is safe for concurrent use by multiple goroutines,
		81  // except for configuration methods, such as Longest.
		82  type Regexp struct {
		83  	expr					 string			 // as passed to Compile
		84  	prog					 *syntax.Prog // compiled program
		85  	onepass				*onePassProg // onepass program or nil
		86  	numSubexp			int
		87  	maxBitStateLen int
		88  	subexpNames		[]string
		89  	prefix				 string				 // required prefix in unanchored matches
		90  	prefixBytes		[]byte				 // prefix, as a []byte
		91  	prefixRune		 rune					 // first rune in prefix
		92  	prefixEnd			uint32				 // pc for last rune in prefix
		93  	mpool					int						// pool for machines
		94  	matchcap			 int						// size of recorded match lengths
		95  	prefixComplete bool					 // prefix is the entire regexp
		96  	cond					 syntax.EmptyOp // empty-width conditions required at start of match
		97  	minInputLen		int						// minimum length of the input in bytes
		98  
		99  	// This field can be modified by the Longest method,
	 100  	// but it is otherwise read-only.
	 101  	longest bool // whether regexp prefers leftmost-longest match
	 102  }
	 103  
	 104  // String returns the source text used to compile the regular expression.
	 105  func (re *Regexp) String() string {
	 106  	return re.expr
	 107  }
	 108  
	 109  // Copy returns a new Regexp object copied from re.
	 110  // Calling Longest on one copy does not affect another.
	 111  //
	 112  // Deprecated: In earlier releases, when using a Regexp in multiple goroutines,
	 113  // giving each goroutine its own copy helped to avoid lock contention.
	 114  // As of Go 1.12, using Copy is no longer necessary to avoid lock contention.
	 115  // Copy may still be appropriate if the reason for its use is to make
	 116  // two copies with different Longest settings.
	 117  func (re *Regexp) Copy() *Regexp {
	 118  	re2 := *re
	 119  	return &re2
	 120  }
	 121  
	 122  // Compile parses a regular expression and returns, if successful,
	 123  // a Regexp object that can be used to match against text.
	 124  //
	 125  // When matching against text, the regexp returns a match that
	 126  // begins as early as possible in the input (leftmost), and among those
	 127  // it chooses the one that a backtracking search would have found first.
	 128  // This so-called leftmost-first matching is the same semantics
	 129  // that Perl, Python, and other implementations use, although this
	 130  // package implements it without the expense of backtracking.
	 131  // For POSIX leftmost-longest matching, see CompilePOSIX.
	 132  func Compile(expr string) (*Regexp, error) {
	 133  	return compile(expr, syntax.Perl, false)
	 134  }
	 135  
	 136  // CompilePOSIX is like Compile but restricts the regular expression
	 137  // to POSIX ERE (egrep) syntax and changes the match semantics to
	 138  // leftmost-longest.
	 139  //
	 140  // That is, when matching against text, the regexp returns a match that
	 141  // begins as early as possible in the input (leftmost), and among those
	 142  // it chooses a match that is as long as possible.
	 143  // This so-called leftmost-longest matching is the same semantics
	 144  // that early regular expression implementations used and that POSIX
	 145  // specifies.
	 146  //
	 147  // However, there can be multiple leftmost-longest matches, with different
	 148  // submatch choices, and here this package diverges from POSIX.
	 149  // Among the possible leftmost-longest matches, this package chooses
	 150  // the one that a backtracking search would have found first, while POSIX
	 151  // specifies that the match be chosen to maximize the length of the first
	 152  // subexpression, then the second, and so on from left to right.
	 153  // The POSIX rule is computationally prohibitive and not even well-defined.
	 154  // See https://swtch.com/~rsc/regexp/regexp2.html#posix for details.
	 155  func CompilePOSIX(expr string) (*Regexp, error) {
	 156  	return compile(expr, syntax.POSIX, true)
	 157  }
	 158  
	 159  // Longest makes future searches prefer the leftmost-longest match.
	 160  // That is, when matching against text, the regexp returns a match that
	 161  // begins as early as possible in the input (leftmost), and among those
	 162  // it chooses a match that is as long as possible.
	 163  // This method modifies the Regexp and may not be called concurrently
	 164  // with any other methods.
	 165  func (re *Regexp) Longest() {
	 166  	re.longest = true
	 167  }
	 168  
	 169  func compile(expr string, mode syntax.Flags, longest bool) (*Regexp, error) {
	 170  	re, err := syntax.Parse(expr, mode)
	 171  	if err != nil {
	 172  		return nil, err
	 173  	}
	 174  	maxCap := re.MaxCap()
	 175  	capNames := re.CapNames()
	 176  
	 177  	re = re.Simplify()
	 178  	prog, err := syntax.Compile(re)
	 179  	if err != nil {
	 180  		return nil, err
	 181  	}
	 182  	matchcap := prog.NumCap
	 183  	if matchcap < 2 {
	 184  		matchcap = 2
	 185  	}
	 186  	regexp := &Regexp{
	 187  		expr:				expr,
	 188  		prog:				prog,
	 189  		onepass:		 compileOnePass(prog),
	 190  		numSubexp:	 maxCap,
	 191  		subexpNames: capNames,
	 192  		cond:				prog.StartCond(),
	 193  		longest:		 longest,
	 194  		matchcap:		matchcap,
	 195  		minInputLen: minInputLen(re),
	 196  	}
	 197  	if regexp.onepass == nil {
	 198  		regexp.prefix, regexp.prefixComplete = prog.Prefix()
	 199  		regexp.maxBitStateLen = maxBitStateLen(prog)
	 200  	} else {
	 201  		regexp.prefix, regexp.prefixComplete, regexp.prefixEnd = onePassPrefix(prog)
	 202  	}
	 203  	if regexp.prefix != "" {
	 204  		// TODO(rsc): Remove this allocation by adding
	 205  		// IndexString to package bytes.
	 206  		regexp.prefixBytes = []byte(regexp.prefix)
	 207  		regexp.prefixRune, _ = utf8.DecodeRuneInString(regexp.prefix)
	 208  	}
	 209  
	 210  	n := len(prog.Inst)
	 211  	i := 0
	 212  	for matchSize[i] != 0 && matchSize[i] < n {
	 213  		i++
	 214  	}
	 215  	regexp.mpool = i
	 216  
	 217  	return regexp, nil
	 218  }
	 219  
	 220  // Pools of *machine for use during (*Regexp).doExecute,
	 221  // split up by the size of the execution queues.
	 222  // matchPool[i] machines have queue size matchSize[i].
	 223  // On a 64-bit system each queue entry is 16 bytes,
	 224  // so matchPool[0] has 16*2*128 = 4kB queues, etc.
	 225  // The final matchPool is a catch-all for very large queues.
	 226  var (
	 227  	matchSize = [...]int{128, 512, 2048, 16384, 0}
	 228  	matchPool [len(matchSize)]sync.Pool
	 229  )
	 230  
	 231  // get returns a machine to use for matching re.
	 232  // It uses the re's machine cache if possible, to avoid
	 233  // unnecessary allocation.
	 234  func (re *Regexp) get() *machine {
	 235  	m, ok := matchPool[re.mpool].Get().(*machine)
	 236  	if !ok {
	 237  		m = new(machine)
	 238  	}
	 239  	m.re = re
	 240  	m.p = re.prog
	 241  	if cap(m.matchcap) < re.matchcap {
	 242  		m.matchcap = make([]int, re.matchcap)
	 243  		for _, t := range m.pool {
	 244  			t.cap = make([]int, re.matchcap)
	 245  		}
	 246  	}
	 247  
	 248  	// Allocate queues if needed.
	 249  	// Or reallocate, for "large" match pool.
	 250  	n := matchSize[re.mpool]
	 251  	if n == 0 { // large pool
	 252  		n = len(re.prog.Inst)
	 253  	}
	 254  	if len(m.q0.sparse) < n {
	 255  		m.q0 = queue{make([]uint32, n), make([]entry, 0, n)}
	 256  		m.q1 = queue{make([]uint32, n), make([]entry, 0, n)}
	 257  	}
	 258  	return m
	 259  }
	 260  
	 261  // put returns a machine to the correct machine pool.
	 262  func (re *Regexp) put(m *machine) {
	 263  	m.re = nil
	 264  	m.p = nil
	 265  	m.inputs.clear()
	 266  	matchPool[re.mpool].Put(m)
	 267  }
	 268  
	 269  // minInputLen walks the regexp to find the minimum length of any matchable input
	 270  func minInputLen(re *syntax.Regexp) int {
	 271  	switch re.Op {
	 272  	default:
	 273  		return 0
	 274  	case syntax.OpAnyChar, syntax.OpAnyCharNotNL, syntax.OpCharClass:
	 275  		return 1
	 276  	case syntax.OpLiteral:
	 277  		l := 0
	 278  		for _, r := range re.Rune {
	 279  			l += utf8.RuneLen(r)
	 280  		}
	 281  		return l
	 282  	case syntax.OpCapture, syntax.OpPlus:
	 283  		return minInputLen(re.Sub[0])
	 284  	case syntax.OpRepeat:
	 285  		return re.Min * minInputLen(re.Sub[0])
	 286  	case syntax.OpConcat:
	 287  		l := 0
	 288  		for _, sub := range re.Sub {
	 289  			l += minInputLen(sub)
	 290  		}
	 291  		return l
	 292  	case syntax.OpAlternate:
	 293  		l := minInputLen(re.Sub[0])
	 294  		var lnext int
	 295  		for _, sub := range re.Sub[1:] {
	 296  			lnext = minInputLen(sub)
	 297  			if lnext < l {
	 298  				l = lnext
	 299  			}
	 300  		}
	 301  		return l
	 302  	}
	 303  }
	 304  
	 305  // MustCompile is like Compile but panics if the expression cannot be parsed.
	 306  // It simplifies safe initialization of global variables holding compiled regular
	 307  // expressions.
	 308  func MustCompile(str string) *Regexp {
	 309  	regexp, err := Compile(str)
	 310  	if err != nil {
	 311  		panic(`regexp: Compile(` + quote(str) + `): ` + err.Error())
	 312  	}
	 313  	return regexp
	 314  }
	 315  
	 316  // MustCompilePOSIX is like CompilePOSIX but panics if the expression cannot be parsed.
	 317  // It simplifies safe initialization of global variables holding compiled regular
	 318  // expressions.
	 319  func MustCompilePOSIX(str string) *Regexp {
	 320  	regexp, err := CompilePOSIX(str)
	 321  	if err != nil {
	 322  		panic(`regexp: CompilePOSIX(` + quote(str) + `): ` + err.Error())
	 323  	}
	 324  	return regexp
	 325  }
	 326  
	 327  func quote(s string) string {
	 328  	if strconv.CanBackquote(s) {
	 329  		return "`" + s + "`"
	 330  	}
	 331  	return strconv.Quote(s)
	 332  }
	 333  
	 334  // NumSubexp returns the number of parenthesized subexpressions in this Regexp.
	 335  func (re *Regexp) NumSubexp() int {
	 336  	return re.numSubexp
	 337  }
	 338  
	 339  // SubexpNames returns the names of the parenthesized subexpressions
	 340  // in this Regexp. The name for the first sub-expression is names[1],
	 341  // so that if m is a match slice, the name for m[i] is SubexpNames()[i].
	 342  // Since the Regexp as a whole cannot be named, names[0] is always
	 343  // the empty string. The slice should not be modified.
	 344  func (re *Regexp) SubexpNames() []string {
	 345  	return re.subexpNames
	 346  }
	 347  
	 348  // SubexpIndex returns the index of the first subexpression with the given name,
	 349  // or -1 if there is no subexpression with that name.
	 350  //
	 351  // Note that multiple subexpressions can be written using the same name, as in
	 352  // (?P<bob>a+)(?P<bob>b+), which declares two subexpressions named "bob".
	 353  // In this case, SubexpIndex returns the index of the leftmost such subexpression
	 354  // in the regular expression.
	 355  func (re *Regexp) SubexpIndex(name string) int {
	 356  	if name != "" {
	 357  		for i, s := range re.subexpNames {
	 358  			if name == s {
	 359  				return i
	 360  			}
	 361  		}
	 362  	}
	 363  	return -1
	 364  }
	 365  
	 366  const endOfText rune = -1
	 367  
	 368  // input abstracts different representations of the input text. It provides
	 369  // one-character lookahead.
	 370  type input interface {
	 371  	step(pos int) (r rune, width int) // advance one rune
	 372  	canCheckPrefix() bool						 // can we look ahead without losing info?
	 373  	hasPrefix(re *Regexp) bool
	 374  	index(re *Regexp, pos int) int
	 375  	context(pos int) lazyFlag
	 376  }
	 377  
	 378  // inputString scans a string.
	 379  type inputString struct {
	 380  	str string
	 381  }
	 382  
	 383  func (i *inputString) step(pos int) (rune, int) {
	 384  	if pos < len(i.str) {
	 385  		c := i.str[pos]
	 386  		if c < utf8.RuneSelf {
	 387  			return rune(c), 1
	 388  		}
	 389  		return utf8.DecodeRuneInString(i.str[pos:])
	 390  	}
	 391  	return endOfText, 0
	 392  }
	 393  
	 394  func (i *inputString) canCheckPrefix() bool {
	 395  	return true
	 396  }
	 397  
	 398  func (i *inputString) hasPrefix(re *Regexp) bool {
	 399  	return strings.HasPrefix(i.str, re.prefix)
	 400  }
	 401  
	 402  func (i *inputString) index(re *Regexp, pos int) int {
	 403  	return strings.Index(i.str[pos:], re.prefix)
	 404  }
	 405  
	 406  func (i *inputString) context(pos int) lazyFlag {
	 407  	r1, r2 := endOfText, endOfText
	 408  	// 0 < pos && pos <= len(i.str)
	 409  	if uint(pos-1) < uint(len(i.str)) {
	 410  		r1 = rune(i.str[pos-1])
	 411  		if r1 >= utf8.RuneSelf {
	 412  			r1, _ = utf8.DecodeLastRuneInString(i.str[:pos])
	 413  		}
	 414  	}
	 415  	// 0 <= pos && pos < len(i.str)
	 416  	if uint(pos) < uint(len(i.str)) {
	 417  		r2 = rune(i.str[pos])
	 418  		if r2 >= utf8.RuneSelf {
	 419  			r2, _ = utf8.DecodeRuneInString(i.str[pos:])
	 420  		}
	 421  	}
	 422  	return newLazyFlag(r1, r2)
	 423  }
	 424  
	 425  // inputBytes scans a byte slice.
	 426  type inputBytes struct {
	 427  	str []byte
	 428  }
	 429  
	 430  func (i *inputBytes) step(pos int) (rune, int) {
	 431  	if pos < len(i.str) {
	 432  		c := i.str[pos]
	 433  		if c < utf8.RuneSelf {
	 434  			return rune(c), 1
	 435  		}
	 436  		return utf8.DecodeRune(i.str[pos:])
	 437  	}
	 438  	return endOfText, 0
	 439  }
	 440  
	 441  func (i *inputBytes) canCheckPrefix() bool {
	 442  	return true
	 443  }
	 444  
	 445  func (i *inputBytes) hasPrefix(re *Regexp) bool {
	 446  	return bytes.HasPrefix(i.str, re.prefixBytes)
	 447  }
	 448  
	 449  func (i *inputBytes) index(re *Regexp, pos int) int {
	 450  	return bytes.Index(i.str[pos:], re.prefixBytes)
	 451  }
	 452  
	 453  func (i *inputBytes) context(pos int) lazyFlag {
	 454  	r1, r2 := endOfText, endOfText
	 455  	// 0 < pos && pos <= len(i.str)
	 456  	if uint(pos-1) < uint(len(i.str)) {
	 457  		r1 = rune(i.str[pos-1])
	 458  		if r1 >= utf8.RuneSelf {
	 459  			r1, _ = utf8.DecodeLastRune(i.str[:pos])
	 460  		}
	 461  	}
	 462  	// 0 <= pos && pos < len(i.str)
	 463  	if uint(pos) < uint(len(i.str)) {
	 464  		r2 = rune(i.str[pos])
	 465  		if r2 >= utf8.RuneSelf {
	 466  			r2, _ = utf8.DecodeRune(i.str[pos:])
	 467  		}
	 468  	}
	 469  	return newLazyFlag(r1, r2)
	 470  }
	 471  
	 472  // inputReader scans a RuneReader.
	 473  type inputReader struct {
	 474  	r		 io.RuneReader
	 475  	atEOT bool
	 476  	pos	 int
	 477  }
	 478  
	 479  func (i *inputReader) step(pos int) (rune, int) {
	 480  	if !i.atEOT && pos != i.pos {
	 481  		return endOfText, 0
	 482  
	 483  	}
	 484  	r, w, err := i.r.ReadRune()
	 485  	if err != nil {
	 486  		i.atEOT = true
	 487  		return endOfText, 0
	 488  	}
	 489  	i.pos += w
	 490  	return r, w
	 491  }
	 492  
	 493  func (i *inputReader) canCheckPrefix() bool {
	 494  	return false
	 495  }
	 496  
	 497  func (i *inputReader) hasPrefix(re *Regexp) bool {
	 498  	return false
	 499  }
	 500  
	 501  func (i *inputReader) index(re *Regexp, pos int) int {
	 502  	return -1
	 503  }
	 504  
	 505  func (i *inputReader) context(pos int) lazyFlag {
	 506  	return 0 // not used
	 507  }
	 508  
	 509  // LiteralPrefix returns a literal string that must begin any match
	 510  // of the regular expression re. It returns the boolean true if the
	 511  // literal string comprises the entire regular expression.
	 512  func (re *Regexp) LiteralPrefix() (prefix string, complete bool) {
	 513  	return re.prefix, re.prefixComplete
	 514  }
	 515  
	 516  // MatchReader reports whether the text returned by the RuneReader
	 517  // contains any match of the regular expression re.
	 518  func (re *Regexp) MatchReader(r io.RuneReader) bool {
	 519  	return re.doMatch(r, nil, "")
	 520  }
	 521  
	 522  // MatchString reports whether the string s
	 523  // contains any match of the regular expression re.
	 524  func (re *Regexp) MatchString(s string) bool {
	 525  	return re.doMatch(nil, nil, s)
	 526  }
	 527  
	 528  // Match reports whether the byte slice b
	 529  // contains any match of the regular expression re.
	 530  func (re *Regexp) Match(b []byte) bool {
	 531  	return re.doMatch(nil, b, "")
	 532  }
	 533  
	 534  // MatchReader reports whether the text returned by the RuneReader
	 535  // contains any match of the regular expression pattern.
	 536  // More complicated queries need to use Compile and the full Regexp interface.
	 537  func MatchReader(pattern string, r io.RuneReader) (matched bool, err error) {
	 538  	re, err := Compile(pattern)
	 539  	if err != nil {
	 540  		return false, err
	 541  	}
	 542  	return re.MatchReader(r), nil
	 543  }
	 544  
	 545  // MatchString reports whether the string s
	 546  // contains any match of the regular expression pattern.
	 547  // More complicated queries need to use Compile and the full Regexp interface.
	 548  func MatchString(pattern string, s string) (matched bool, err error) {
	 549  	re, err := Compile(pattern)
	 550  	if err != nil {
	 551  		return false, err
	 552  	}
	 553  	return re.MatchString(s), nil
	 554  }
	 555  
	 556  // Match reports whether the byte slice b
	 557  // contains any match of the regular expression pattern.
	 558  // More complicated queries need to use Compile and the full Regexp interface.
	 559  func Match(pattern string, b []byte) (matched bool, err error) {
	 560  	re, err := Compile(pattern)
	 561  	if err != nil {
	 562  		return false, err
	 563  	}
	 564  	return re.Match(b), nil
	 565  }
	 566  
	 567  // ReplaceAllString returns a copy of src, replacing matches of the Regexp
	 568  // with the replacement string repl. Inside repl, $ signs are interpreted as
	 569  // in Expand, so for instance $1 represents the text of the first submatch.
	 570  func (re *Regexp) ReplaceAllString(src, repl string) string {
	 571  	n := 2
	 572  	if strings.Contains(repl, "$") {
	 573  		n = 2 * (re.numSubexp + 1)
	 574  	}
	 575  	b := re.replaceAll(nil, src, n, func(dst []byte, match []int) []byte {
	 576  		return re.expand(dst, repl, nil, src, match)
	 577  	})
	 578  	return string(b)
	 579  }
	 580  
	 581  // ReplaceAllLiteralString returns a copy of src, replacing matches of the Regexp
	 582  // with the replacement string repl. The replacement repl is substituted directly,
	 583  // without using Expand.
	 584  func (re *Regexp) ReplaceAllLiteralString(src, repl string) string {
	 585  	return string(re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
	 586  		return append(dst, repl...)
	 587  	}))
	 588  }
	 589  
	 590  // ReplaceAllStringFunc returns a copy of src in which all matches of the
	 591  // Regexp have been replaced by the return value of function repl applied
	 592  // to the matched substring. The replacement returned by repl is substituted
	 593  // directly, without using Expand.
	 594  func (re *Regexp) ReplaceAllStringFunc(src string, repl func(string) string) string {
	 595  	b := re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
	 596  		return append(dst, repl(src[match[0]:match[1]])...)
	 597  	})
	 598  	return string(b)
	 599  }
	 600  
	 601  func (re *Regexp) replaceAll(bsrc []byte, src string, nmatch int, repl func(dst []byte, m []int) []byte) []byte {
	 602  	lastMatchEnd := 0 // end position of the most recent match
	 603  	searchPos := 0		// position where we next look for a match
	 604  	var buf []byte
	 605  	var endPos int
	 606  	if bsrc != nil {
	 607  		endPos = len(bsrc)
	 608  	} else {
	 609  		endPos = len(src)
	 610  	}
	 611  	if nmatch > re.prog.NumCap {
	 612  		nmatch = re.prog.NumCap
	 613  	}
	 614  
	 615  	var dstCap [2]int
	 616  	for searchPos <= endPos {
	 617  		a := re.doExecute(nil, bsrc, src, searchPos, nmatch, dstCap[:0])
	 618  		if len(a) == 0 {
	 619  			break // no more matches
	 620  		}
	 621  
	 622  		// Copy the unmatched characters before this match.
	 623  		if bsrc != nil {
	 624  			buf = append(buf, bsrc[lastMatchEnd:a[0]]...)
	 625  		} else {
	 626  			buf = append(buf, src[lastMatchEnd:a[0]]...)
	 627  		}
	 628  
	 629  		// Now insert a copy of the replacement string, but not for a
	 630  		// match of the empty string immediately after another match.
	 631  		// (Otherwise, we get double replacement for patterns that
	 632  		// match both empty and nonempty strings.)
	 633  		if a[1] > lastMatchEnd || a[0] == 0 {
	 634  			buf = repl(buf, a)
	 635  		}
	 636  		lastMatchEnd = a[1]
	 637  
	 638  		// Advance past this match; always advance at least one character.
	 639  		var width int
	 640  		if bsrc != nil {
	 641  			_, width = utf8.DecodeRune(bsrc[searchPos:])
	 642  		} else {
	 643  			_, width = utf8.DecodeRuneInString(src[searchPos:])
	 644  		}
	 645  		if searchPos+width > a[1] {
	 646  			searchPos += width
	 647  		} else if searchPos+1 > a[1] {
	 648  			// This clause is only needed at the end of the input
	 649  			// string. In that case, DecodeRuneInString returns width=0.
	 650  			searchPos++
	 651  		} else {
	 652  			searchPos = a[1]
	 653  		}
	 654  	}
	 655  
	 656  	// Copy the unmatched characters after the last match.
	 657  	if bsrc != nil {
	 658  		buf = append(buf, bsrc[lastMatchEnd:]...)
	 659  	} else {
	 660  		buf = append(buf, src[lastMatchEnd:]...)
	 661  	}
	 662  
	 663  	return buf
	 664  }
	 665  
	 666  // ReplaceAll returns a copy of src, replacing matches of the Regexp
	 667  // with the replacement text repl. Inside repl, $ signs are interpreted as
	 668  // in Expand, so for instance $1 represents the text of the first submatch.
	 669  func (re *Regexp) ReplaceAll(src, repl []byte) []byte {
	 670  	n := 2
	 671  	if bytes.IndexByte(repl, '$') >= 0 {
	 672  		n = 2 * (re.numSubexp + 1)
	 673  	}
	 674  	srepl := ""
	 675  	b := re.replaceAll(src, "", n, func(dst []byte, match []int) []byte {
	 676  		if len(srepl) != len(repl) {
	 677  			srepl = string(repl)
	 678  		}
	 679  		return re.expand(dst, srepl, src, "", match)
	 680  	})
	 681  	return b
	 682  }
	 683  
	 684  // ReplaceAllLiteral returns a copy of src, replacing matches of the Regexp
	 685  // with the replacement bytes repl. The replacement repl is substituted directly,
	 686  // without using Expand.
	 687  func (re *Regexp) ReplaceAllLiteral(src, repl []byte) []byte {
	 688  	return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
	 689  		return append(dst, repl...)
	 690  	})
	 691  }
	 692  
	 693  // ReplaceAllFunc returns a copy of src in which all matches of the
	 694  // Regexp have been replaced by the return value of function repl applied
	 695  // to the matched byte slice. The replacement returned by repl is substituted
	 696  // directly, without using Expand.
	 697  func (re *Regexp) ReplaceAllFunc(src []byte, repl func([]byte) []byte) []byte {
	 698  	return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
	 699  		return append(dst, repl(src[match[0]:match[1]])...)
	 700  	})
	 701  }
	 702  
	 703  // Bitmap used by func special to check whether a character needs to be escaped.
	 704  var specialBytes [16]byte
	 705  
	 706  // special reports whether byte b needs to be escaped by QuoteMeta.
	 707  func special(b byte) bool {
	 708  	return b < utf8.RuneSelf && specialBytes[b%16]&(1<<(b/16)) != 0
	 709  }
	 710  
	 711  func init() {
	 712  	for _, b := range []byte(`\.+*?()|[]{}^$`) {
	 713  		specialBytes[b%16] |= 1 << (b / 16)
	 714  	}
	 715  }
	 716  
	 717  // QuoteMeta returns a string that escapes all regular expression metacharacters
	 718  // inside the argument text; the returned string is a regular expression matching
	 719  // the literal text.
	 720  func QuoteMeta(s string) string {
	 721  	// A byte loop is correct because all metacharacters are ASCII.
	 722  	var i int
	 723  	for i = 0; i < len(s); i++ {
	 724  		if special(s[i]) {
	 725  			break
	 726  		}
	 727  	}
	 728  	// No meta characters found, so return original string.
	 729  	if i >= len(s) {
	 730  		return s
	 731  	}
	 732  
	 733  	b := make([]byte, 2*len(s)-i)
	 734  	copy(b, s[:i])
	 735  	j := i
	 736  	for ; i < len(s); i++ {
	 737  		if special(s[i]) {
	 738  			b[j] = '\\'
	 739  			j++
	 740  		}
	 741  		b[j] = s[i]
	 742  		j++
	 743  	}
	 744  	return string(b[:j])
	 745  }
	 746  
	 747  // The number of capture values in the program may correspond
	 748  // to fewer capturing expressions than are in the regexp.
	 749  // For example, "(a){0}" turns into an empty program, so the
	 750  // maximum capture in the program is 0 but we need to return
	 751  // an expression for \1.	Pad appends -1s to the slice a as needed.
	 752  func (re *Regexp) pad(a []int) []int {
	 753  	if a == nil {
	 754  		// No match.
	 755  		return nil
	 756  	}
	 757  	n := (1 + re.numSubexp) * 2
	 758  	for len(a) < n {
	 759  		a = append(a, -1)
	 760  	}
	 761  	return a
	 762  }
	 763  
	 764  // allMatches calls deliver at most n times
	 765  // with the location of successive matches in the input text.
	 766  // The input text is b if non-nil, otherwise s.
	 767  func (re *Regexp) allMatches(s string, b []byte, n int, deliver func([]int)) {
	 768  	var end int
	 769  	if b == nil {
	 770  		end = len(s)
	 771  	} else {
	 772  		end = len(b)
	 773  	}
	 774  
	 775  	for pos, i, prevMatchEnd := 0, 0, -1; i < n && pos <= end; {
	 776  		matches := re.doExecute(nil, b, s, pos, re.prog.NumCap, nil)
	 777  		if len(matches) == 0 {
	 778  			break
	 779  		}
	 780  
	 781  		accept := true
	 782  		if matches[1] == pos {
	 783  			// We've found an empty match.
	 784  			if matches[0] == prevMatchEnd {
	 785  				// We don't allow an empty match right
	 786  				// after a previous match, so ignore it.
	 787  				accept = false
	 788  			}
	 789  			var width int
	 790  			// TODO: use step()
	 791  			if b == nil {
	 792  				_, width = utf8.DecodeRuneInString(s[pos:end])
	 793  			} else {
	 794  				_, width = utf8.DecodeRune(b[pos:end])
	 795  			}
	 796  			if width > 0 {
	 797  				pos += width
	 798  			} else {
	 799  				pos = end + 1
	 800  			}
	 801  		} else {
	 802  			pos = matches[1]
	 803  		}
	 804  		prevMatchEnd = matches[1]
	 805  
	 806  		if accept {
	 807  			deliver(re.pad(matches))
	 808  			i++
	 809  		}
	 810  	}
	 811  }
	 812  
	 813  // Find returns a slice holding the text of the leftmost match in b of the regular expression.
	 814  // A return value of nil indicates no match.
	 815  func (re *Regexp) Find(b []byte) []byte {
	 816  	var dstCap [2]int
	 817  	a := re.doExecute(nil, b, "", 0, 2, dstCap[:0])
	 818  	if a == nil {
	 819  		return nil
	 820  	}
	 821  	return b[a[0]:a[1]:a[1]]
	 822  }
	 823  
	 824  // FindIndex returns a two-element slice of integers defining the location of
	 825  // the leftmost match in b of the regular expression. The match itself is at
	 826  // b[loc[0]:loc[1]].
	 827  // A return value of nil indicates no match.
	 828  func (re *Regexp) FindIndex(b []byte) (loc []int) {
	 829  	a := re.doExecute(nil, b, "", 0, 2, nil)
	 830  	if a == nil {
	 831  		return nil
	 832  	}
	 833  	return a[0:2]
	 834  }
	 835  
	 836  // FindString returns a string holding the text of the leftmost match in s of the regular
	 837  // expression. If there is no match, the return value is an empty string,
	 838  // but it will also be empty if the regular expression successfully matches
	 839  // an empty string. Use FindStringIndex or FindStringSubmatch if it is
	 840  // necessary to distinguish these cases.
	 841  func (re *Regexp) FindString(s string) string {
	 842  	var dstCap [2]int
	 843  	a := re.doExecute(nil, nil, s, 0, 2, dstCap[:0])
	 844  	if a == nil {
	 845  		return ""
	 846  	}
	 847  	return s[a[0]:a[1]]
	 848  }
	 849  
	 850  // FindStringIndex returns a two-element slice of integers defining the
	 851  // location of the leftmost match in s of the regular expression. The match
	 852  // itself is at s[loc[0]:loc[1]].
	 853  // A return value of nil indicates no match.
	 854  func (re *Regexp) FindStringIndex(s string) (loc []int) {
	 855  	a := re.doExecute(nil, nil, s, 0, 2, nil)
	 856  	if a == nil {
	 857  		return nil
	 858  	}
	 859  	return a[0:2]
	 860  }
	 861  
	 862  // FindReaderIndex returns a two-element slice of integers defining the
	 863  // location of the leftmost match of the regular expression in text read from
	 864  // the RuneReader. The match text was found in the input stream at
	 865  // byte offset loc[0] through loc[1]-1.
	 866  // A return value of nil indicates no match.
	 867  func (re *Regexp) FindReaderIndex(r io.RuneReader) (loc []int) {
	 868  	a := re.doExecute(r, nil, "", 0, 2, nil)
	 869  	if a == nil {
	 870  		return nil
	 871  	}
	 872  	return a[0:2]
	 873  }
	 874  
	 875  // FindSubmatch returns a slice of slices holding the text of the leftmost
	 876  // match of the regular expression in b and the matches, if any, of its
	 877  // subexpressions, as defined by the 'Submatch' descriptions in the package
	 878  // comment.
	 879  // A return value of nil indicates no match.
	 880  func (re *Regexp) FindSubmatch(b []byte) [][]byte {
	 881  	var dstCap [4]int
	 882  	a := re.doExecute(nil, b, "", 0, re.prog.NumCap, dstCap[:0])
	 883  	if a == nil {
	 884  		return nil
	 885  	}
	 886  	ret := make([][]byte, 1+re.numSubexp)
	 887  	for i := range ret {
	 888  		if 2*i < len(a) && a[2*i] >= 0 {
	 889  			ret[i] = b[a[2*i]:a[2*i+1]:a[2*i+1]]
	 890  		}
	 891  	}
	 892  	return ret
	 893  }
	 894  
	 895  // Expand appends template to dst and returns the result; during the
	 896  // append, Expand replaces variables in the template with corresponding
	 897  // matches drawn from src. The match slice should have been returned by
	 898  // FindSubmatchIndex.
	 899  //
	 900  // In the template, a variable is denoted by a substring of the form
	 901  // $name or ${name}, where name is a non-empty sequence of letters,
	 902  // digits, and underscores. A purely numeric name like $1 refers to
	 903  // the submatch with the corresponding index; other names refer to
	 904  // capturing parentheses named with the (?P<name>...) syntax. A
	 905  // reference to an out of range or unmatched index or a name that is not
	 906  // present in the regular expression is replaced with an empty slice.
	 907  //
	 908  // In the $name form, name is taken to be as long as possible: $1x is
	 909  // equivalent to ${1x}, not ${1}x, and, $10 is equivalent to ${10}, not ${1}0.
	 910  //
	 911  // To insert a literal $ in the output, use $$ in the template.
	 912  func (re *Regexp) Expand(dst []byte, template []byte, src []byte, match []int) []byte {
	 913  	return re.expand(dst, string(template), src, "", match)
	 914  }
	 915  
	 916  // ExpandString is like Expand but the template and source are strings.
	 917  // It appends to and returns a byte slice in order to give the calling
	 918  // code control over allocation.
	 919  func (re *Regexp) ExpandString(dst []byte, template string, src string, match []int) []byte {
	 920  	return re.expand(dst, template, nil, src, match)
	 921  }
	 922  
	 923  func (re *Regexp) expand(dst []byte, template string, bsrc []byte, src string, match []int) []byte {
	 924  	for len(template) > 0 {
	 925  		i := strings.Index(template, "$")
	 926  		if i < 0 {
	 927  			break
	 928  		}
	 929  		dst = append(dst, template[:i]...)
	 930  		template = template[i:]
	 931  		if len(template) > 1 && template[1] == '$' {
	 932  			// Treat $$ as $.
	 933  			dst = append(dst, '$')
	 934  			template = template[2:]
	 935  			continue
	 936  		}
	 937  		name, num, rest, ok := extract(template)
	 938  		if !ok {
	 939  			// Malformed; treat $ as raw text.
	 940  			dst = append(dst, '$')
	 941  			template = template[1:]
	 942  			continue
	 943  		}
	 944  		template = rest
	 945  		if num >= 0 {
	 946  			if 2*num+1 < len(match) && match[2*num] >= 0 {
	 947  				if bsrc != nil {
	 948  					dst = append(dst, bsrc[match[2*num]:match[2*num+1]]...)
	 949  				} else {
	 950  					dst = append(dst, src[match[2*num]:match[2*num+1]]...)
	 951  				}
	 952  			}
	 953  		} else {
	 954  			for i, namei := range re.subexpNames {
	 955  				if name == namei && 2*i+1 < len(match) && match[2*i] >= 0 {
	 956  					if bsrc != nil {
	 957  						dst = append(dst, bsrc[match[2*i]:match[2*i+1]]...)
	 958  					} else {
	 959  						dst = append(dst, src[match[2*i]:match[2*i+1]]...)
	 960  					}
	 961  					break
	 962  				}
	 963  			}
	 964  		}
	 965  	}
	 966  	dst = append(dst, template...)
	 967  	return dst
	 968  }
	 969  
	 970  // extract returns the name from a leading "$name" or "${name}" in str.
	 971  // If it is a number, extract returns num set to that number; otherwise num = -1.
	 972  func extract(str string) (name string, num int, rest string, ok bool) {
	 973  	if len(str) < 2 || str[0] != '$' {
	 974  		return
	 975  	}
	 976  	brace := false
	 977  	if str[1] == '{' {
	 978  		brace = true
	 979  		str = str[2:]
	 980  	} else {
	 981  		str = str[1:]
	 982  	}
	 983  	i := 0
	 984  	for i < len(str) {
	 985  		rune, size := utf8.DecodeRuneInString(str[i:])
	 986  		if !unicode.IsLetter(rune) && !unicode.IsDigit(rune) && rune != '_' {
	 987  			break
	 988  		}
	 989  		i += size
	 990  	}
	 991  	if i == 0 {
	 992  		// empty name is not okay
	 993  		return
	 994  	}
	 995  	name = str[:i]
	 996  	if brace {
	 997  		if i >= len(str) || str[i] != '}' {
	 998  			// missing closing brace
	 999  			return
	1000  		}
	1001  		i++
	1002  	}
	1003  
	1004  	// Parse number.
	1005  	num = 0
	1006  	for i := 0; i < len(name); i++ {
	1007  		if name[i] < '0' || '9' < name[i] || num >= 1e8 {
	1008  			num = -1
	1009  			break
	1010  		}
	1011  		num = num*10 + int(name[i]) - '0'
	1012  	}
	1013  	// Disallow leading zeros.
	1014  	if name[0] == '0' && len(name) > 1 {
	1015  		num = -1
	1016  	}
	1017  
	1018  	rest = str[i:]
	1019  	ok = true
	1020  	return
	1021  }
	1022  
	1023  // FindSubmatchIndex returns a slice holding the index pairs identifying the
	1024  // leftmost match of the regular expression in b and the matches, if any, of
	1025  // its subexpressions, as defined by the 'Submatch' and 'Index' descriptions
	1026  // in the package comment.
	1027  // A return value of nil indicates no match.
	1028  func (re *Regexp) FindSubmatchIndex(b []byte) []int {
	1029  	return re.pad(re.doExecute(nil, b, "", 0, re.prog.NumCap, nil))
	1030  }
	1031  
	1032  // FindStringSubmatch returns a slice of strings holding the text of the
	1033  // leftmost match of the regular expression in s and the matches, if any, of
	1034  // its subexpressions, as defined by the 'Submatch' description in the
	1035  // package comment.
	1036  // A return value of nil indicates no match.
	1037  func (re *Regexp) FindStringSubmatch(s string) []string {
	1038  	var dstCap [4]int
	1039  	a := re.doExecute(nil, nil, s, 0, re.prog.NumCap, dstCap[:0])
	1040  	if a == nil {
	1041  		return nil
	1042  	}
	1043  	ret := make([]string, 1+re.numSubexp)
	1044  	for i := range ret {
	1045  		if 2*i < len(a) && a[2*i] >= 0 {
	1046  			ret[i] = s[a[2*i]:a[2*i+1]]
	1047  		}
	1048  	}
	1049  	return ret
	1050  }
	1051  
	1052  // FindStringSubmatchIndex returns a slice holding the index pairs
	1053  // identifying the leftmost match of the regular expression in s and the
	1054  // matches, if any, of its subexpressions, as defined by the 'Submatch' and
	1055  // 'Index' descriptions in the package comment.
	1056  // A return value of nil indicates no match.
	1057  func (re *Regexp) FindStringSubmatchIndex(s string) []int {
	1058  	return re.pad(re.doExecute(nil, nil, s, 0, re.prog.NumCap, nil))
	1059  }
	1060  
	1061  // FindReaderSubmatchIndex returns a slice holding the index pairs
	1062  // identifying the leftmost match of the regular expression of text read by
	1063  // the RuneReader, and the matches, if any, of its subexpressions, as defined
	1064  // by the 'Submatch' and 'Index' descriptions in the package comment. A
	1065  // return value of nil indicates no match.
	1066  func (re *Regexp) FindReaderSubmatchIndex(r io.RuneReader) []int {
	1067  	return re.pad(re.doExecute(r, nil, "", 0, re.prog.NumCap, nil))
	1068  }
	1069  
	1070  const startSize = 10 // The size at which to start a slice in the 'All' routines.
	1071  
	1072  // FindAll is the 'All' version of Find; it returns a slice of all successive
	1073  // matches of the expression, as defined by the 'All' description in the
	1074  // package comment.
	1075  // A return value of nil indicates no match.
	1076  func (re *Regexp) FindAll(b []byte, n int) [][]byte {
	1077  	if n < 0 {
	1078  		n = len(b) + 1
	1079  	}
	1080  	var result [][]byte
	1081  	re.allMatches("", b, n, func(match []int) {
	1082  		if result == nil {
	1083  			result = make([][]byte, 0, startSize)
	1084  		}
	1085  		result = append(result, b[match[0]:match[1]:match[1]])
	1086  	})
	1087  	return result
	1088  }
	1089  
	1090  // FindAllIndex is the 'All' version of FindIndex; it returns a slice of all
	1091  // successive matches of the expression, as defined by the 'All' description
	1092  // in the package comment.
	1093  // A return value of nil indicates no match.
	1094  func (re *Regexp) FindAllIndex(b []byte, n int) [][]int {
	1095  	if n < 0 {
	1096  		n = len(b) + 1
	1097  	}
	1098  	var result [][]int
	1099  	re.allMatches("", b, n, func(match []int) {
	1100  		if result == nil {
	1101  			result = make([][]int, 0, startSize)
	1102  		}
	1103  		result = append(result, match[0:2])
	1104  	})
	1105  	return result
	1106  }
	1107  
	1108  // FindAllString is the 'All' version of FindString; it returns a slice of all
	1109  // successive matches of the expression, as defined by the 'All' description
	1110  // in the package comment.
	1111  // A return value of nil indicates no match.
	1112  func (re *Regexp) FindAllString(s string, n int) []string {
	1113  	if n < 0 {
	1114  		n = len(s) + 1
	1115  	}
	1116  	var result []string
	1117  	re.allMatches(s, nil, n, func(match []int) {
	1118  		if result == nil {
	1119  			result = make([]string, 0, startSize)
	1120  		}
	1121  		result = append(result, s[match[0]:match[1]])
	1122  	})
	1123  	return result
	1124  }
	1125  
	1126  // FindAllStringIndex is the 'All' version of FindStringIndex; it returns a
	1127  // slice of all successive matches of the expression, as defined by the 'All'
	1128  // description in the package comment.
	1129  // A return value of nil indicates no match.
	1130  func (re *Regexp) FindAllStringIndex(s string, n int) [][]int {
	1131  	if n < 0 {
	1132  		n = len(s) + 1
	1133  	}
	1134  	var result [][]int
	1135  	re.allMatches(s, nil, n, func(match []int) {
	1136  		if result == nil {
	1137  			result = make([][]int, 0, startSize)
	1138  		}
	1139  		result = append(result, match[0:2])
	1140  	})
	1141  	return result
	1142  }
	1143  
	1144  // FindAllSubmatch is the 'All' version of FindSubmatch; it returns a slice
	1145  // of all successive matches of the expression, as defined by the 'All'
	1146  // description in the package comment.
	1147  // A return value of nil indicates no match.
	1148  func (re *Regexp) FindAllSubmatch(b []byte, n int) [][][]byte {
	1149  	if n < 0 {
	1150  		n = len(b) + 1
	1151  	}
	1152  	var result [][][]byte
	1153  	re.allMatches("", b, n, func(match []int) {
	1154  		if result == nil {
	1155  			result = make([][][]byte, 0, startSize)
	1156  		}
	1157  		slice := make([][]byte, len(match)/2)
	1158  		for j := range slice {
	1159  			if match[2*j] >= 0 {
	1160  				slice[j] = b[match[2*j]:match[2*j+1]:match[2*j+1]]
	1161  			}
	1162  		}
	1163  		result = append(result, slice)
	1164  	})
	1165  	return result
	1166  }
	1167  
	1168  // FindAllSubmatchIndex is the 'All' version of FindSubmatchIndex; it returns
	1169  // a slice of all successive matches of the expression, as defined by the
	1170  // 'All' description in the package comment.
	1171  // A return value of nil indicates no match.
	1172  func (re *Regexp) FindAllSubmatchIndex(b []byte, n int) [][]int {
	1173  	if n < 0 {
	1174  		n = len(b) + 1
	1175  	}
	1176  	var result [][]int
	1177  	re.allMatches("", b, n, func(match []int) {
	1178  		if result == nil {
	1179  			result = make([][]int, 0, startSize)
	1180  		}
	1181  		result = append(result, match)
	1182  	})
	1183  	return result
	1184  }
	1185  
	1186  // FindAllStringSubmatch is the 'All' version of FindStringSubmatch; it
	1187  // returns a slice of all successive matches of the expression, as defined by
	1188  // the 'All' description in the package comment.
	1189  // A return value of nil indicates no match.
	1190  func (re *Regexp) FindAllStringSubmatch(s string, n int) [][]string {
	1191  	if n < 0 {
	1192  		n = len(s) + 1
	1193  	}
	1194  	var result [][]string
	1195  	re.allMatches(s, nil, n, func(match []int) {
	1196  		if result == nil {
	1197  			result = make([][]string, 0, startSize)
	1198  		}
	1199  		slice := make([]string, len(match)/2)
	1200  		for j := range slice {
	1201  			if match[2*j] >= 0 {
	1202  				slice[j] = s[match[2*j]:match[2*j+1]]
	1203  			}
	1204  		}
	1205  		result = append(result, slice)
	1206  	})
	1207  	return result
	1208  }
	1209  
	1210  // FindAllStringSubmatchIndex is the 'All' version of
	1211  // FindStringSubmatchIndex; it returns a slice of all successive matches of
	1212  // the expression, as defined by the 'All' description in the package
	1213  // comment.
	1214  // A return value of nil indicates no match.
	1215  func (re *Regexp) FindAllStringSubmatchIndex(s string, n int) [][]int {
	1216  	if n < 0 {
	1217  		n = len(s) + 1
	1218  	}
	1219  	var result [][]int
	1220  	re.allMatches(s, nil, n, func(match []int) {
	1221  		if result == nil {
	1222  			result = make([][]int, 0, startSize)
	1223  		}
	1224  		result = append(result, match)
	1225  	})
	1226  	return result
	1227  }
	1228  
	1229  // Split slices s into substrings separated by the expression and returns a slice of
	1230  // the substrings between those expression matches.
	1231  //
	1232  // The slice returned by this method consists of all the substrings of s
	1233  // not contained in the slice returned by FindAllString. When called on an expression
	1234  // that contains no metacharacters, it is equivalent to strings.SplitN.
	1235  //
	1236  // Example:
	1237  //	 s := regexp.MustCompile("a*").Split("abaabaccadaaae", 5)
	1238  //	 // s: ["", "b", "b", "c", "cadaaae"]
	1239  //
	1240  // The count determines the number of substrings to return:
	1241  //	 n > 0: at most n substrings; the last substring will be the unsplit remainder.
	1242  //	 n == 0: the result is nil (zero substrings)
	1243  //	 n < 0: all substrings
	1244  func (re *Regexp) Split(s string, n int) []string {
	1245  
	1246  	if n == 0 {
	1247  		return nil
	1248  	}
	1249  
	1250  	if len(re.expr) > 0 && len(s) == 0 {
	1251  		return []string{""}
	1252  	}
	1253  
	1254  	matches := re.FindAllStringIndex(s, n)
	1255  	strings := make([]string, 0, len(matches))
	1256  
	1257  	beg := 0
	1258  	end := 0
	1259  	for _, match := range matches {
	1260  		if n > 0 && len(strings) >= n-1 {
	1261  			break
	1262  		}
	1263  
	1264  		end = match[0]
	1265  		if match[1] != 0 {
	1266  			strings = append(strings, s[beg:end])
	1267  		}
	1268  		beg = match[1]
	1269  	}
	1270  
	1271  	if end != len(s) {
	1272  		strings = append(strings, s[beg:])
	1273  	}
	1274  
	1275  	return strings
	1276  }
	1277  

View as plain text