regexp.go 34 KB
Newer Older
1
// Copyright 2009 The Go Authors. All rights reserved.
2 3 4
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

5
// Package regexp implements regular expression search.
6
//
7 8 9
// The syntax of the regular expressions accepted is the same
// general syntax used by Perl, Python, and other languages.
// 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 15 16 17 18 19 20 21
// The regexp implementation provided by this package is
// guaranteed to run in time linear in the size of the input.
// (This is a property not guaranteed by most open source
// implementations of regular expressions.) For more information
// about this property, see
//	http://swtch.com/~rsc/regexp/regexp1.html
// or any book about automata theory.
//
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 28 29
//
//	Find(All)?(String)?(Submatch)?(Index)?
//
// If 'All' is present, the routine matches successive non-overlapping
30 31 32
// matches of the entire expression. Empty matches abutting a preceding
// match are ignored. The return value is a slice containing the successive
// return values of the corresponding non-'All' routine. These routines take
33 34 35 36 37 38 39
// an extra integer argument, n; if n >= 0, the function returns at most n
// matches/submatches.
//
// If 'String' is present, the argument is a string; otherwise it is a slice
// of bytes; return values are adjusted as appropriate.
//
// If 'Submatch' is present, the return value is a slice identifying the
40 41 42 43 44
// successive submatches of the expression. Submatches are matches of
// parenthesized subexpressions (also known as capturing groups) within the
// regular expression, numbered from left to right in order of opening
// parenthesis. Submatch 0 is the match of the entire expression, submatch 1
// the match of the first parenthesized subexpression, and so on.
45 46 47
//
// If 'Index' is present, matches and submatches are identified by byte index
// pairs within the input string: result[2*n:2*n+1] identifies the indexes of
48 49 50
// the nth submatch. The pair for n==0 identifies the match of the entire
// expression. If 'Index' is not present, the match is identified by the
// text of the match/submatch. If an index is negative, it means that
51 52
// subexpression did not match any string in the input.
//
53 54 55 56 57
// There is also a subset of the methods that can be applied to text read
// from a RuneReader:
//
//	MatchReader, FindReaderIndex, FindReaderSubmatchIndex
//
58
// This set may grow. Note that regular expression matches may need to
59 60 61 62
// examine text beyond the text returned by a match, so the methods that
// match text from a RuneReader may read arbitrarily far into the input
// before returning.
//
63 64 65 66 67 68 69
// (There are a few other methods that do not match this pattern.)
//
package regexp

import (
	"bytes"
	"io"
70 71
	"regexp/syntax"
	"strconv"
72
	"strings"
73
	"sync"
74
	"unicode"
75
	"unicode/utf8"
76 77 78
)

// Regexp is the representation of a compiled regular expression.
79
// A Regexp is safe for concurrent use by multiple goroutines.
80
type Regexp struct {
81
	// read-only after Compile
82 83 84 85 86 87 88 89
	regexpRO

	// cache of machines for running regexp
	mu      sync.Mutex
	machine []*machine
}

type regexpRO struct {
90 91
	expr           string         // as passed to Compile
	prog           *syntax.Prog   // compiled program
92
	onepass        *onePassProg   // onepass program or nil
93 94 95
	prefix         string         // required prefix in unanchored matches
	prefixBytes    []byte         // prefix, as a []byte
	prefixComplete bool           // prefix is the entire regexp
96
	prefixRune     rune           // first rune in prefix
97
	prefixEnd      uint32         // pc for last rune in prefix
98 99
	cond           syntax.EmptyOp // empty-width conditions required at start of match
	numSubexp      int
100
	subexpNames    []string
101
	longest        bool
102 103
}

104 105 106 107 108
// String returns the source text used to compile the regular expression.
func (re *Regexp) String() string {
	return re.expr
}

109 110 111 112 113
// Copy returns a new Regexp object copied from re.
//
// When using a Regexp in multiple goroutines, giving each goroutine
// its own copy helps to avoid lock contention.
func (re *Regexp) Copy() *Regexp {
114 115 116 117 118
	// It is not safe to copy Regexp by value
	// since it contains a sync.Mutex.
	return &Regexp{
		regexpRO: re.regexpRO,
	}
119 120
}

121 122 123 124 125 126 127 128 129 130
// Compile parses a regular expression and returns, if successful,
// a Regexp object that can be used to match against text.
//
// When matching against text, the regexp returns a match that
// begins as early as possible in the input (leftmost), and among those
// it chooses the one that a backtracking search would have found first.
// This so-called leftmost-first matching is the same semantics
// that Perl, Python, and other implementations use, although this
// package implements it without the expense of backtracking.
// For POSIX leftmost-longest matching, see CompilePOSIX.
131
func Compile(expr string) (*Regexp, error) {
132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
	return compile(expr, syntax.Perl, false)
}

