Source file src/regexp/regexp.go

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

View as plain text