...
Run Format

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

View as plain text