// CompilePOSIX is like Compile but restricts the regular expression
// to POSIX ERE (egrep) syntax and changes the match semantics to
// leftmost-longest.
//
// That is, when matching against text, the regexp returns a match that
// begins as early as possible in the input (leftmost), and among those
// it chooses a match that is as long as possible.
// This so-called leftmost-longest matching is the same semantics
// that early regular expression implementations used and that POSIX
// specifies.
//
// However, there can be multiple leftmost-longest matches, with different
// submatch choices, and here this package diverges from POSIX.
// Among the possible leftmost-longest matches, this package chooses
// the one that a backtracking search would have found first, while POSIX
// specifies that the match be chosen to maximize the length of the first
// subexpression, then the second, and so on from left to right.
// The POSIX rule is computationally prohibitive and not even well-defined.
// See http://swtch.com/~rsc/regexp/regexp2.html#posix for details.
154
func CompilePOSIX(expr string) (*Regexp, error) {
155 156 157
	return compile(expr, syntax.POSIX, true)
}

158 159 160 161 162 163 164 165
// Longest makes future searches prefer the leftmost-longest match.
// That is, when matching against text, the regexp returns a match that
// begins as early as possible in the input (leftmost), and among those
// it chooses a match that is as long as possible.
func (re *Regexp) Longest() {
	re.longest = true
}

166
func compile(expr string, mode syntax.Flags, longest bool) (*Regexp, error) {
167 168 169 170 171
	re, err := syntax.Parse(expr, mode)
	if err != nil {
		return nil, err
	}
	maxCap := re.MaxCap()
172 173
	capNames := re.CapNames()

174 175 176 177 178 179
	re = re.Simplify()
	prog, err := syntax.Compile(re)
	if err != nil {
		return nil, err
	}
	regexp := &Regexp{
180 181 182 183 184 185 186 187 188
		regexpRO: regexpRO{
			expr:        expr,
			prog:        prog,
			onepass:     compileOnePass(prog),
			numSubexp:   maxCap,
			subexpNames: capNames,
			cond:        prog.StartCond(),
			longest:     longest,
		},
189
	}
190 191 192 193 194
	if regexp.onepass == notOnePass {
		regexp.prefix, regexp.prefixComplete = prog.Prefix()
	} else {
		regexp.prefix, regexp.prefixComplete, regexp.prefixEnd = onePassPrefix(prog)
	}
195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
	if regexp.prefix != "" {
		// TODO(rsc): Remove this allocation by adding
		// IndexString to package bytes.
		regexp.prefixBytes = []byte(regexp.prefix)
		regexp.prefixRune, _ = utf8.DecodeRuneInString(regexp.prefix)
	}
	return regexp, nil
}

// get returns a machine to use for matching re.
// It uses the re's machine cache if possible, to avoid
// unnecessary allocation.
func (re *Regexp) get() *machine {
	re.mu.Lock()
	if n := len(re.machine); n > 0 {
		z := re.machine[n-1]
		re.machine = re.machine[:n-1]
		re.mu.Unlock()
		return z
	}
	re.mu.Unlock()
216
	z := progMachine(re.prog, re.onepass)
217 218 219 220 221 222 223 224 225 226 227 228
	z.re = re
	return z
}

// put returns a machine to the re's machine cache.
// There is no attempt to limit the size of the cache, so it will
// grow to the maximum number of simultaneous matches
// run using re.  (The cache empties when re gets garbage collected.)
func (re *Regexp) put(z *machine) {
	re.mu.Lock()
	re.machine = append(re.machine, z)
	re.mu.Unlock()
229 230 231 232 233 234 235 236
}

// MustCompile is like Compile but panics if the expression cannot be parsed.
// It simplifies safe initialization of global variables holding compiled regular
// expressions.
func MustCompile(str string) *Regexp {
	regexp, error := Compile(str)
	if error != nil {
237
		panic(`regexp: Compile(` + quote(str) + `): ` + error.Error())
238 239 240 241
	}
	return regexp
}

242 243 244 245 246 247
// MustCompilePOSIX is like CompilePOSIX but panics if the expression cannot be parsed.
// It simplifies safe initialization of global variables holding compiled regular
// expressions.
func MustCompilePOSIX(str string) *Regexp {
	regexp, error := CompilePOSIX(str)
	if error != nil {
248
		panic(`regexp: CompilePOSIX(` + quote(str) + `): ` + error.Error())
249
	}
250
	return regexp
251 252
}

253 254 255
func quote(s string) string {
	if strconv.CanBackquote(s) {
		return "`" + s + "`"
256
	}
257
	return strconv.Quote(s)
258 259
}

260 261 262
// NumSubexp returns the number of parenthesized subexpressions in this Regexp.
func (re *Regexp) NumSubexp() int {
	return re.numSubexp
263 264
}

