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

View as plain text