265
// SubexpNames returns the names of the parenthesized subexpressions
266
// in this Regexp. The name for the first sub-expression is names[1],
267 268
// so that if m is a match slice, the name for m[i] is SubexpNames()[i].
// Since the Regexp as a whole cannot be named, names[0] is always
269
// the empty string. The slice should not be modified.
270 271 272 273
func (re *Regexp) SubexpNames() []string {
	return re.subexpNames
}

274
const endOfText rune = -1
275

276 277 278
// input abstracts different representations of the input text. It provides
// one-character lookahead.
type input interface {
279 280
	step(pos int) (r rune, width int) // advance one rune
	canCheckPrefix() bool             // can we look ahead without losing info?
281 282
	hasPrefix(re *Regexp) bool
	index(re *Regexp, pos int) int
283
	context(pos int) syntax.EmptyOp
284 285 286 287 288 289 290
}

// inputString scans a string.
type inputString struct {
	str string
}

291
func (i *inputString) step(pos int) (rune, int) {
292
	if pos < len(i.str) {
293 294
		c := i.str[pos]
		if c < utf8.RuneSelf {
295
			return rune(c), 1
296 297
		}
		return utf8.DecodeRuneInString(i.str[pos:])
298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313
	}
	return endOfText, 0
}

func (i *inputString) canCheckPrefix() bool {
	return true
}

func (i *inputString) hasPrefix(re *Regexp) bool {
	return strings.HasPrefix(i.str, re.prefix)
}

func (i *inputString) index(re *Regexp, pos int) int {
	return strings.Index(i.str[pos:], re.prefix)
}

314
func (i *inputString) context(pos int) syntax.EmptyOp {
315
	r1, r2 := endOfText, endOfText
316 317 318 319 320 321 322 323 324
	if pos > 0 && pos <= len(i.str) {
		r1, _ = utf8.DecodeLastRuneInString(i.str[:pos])
	}
	if pos < len(i.str) {
		r2, _ = utf8.DecodeRuneInString(i.str[pos:])
	}
	return syntax.EmptyOpContext(r1, r2)
}

325 326 327 328 329
// inputBytes scans a byte slice.
type inputBytes struct {
	str []byte
}

330
func (i *inputBytes) step(pos int) (rune, int) {
331
	if pos < len(i.str) {
332 333
		c := i.str[pos]
		if c < utf8.RuneSelf {
334
			return rune(c), 1
335 336
		}
		return utf8.DecodeRune(i.str[pos:])
337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352
	}
	return endOfText, 0
}

func (i *inputBytes) canCheckPrefix() bool {
	return true
}

func (i *inputBytes) hasPrefix(re *Regexp) bool {
	return bytes.HasPrefix(i.str, re.prefixBytes)
}

func (i *inputBytes) index(re *Regexp, pos int) int {
	return bytes.Index(i.str[pos:], re.prefixBytes)
}

353
func (i *inputBytes) context(pos int) syntax.EmptyOp {
354
	r1, r2 := endOfText, endOfText
355 356 357 358 359 360 361 362 363
	if pos > 0 && pos <= len(i.str) {
		r1, _ = utf8.DecodeLastRune(i.str[:pos])
	}
	if pos < len(i.str) {
		r2, _ = utf8.DecodeRune(i.str[pos:])
	}
	return syntax.EmptyOpContext(r1, r2)
}

364 365 366 367 368 369 370
// inputReader scans a RuneReader.
type inputReader struct {
	r     io.RuneReader
	atEOT bool
	pos   int
}

371
func (i *inputReader) step(pos int) (rune, int) {
372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396
	if !i.atEOT && pos != i.pos {
		return endOfText, 0

	}
	r, w, err := i.r.ReadRune()
	if err != nil {
		i.atEOT = true
		return endOfText, 0
	}
	i.pos += w
	return r, w
}

func (i *inputReader) canCheckPrefix() bool {
	return false
}

func (i *inputReader) hasPrefix(re *Regexp) bool {
	return false
}

func (i *inputReader) index(re *Regexp, pos int) int {
	return -1
}

397 398
func (i *inputReader) context(pos int) syntax.EmptyOp {
	return 0
399 400
}

401
// LiteralPrefix returns a literal string that must begin any match
402
// of the regular expression re. It returns the boolean true if the
403 404
// literal string comprises the entire regular expression.
func (re *Regexp) LiteralPrefix() (prefix string, complete bool) {
405
	return re.prefix, re.prefixComplete
406 407
}

408 409
// MatchReader reports whether the Regexp matches the text read by the
// RuneReader.
410
func (re *Regexp) MatchReader(r io.RuneReader) bool {
411
	return re.doMatch(r, nil, "")
412 413
}

414
// MatchString reports whether the Regexp matches the string s.
415
func (re *Regexp) MatchString(s string) bool {
416
	return re.doMatch(nil, nil, s)
417
}
418

419
// Match reports whether the Regexp matches the byte slice b.
420
func (re *Regexp) Match(b []byte) bool {
421
	return re.doMatch(nil, b, "")
422
}
423

424
// MatchReader checks whether a textual regular expression matches the text
425
// read by the RuneReader. More complicated queries need to use Compile and
426
// the full Regexp interface.
427
func MatchReader(pattern string, r io.RuneReader) (matched bool, err error) {
428 429 430 431 432 433
	re, err := Compile(pattern)
	if err != nil {
		return false, err
	}
	return re.MatchReader(r), nil
}
434 435

// MatchString checks whether a textual regular expression
436
// matches a string. More complicated queries need
437
// to use Compile and the full Regexp interface.
438
func MatchString(pattern string, s string) (matched bool, err error) {
439 440 441 442 443 444 445 446
	re, err := Compile(pattern)
	if err != nil {
		return false, err
	}
	return re.MatchString(s), nil
}

// Match checks whether a textual regular expression
447
// matches a byte slice. More complicated queries need
448
// to use Compile and the full Regexp interface.
449
func Match(pattern string, b []byte) (matched bool, err error) {
450 451 452 453 454 455 456
	re, err := Compile(pattern)
	if err != nil {
		return false, err
	}
	return re.Match(b), nil
}

457
// ReplaceAllString returns a copy of src, replacing matches of the Regexp
458
// with the replacement string repl. Inside repl, $ signs are interpreted as
459
// in Expand, so for instance $1 represents the text of the first submatch.
460
func (re *Regexp) ReplaceAllString(src, repl string) string {
461
	n := 2
462
	if strings.Contains(repl, "$") {
463 464 465 466 467 468 469 470
		n = 2 * (re.numSubexp + 1)
	}
	b := re.replaceAll(nil, src, n, func(dst []byte, match []int) []byte {
		return re.expand(dst, repl, nil, src, match)
	})
	return string(b)
}

471
// ReplaceAllLiteralString returns a copy of src, replacing matches of the Regexp
472
// with the replacement string repl. The replacement repl is substituted directly,
473 474 475 476 477
// without using Expand.
func (re *Regexp) ReplaceAllLiteralString(src, repl string) string {
	return string(re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
		return append(dst, repl...)
	}))
478 479
}

480
// ReplaceAllStringFunc returns a copy of src in which all matches of the
481
// Regexp have been replaced by the return value of function repl applied
482
// to the matched substring. The replacement returned by repl is substituted
483
// directly, without using Expand.
484
func (re *Regexp) ReplaceAllStringFunc(src string, repl func(string) string) string {
485 486 487 488 489 490 491
	b := re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
		return append(dst, repl(src[match[0]:match[1]])...)
	})
	return string(b)
}

func (re *Regexp) replaceAll(bsrc []byte, src string, nmatch int, repl func(dst []byte, m []int) []byte) []byte {
492 493
	lastMatchEnd := 0 // end position of the most recent match
	searchPos := 0    // position where we next look for a match
494 495 496 497 498 499 500
	var buf []byte
	var endPos int
	if bsrc != nil {
		endPos = len(bsrc)
	} else {
		endPos = len(src)
	}
501 502 503 504
	if nmatch > re.prog.NumCap {
		nmatch = re.prog.NumCap
	}

505
	var dstCap [2]int
506
	for searchPos <= endPos {
507
		a := re.doExecute(nil, bsrc, src, searchPos, nmatch, dstCap[:0])
508 509 510 511 512
		if len(a) == 0 {
			break // no more matches
		}

		// Copy the unmatched characters before this match.
513 514 515 516 517
		if bsrc != nil {
			buf = append(buf, bsrc[lastMatchEnd:a[0]]...)
		} else {
			buf = append(buf, src[lastMatchEnd:a[0]]...)
		}
518 519 520 521 522 523

		// Now insert a copy of the replacement string, but not for a
		// match of the empty string immediately after another match.
		// (Otherwise, we get double replacement for patterns that
		// match both empty and nonempty strings.)
		if a[1] > lastMatchEnd || a[0] == 0 {
524
			buf = repl(buf, a)
525 526 527 528
		}
		lastMatchEnd = a[1]

		// Advance past this match; always advance at least one character.
529 530 531 532 533 534
		var width int
		if bsrc != nil {
			_, width = utf8.DecodeRune(bsrc[searchPos:])
		} else {
			_, width = utf8.DecodeRuneInString(src[searchPos:])
		}
535 536 537 538
		if searchPos+width > a[1] {
			searchPos += width
		} else if searchPos+1 > a[1] {
			// This clause is only needed at the end of the input
539
			// string. In that case, DecodeRuneInString returns width=0.
540 541 542 543 544 545 546
			searchPos++
		} else {
			searchPos = a[1]
		}
	}

	// Copy the unmatched characters after the last match.
547 548 549 550 551
	if bsrc != nil {
		buf = append(buf, bsrc[lastMatchEnd:]...)
	} else {
		buf = append(buf, src[lastMatchEnd:]...)
	}
552

553
	return buf
554 555
}

556
// ReplaceAll returns a copy of src, replacing matches of the Regexp
557
// with the replacement text repl. Inside repl, $ signs are interpreted as
558
// in Expand, so for instance $1 represents the text of the first submatch.
559
func (re *Regexp) ReplaceAll(src, repl []byte) []byte {
560 561 562 563 564 565 566 567
	n := 2
	if bytes.IndexByte(repl, '$') >= 0 {
		n = 2 * (re.numSubexp + 1)
	}
	srepl := ""
	b := re.replaceAll(src, "", n, func(dst []byte, match []int) []byte {
		if len(srepl) != len(repl) {
			srepl = string(repl)
568
		}
569 570 571 572
		return re.expand(dst, srepl, src, "", match)
	})
	return b
}
573

574
// ReplaceAllLiteral returns a copy of src, replacing matches of the Regexp
575
// with the replacement bytes repl. The replacement repl is substituted directly,
576 577 578 579 580 581
// without using Expand.
func (re *Regexp) ReplaceAllLiteral(src, repl []byte) []byte {
	return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
		return append(dst, repl...)
	})
}
582

583
// ReplaceAllFunc returns a copy of src in which all matches of the
584
// Regexp have been replaced by the return value of function repl applied
585
// to the matched byte slice. The replacement returned by repl is substituted
586 587 588 589 590
// directly, without using Expand.
func (re *Regexp) ReplaceAllFunc(src []byte, repl func([]byte) []byte) []byte {
	return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
		return append(dst, repl(src[match[0]:match[1]])...)
	})
591 592
}

593 594 595 596 597 598
var specialBytes = []byte(`\.+*?()|[]{}^$`)

func special(b byte) bool {
	return bytes.IndexByte(specialBytes, b) >= 0
}

599 600
// QuoteMeta returns a string that quotes all regular expression metacharacters
// inside the argument text; the returned string is a regular expression matching
601
// the literal text. For example, QuoteMeta(`[foo]`) returns `\[foo\]`.
602 603
func QuoteMeta(s string) string {
	// A byte loop is correct because all metacharacters are ASCII.
604 605 606 607 608 609 610 611 612 613 614 615 616 617 618
	var i int
	for i = 0; i < len(s); i++ {
		if special(s[i]) {
			break
		}
	}
	// No meta characters found, so return original string.
	if i >= len(s) {
		return s
	}

	b := make([]byte, 2*len(s)-i)
	copy(b, s[:i])
	j := i
	for ; i < len(s); i++ {
619
		if special(s[i]) {
620 621 622 623 624 625
			b[j] = '\\'
			j++
		}
		b[j] = s[i]
		j++
	}
626
	return string(b[:j])
627 628
}

629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645
// The number of capture values in the program may correspond
// to fewer capturing expressions than are in the regexp.
// For example, "(a){0}" turns into an empty program, so the
// maximum capture in the program is 0 but we need to return
// an expression for \1.  Pad appends -1s to the slice a as needed.
func (re *Regexp) pad(a []int) []int {
	if a == nil {
		// No match.
		return nil
	}
	n := (1 + re.numSubexp) * 2
	for len(a) < n {
		a = append(a, -1)
	}
	return a
}

646 647 648 649 650 651 652 653 654 655
// Find matches in slice b if b is non-nil, otherwise find matches in string s.
func (re *Regexp) allMatches(s string, b []byte, n int, deliver func([]int)) {
	var end int
	if b == nil {
		end = len(s)
	} else {
		end = len(b)
	}

	for pos, i, prevMatchEnd := 0, 0, -1; i < n && pos <= end; {
656
		matches := re.doExecute(nil, b, s, pos, re.prog.NumCap, nil)
657 658 659 660 661 662 663 664 665 666 667 668 669
		if len(matches) == 0 {
			break
		}

		accept := true
		if matches[1] == pos {
			// We've found an empty match.
			if matches[0] == prevMatchEnd {
				// We don't allow an empty match right
				// after a previous match, so ignore it.
				accept = false
			}
			var width int
670
			// TODO: use step()
671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686
			if b == nil {
				_, width = utf8.DecodeRuneInString(s[pos:end])
			} else {
				_, width = utf8.DecodeRune(b[pos:end])
			}
			if width > 0 {
				pos += width
			} else {
				pos = end + 1
			}
		} else {
			pos = matches[1]
		}
		prevMatchEnd = matches[1]

		if accept {
687
			deliver(re.pad(matches))
688 689 690 691 692 693 694 695
			i++
		}
	}
}

// Find returns a slice holding the text of the leftmost match in b of the regular expression.
// A return value of nil indicates no match.
func (re *Regexp) Find(b []byte) []byte {
696 697
	var dstCap [2]int
	a := re.doExecute(nil, b, "", 0, 2, dstCap[:0])
698 699 700 701 702 703 704
	if a == nil {
		return nil
	}
	return b[a[0]:a[1]]
}

// FindIndex returns a two-element slice of integers defining the location of
705
// the leftmost match in b of the regular expression. The match itself is at
706 707 708
// b[loc[0]:loc[1]].
// A return value of nil indicates no match.
func (re *Regexp) FindIndex(b []byte) (loc []int) {
709
	a := re.doExecute(nil, b, "", 0, 2, nil)
710 711 712 713 714 715 716
	if a == nil {
		return nil
	}
	return a[0:2]
}

// FindString returns a string holding the text of the leftmost match in s of the regular
717
// expression. If there is no match, the return value is an empty string,
718
// but it will also be empty if the regular expression successfully matches
719
// an empty string. Use FindStringIndex or FindStringSubmatch if it is
720 721
// necessary to distinguish these cases.
func (re *Regexp) FindString(s string) string {
722 723
	var dstCap [2]int
	a := re.doExecute(nil, nil, s, 0, 2, dstCap[:0])
724 725 726 727 728 729 730
	if a == nil {
		return ""
	}
	return s[a[0]:a[1]]
}

// FindStringIndex returns a two-element slice of integers defining the
731
// location of the leftmost match in s of the regular expression. The match
732 733
// itself is at s[loc[0]:loc[1]].
// A return value of nil indicates no match.
734
func (re *Regexp) FindStringIndex(s string) (loc []int) {
735
	a := re.doExecute(nil, nil, s, 0, 2, nil)
736 737 738 739 740 741 742 743
	if a == nil {
		return nil
	}
	return a[0:2]
}

// FindReaderIndex returns a two-element slice of integers defining the
// location of the leftmost match of the regular expression in text read from
744
// the RuneReader. The match text was found in the input stream at
745 746
// byte offset loc[0] through loc[1]-1.
// A return value of nil indicates no match.
747
func (re *Regexp) FindReaderIndex(r io.RuneReader) (loc []int) {
748
	a := re.doExecute(r, nil, "", 0, 2, nil)
749 750 751 752 753 754 755 756 757 758 759 760
	if a == nil {
		return nil
	}
	return a[0:2]
}

// FindSubmatch returns a slice of slices holding the text of the leftmost
// match of the regular expression in b and the matches, if any, of its
// subexpressions, as defined by the 'Submatch' descriptions in the package
// comment.
// A return value of nil indicates no match.
func (re *Regexp) FindSubmatch(b []byte) [][]byte {
761 762
	var dstCap [4]int
	a := re.doExecute(nil, b, "", 0, re.prog.NumCap, dstCap[:0])
763 764 765
	if a == nil {
		return nil
	}
766
	ret := make([][]byte, 1+re.numSubexp)
767
	for i := range ret {
768
		if 2*i < len(a) && a[2*i] >= 0 {
769 770 771 772 773 774
			ret[i] = b[a[2*i]:a[2*i+1]]
		}
	}
	return ret
}

775 776
// Expand appends template to dst and returns the result; during the
// append, Expand replaces variables in the template with corresponding
777
// matches drawn from src. The match slice should have been returned by
778
// FindSubmatchIndex.
779
//
780 781
// In the template, a variable is denoted by a substring of the form
// $name or ${name}, where name is a non-empty sequence of letters,
782
// digits, and underscores. A purely numeric name like $1 refers to
783
// the submatch with the corresponding index; other names refer to
784
// capturing parentheses named with the (?P<name>...) syntax. A
785
// reference to an out of range or unmatched index or a name that is not
786
// present in the regular expression is replaced with an empty slice.
787
//
788 789
// In the $name form, name is taken to be as long as possible: $1x is
// equivalent to ${1x}, not ${1}x, and, $10 is equivalent to ${10}, not ${1}0.
790
//
791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825
// To insert a literal $ in the output, use $$ in the template.
func (re *Regexp) Expand(dst []byte, template []byte, src []byte, match []int) []byte {
	return re.expand(dst, string(template), src, "", match)
}

// ExpandString is like Expand but the template and source are strings.
// It appends to and returns a byte slice in order to give the calling
// code control over allocation.
func (re *Regexp) ExpandString(dst []byte, template string, src string, match []int) []byte {
	return re.expand(dst, template, nil, src, match)
}

func (re *Regexp) expand(dst []byte, template string, bsrc []byte, src string, match []int) []byte {
	for len(template) > 0 {
		i := strings.Index(template, "$")
		if i < 0 {
			break
		}
		dst = append(dst, template[:i]...)
		template = template[i:]
		if len(template) > 1 && template[1] == '$' {
			// Treat $$ as $.
			dst = append(dst, '$')
			template = template[2:]
			continue
		}
		name, num, rest, ok := extract(template)
		if !ok {
			// Malformed; treat $ as raw text.
			dst = append(dst, '$')
			template = template[1:]
			continue
		}
		template = rest
		if num >= 0 {
826
			if 2*num+1 < len(match) && match[2*num] >= 0 {
827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902
				if bsrc != nil {
					dst = append(dst, bsrc[match[2*num]:match[2*num+1]]...)
				} else {
					dst = append(dst, src[match[2*num]:match[2*num+1]]...)
				}
			}
		} else {
			for i, namei := range re.subexpNames {
				if name == namei && 2*i+1 < len(match) && match[2*i] >= 0 {
					if bsrc != nil {
						dst = append(dst, bsrc[match[2*i]:match[2*i+1]]...)
					} else {
						dst = append(dst, src[match[2*i]:match[2*i+1]]...)
					}
					break
				}
			}
		}
	}
	dst = append(dst, template...)
	return dst
}

// extract returns the name from a leading "$name" or "${name}" in str.
// If it is a number, extract returns num set to that number; otherwise num = -1.
func extract(str string) (name string, num int, rest string, ok bool) {
	if len(str) < 2 || str[0] != '$' {
		return
	}
	brace := false
	if str[1] == '{' {
		brace = true
		str = str[2:]
	} else {
		str = str[1:]
	}
	i := 0
	for i < len(str) {
		rune, size := utf8.DecodeRuneInString(str[i:])
		if !unicode.IsLetter(rune) && !unicode.IsDigit(rune) && rune != '_' {
			break
		}
		i += size
	}
	if i == 0 {
		// empty name is not okay
		return
	}
	name = str[:i]
	if brace {
		if i >= len(str) || str[i] != '}' {
			// missing closing brace
			return
		}
		i++
	}

	// Parse number.
	num = 0
	for i := 0; i < len(name); i++ {
		if name[i] < '0' || '9' < name[i] || num >= 1e8 {
			num = -1
			break
		}
		num = num*10 + int(name[i]) - '0'
	}
	// Disallow leading zeros.
	if name[0] == '0' && len(name) > 1 {
		num = -1
	}

	rest = str[i:]
	ok = true
	return
}

903 904 905 906 907 908
// FindSubmatchIndex returns a slice holding the index pairs identifying the
// leftmost match of the regular expression in b and the matches, if any, of
// its subexpressions, as defined by the 'Submatch' and 'Index' descriptions
// in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindSubmatchIndex(b []byte) []int {
909
	return re.pad(re.doExecute(nil, b, "", 0, re.prog.NumCap, nil))
910 911 912 913 914 915 916 917
}

// FindStringSubmatch returns a slice of strings holding the text of the
// leftmost match of the regular expression in s and the matches, if any, of
// its subexpressions, as defined by the 'Submatch' description in the
// package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindStringSubmatch(s string) []string {
918 919
	var dstCap [4]int
	a := re.doExecute(nil, nil, s, 0, re.prog.NumCap, dstCap[:0])
920 921 922
	if a == nil {
		return nil
	}
923
	ret := make([]string, 1+re.numSubexp)
924
	for i := range ret {
925
		if 2*i < len(a) && a[2*i] >= 0 {
926 927 928 929 930 931 932 933 934 935 936 937
			ret[i] = s[a[2*i]:a[2*i+1]]
		}
	}
	return ret
}

// FindStringSubmatchIndex returns a slice holding the index pairs
// identifying the leftmost match of the regular expression in s and the
// matches, if any, of its subexpressions, as defined by the 'Submatch' and
// 'Index' descriptions in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindStringSubmatchIndex(s string) []int {
938
	return re.pad(re.doExecute(nil, nil, s, 0, re.prog.NumCap, nil))
939 940 941 942 943
}

// FindReaderSubmatchIndex returns a slice holding the index pairs
// identifying the leftmost match of the regular expression of text read by
// the RuneReader, and the matches, if any, of its subexpressions, as defined
944
// by the 'Submatch' and 'Index' descriptions in the package comment. A
945 946
// return value of nil indicates no match.
func (re *Regexp) FindReaderSubmatchIndex(r io.RuneReader) []int {
947
	return re.pad(re.doExecute(r, nil, "", 0, re.prog.NumCap, nil))
948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107
}

const startSize = 10 // The size at which to start a slice in the 'All' routines.

// FindAll is the 'All' version of Find; it returns a slice of all successive
// matches of the expression, as defined by the 'All' description in the
// package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAll(b []byte, n int) [][]byte {
	if n < 0 {
		n = len(b) + 1
	}
	result := make([][]byte, 0, startSize)
	re.allMatches("", b, n, func(match []int) {
		result = append(result, b[match[0]:match[1]])
	})
	if len(result) == 0 {
		return nil
	}
	return result
}

// FindAllIndex is the 'All' version of FindIndex; it returns a slice of all
// successive matches of the expression, as defined by the 'All' description
// in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAllIndex(b []byte, n int) [][]int {
	if n < 0 {
		n = len(b) + 1
	}
	result := make([][]int, 0, startSize)
	re.allMatches("", b, n, func(match []int) {
		result = append(result, match[0:2])
	})
	if len(result) == 0 {
		return nil
	}
	return result
}

// FindAllString is the 'All' version of FindString; it returns a slice of all
// successive matches of the expression, as defined by the 'All' description
// in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAllString(s string, n int) []string {
	if n < 0 {
		n = len(s) + 1
	}
	result := make([]string, 0, startSize)
	re.allMatches(s, nil, n, func(match []int) {
		result = append(result, s[match[0]:match[1]])
	})
	if len(result) == 0 {
		return nil
	}
	return result
}

// FindAllStringIndex is the 'All' version of FindStringIndex; it returns a
// slice of all successive matches of the expression, as defined by the 'All'
// description in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAllStringIndex(s string, n int) [][]int {
	if n < 0 {
		n = len(s) + 1
	}
	result := make([][]int, 0, startSize)
	re.allMatches(s, nil, n, func(match []int) {
		result = append(result, match[0:2])
	})
	if len(result) == 0 {
		return nil
	}
	return result
}

// FindAllSubmatch is the 'All' version of FindSubmatch; it returns a slice
// of all successive matches of the expression, as defined by the 'All'
// description in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAllSubmatch(b []byte, n int) [][][]byte {
	if n < 0 {
		n = len(b) + 1
	}
	result := make([][][]byte, 0, startSize)
	re.allMatches("", b, n, func(match []int) {
		slice := make([][]byte, len(match)/2)
		for j := range slice {
			if match[2*j] >= 0 {
				slice[j] = b[match[2*j]:match[2*j+1]]
			}
		}
		result = append(result, slice)
	})
	if len(result) == 0 {
		return nil
	}
	return result
}

// FindAllSubmatchIndex is the 'All' version of FindSubmatchIndex; it returns
// a slice of all successive matches of the expression, as defined by the
// 'All' description in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAllSubmatchIndex(b []byte, n int) [][]int {
	if n < 0 {
		n = len(b) + 1
	}
	result := make([][]int, 0, startSize)
	re.allMatches("", b, n, func(match []int) {
		result = append(result, match)
	})
	if len(result) == 0 {
		return nil
	}
	return result
}

// FindAllStringSubmatch is the 'All' version of FindStringSubmatch; it
// returns a slice of all successive matches of the expression, as defined by
// the 'All' description in the package comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAllStringSubmatch(s string, n int) [][]string {
	if n < 0 {
		n = len(s) + 1
	}
	result := make([][]string, 0, startSize)
	re.allMatches(s, nil, n, func(match []int) {
		slice := make([]string, len(match)/2)
		for j := range slice {
			if match[2*j] >= 0 {
				slice[j] = s[match[2*j]:match[2*j+1]]
			}
		}
		result = append(result, slice)
	})
	if len(result) == 0 {
		return nil
	}
	return result
}

// FindAllStringSubmatchIndex is the 'All' version of
// FindStringSubmatchIndex; it returns a slice of all successive matches of
// the expression, as defined by the 'All' description in the package
// comment.
// A return value of nil indicates no match.
func (re *Regexp) FindAllStringSubmatchIndex(s string, n int) [][]int {
	if n < 0 {
		n = len(s) + 1
	}
	result := make([][]int, 0, startSize)
	re.allMatches(s, nil, n, func(match []int) {
		result = append(result, match)
	})
	if len(result) == 0 {
		return nil
	}
	return result
}
1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156

// Split slices s into substrings separated by the expression and returns a slice of
// the substrings between those expression matches.
//
// The slice returned by this method consists of all the substrings of s
// not contained in the slice returned by FindAllString. When called on an expression
// that contains no metacharacters, it is equivalent to strings.SplitN.
//
// Example:
//   s := regexp.MustCompile("a*").Split("abaabaccadaaae", 5)
//   // s: ["", "b", "b", "c", "cadaaae"]
//
// The count determines the number of substrings to return:
//   n > 0: at most n substrings; the last substring will be the unsplit remainder.
//   n == 0: the result is nil (zero substrings)
//   n < 0: all substrings
func (re *Regexp) Split(s string, n int) []string {

	if n == 0 {
		return nil
	}

	if len(re.expr) > 0 && len(s) == 0 {
		return []string{""}
	}

	matches := re.FindAllStringIndex(s, n)
	strings := make([]string, 0, len(matches))

	beg := 0
	end := 0
	for _, match := range matches {
		if n > 0 && len(strings) >= n-1 {
			break
		}

		end = match[0]
		if match[1] != 0 {
			strings = append(strings, s[beg:end])
		}
		beg = match[1]
	}

	if end != len(s) {
		strings = append(strings, s[beg:])
	}

	return strings
}