onepass.go

Documentation: regexp

     1  // Copyright 2014 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
     6  
     7  import (
     8  	"regexp/syntax"
     9  	"sort"
    10  	"strings"
    11  	"unicode"
    12  )
    13  
    14  // "One-pass" regexp execution.
    15  // Some regexps can be analyzed to determine that they never need
    16  // backtracking: they are guaranteed to run in one pass over the string
    17  // without bothering to save all the usual NFA state.
    18  // Detect those and execute them more quickly.
    19  
    20  // A onePassProg is a compiled one-pass regular expression program.
    21  // It is the same as syntax.Prog except for the use of onePassInst.
    22  type onePassProg struct {
    23  	Inst   []onePassInst
    24  	Start  int // index of start instruction
    25  	NumCap int // number of InstCapture insts in re
    26  }
    27  
    28  // A onePassInst is a single instruction in a one-pass regular expression program.
    29  // It is the same as syntax.Inst except for the new 'Next' field.
    30  type onePassInst struct {
    31  	syntax.Inst
    32  	Next []uint32
    33  }
    34  
    35  // OnePassPrefix returns a literal string that all matches for the
    36  // regexp must start with. Complete is true if the prefix
    37  // is the entire match. Pc is the index of the last rune instruction
    38  // in the string. The OnePassPrefix skips over the mandatory
    39  // EmptyBeginText
    40  func onePassPrefix(p *syntax.Prog) (prefix string, complete bool, pc uint32) {
    41  	i := &p.Inst[p.Start]
    42  	if i.Op != syntax.InstEmptyWidth || (syntax.EmptyOp(i.Arg))&syntax.EmptyBeginText == 0 {
    43  		return "", i.Op == syntax.InstMatch, uint32(p.Start)
    44  	}
    45  	pc = i.Out
    46  	i = &p.Inst[pc]
    47  	for i.Op == syntax.InstNop {
    48  		pc = i.Out
    49  		i = &p.Inst[pc]
    50  	}
    51  	// Avoid allocation of buffer if prefix is empty.
    52  	if iop(i) != syntax.InstRune || len(i.Rune) != 1 {
    53  		return "", i.Op == syntax.InstMatch, uint32(p.Start)
    54  	}
    55  
    56  	// Have prefix; gather characters.
    57  	var buf strings.Builder
    58  	for iop(i) == syntax.InstRune && len(i.Rune) == 1 && syntax.Flags(i.Arg)&syntax.FoldCase == 0 {
    59  		buf.WriteRune(i.Rune[0])
    60  		pc, i = i.Out, &p.Inst[i.Out]
    61  	}
    62  	if i.Op == syntax.InstEmptyWidth &&
    63  		syntax.EmptyOp(i.Arg)&syntax.EmptyEndText != 0 &&
    64  		p.Inst[i.Out].Op == syntax.InstMatch {
    65  		complete = true
    66  	}
    67  	return buf.String(), complete, pc
    68  }
    69  
    70  // OnePassNext selects the next actionable state of the prog, based on the input character.
    71  // It should only be called when i.Op == InstAlt or InstAltMatch, and from the one-pass machine.
    72  // One of the alternates may ultimately lead without input to end of line. If the instruction
    73  // is InstAltMatch the path to the InstMatch is in i.Out, the normal node in i.Next.
    74  func onePassNext(i *onePassInst, r rune) uint32 {
    75  	next := i.MatchRunePos(r)
    76  	if next >= 0 {
    77  		return i.Next[next]
    78  	}
    79  	if i.Op == syntax.InstAltMatch {
    80  		return i.Out
    81  	}
    82  	return 0
    83  }
    84  
    85  func iop(i *syntax.Inst) syntax.InstOp {
    86  	op := i.Op
    87  	switch op {
    88  	case syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
    89  		op = syntax.InstRune
    90  	}
    91  	return op
    92  }
    93  
    94  // Sparse Array implementation is used as a queueOnePass.
    95  type queueOnePass struct {
    96  	sparse          []uint32
    97  	dense           []uint32
    98  	size, nextIndex uint32
    99  }
   100  
   101  func (q *queueOnePass) empty() bool {
   102  	return q.nextIndex >= q.size
   103  }
   104  
   105  func (q *queueOnePass) next() (n uint32) {
   106  	n = q.dense[q.nextIndex]
   107  	q.nextIndex++
   108  	return
   109  }
   110  
   111  func (q *queueOnePass) clear() {
   112  	q.size = 0
   113  	q.nextIndex = 0
   114  }
   115  
   116  func (q *queueOnePass) contains(u uint32) bool {
   117  	if u >= uint32(len(q.sparse)) {
   118  		return false
   119  	}
   120  	return q.sparse[u] < q.size && q.dense[q.sparse[u]] == u
   121  }
   122  
   123  func (q *queueOnePass) insert(u uint32) {
   124  	if !q.contains(u) {
   125  		q.insertNew(u)
   126  	}
   127  }
   128  
   129  func (q *queueOnePass) insertNew(u uint32) {
   130  	if u >= uint32(len(q.sparse)) {
   131  		return
   132  	}
   133  	q.sparse[u] = q.size
   134  	q.dense[q.size] = u
   135  	q.size++
   136  }
   137  
   138  func newQueue(size int) (q *queueOnePass) {
   139  	return &queueOnePass{
   140  		sparse: make([]uint32, size),
   141  		dense:  make([]uint32, size),
   142  	}
   143  }
   144  
   145  // mergeRuneSets merges two non-intersecting runesets, and returns the merged result,
   146  // and a NextIp array. The idea is that if a rune matches the OnePassRunes at index
   147  // i, NextIp[i/2] is the target. If the input sets intersect, an empty runeset and a
   148  // NextIp array with the single element mergeFailed is returned.
   149  // The code assumes that both inputs contain ordered and non-intersecting rune pairs.
   150  const mergeFailed = uint32(0xffffffff)
   151  
   152  var (
   153  	noRune = []rune{}
   154  	noNext = []uint32{mergeFailed}
   155  )
   156  
   157  func mergeRuneSets(leftRunes, rightRunes *[]rune, leftPC, rightPC uint32) ([]rune, []uint32) {
   158  	leftLen := len(*leftRunes)
   159  	rightLen := len(*rightRunes)
   160  	if leftLen&0x1 != 0 || rightLen&0x1 != 0 {
   161  		panic("mergeRuneSets odd length []rune")
   162  	}
   163  	var (
   164  		lx, rx int
   165  	)
   166  	merged := make([]rune, 0)
   167  	next := make([]uint32, 0)
   168  	ok := true
   169  	defer func() {
   170  		if !ok {
   171  			merged = nil
   172  			next = nil
   173  		}
   174  	}()
   175  
   176  	ix := -1
   177  	extend := func(newLow *int, newArray *[]rune, pc uint32) bool {
   178  		if ix > 0 && (*newArray)[*newLow] <= merged[ix] {
   179  			return false
   180  		}
   181  		merged = append(merged, (*newArray)[*newLow], (*newArray)[*newLow+1])
   182  		*newLow += 2
   183  		ix += 2
   184  		next = append(next, pc)
   185  		return true
   186  	}
   187  
   188  	for lx < leftLen || rx < rightLen {
   189  		switch {
   190  		case rx >= rightLen:
   191  			ok = extend(&lx, leftRunes, leftPC)
   192  		case lx >= leftLen:
   193  			ok = extend(&rx, rightRunes, rightPC)
   194  		case (*rightRunes)[rx] < (*leftRunes)[lx]:
   195  			ok = extend(&rx, rightRunes, rightPC)
   196  		default:
   197  			ok = extend(&lx, leftRunes, leftPC)
   198  		}
   199  		if !ok {
   200  			return noRune, noNext
   201  		}
   202  	}
   203  	return merged, next
   204  }
   205  
   206  // cleanupOnePass drops working memory, and restores certain shortcut instructions.
   207  func cleanupOnePass(prog *onePassProg, original *syntax.Prog) {
   208  	for ix, instOriginal := range original.Inst {
   209  		switch instOriginal.Op {
   210  		case syntax.InstAlt, syntax.InstAltMatch, syntax.InstRune:
   211  		case syntax.InstCapture, syntax.InstEmptyWidth, syntax.InstNop, syntax.InstMatch, syntax.InstFail:
   212  			prog.Inst[ix].Next = nil
   213  		case syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
   214  			prog.Inst[ix].Next = nil
   215  			prog.Inst[ix] = onePassInst{Inst: instOriginal}
   216  		}
   217  	}
   218  }
   219  
   220  // onePassCopy creates a copy of the original Prog, as we'll be modifying it
   221  func onePassCopy(prog *syntax.Prog) *onePassProg {
   222  	p := &onePassProg{
   223  		Start:  prog.Start,
   224  		NumCap: prog.NumCap,
   225  		Inst:   make([]onePassInst, len(prog.Inst)),
   226  	}
   227  	for i, inst := range prog.Inst {
   228  		p.Inst[i] = onePassInst{Inst: inst}
   229  	}
   230  
   231  	// rewrites one or more common Prog constructs that enable some otherwise
   232  	// non-onepass Progs to be onepass. A:BD (for example) means an InstAlt at
   233  	// ip A, that points to ips B & C.
   234  	// A:BC + B:DA => A:BC + B:CD
   235  	// A:BC + B:DC => A:DC + B:DC
   236  	for pc := range p.Inst {
   237  		switch p.Inst[pc].Op {
   238  		default:
   239  			continue
   240  		case syntax.InstAlt, syntax.InstAltMatch:
   241  			// A:Bx + B:Ay
   242  			p_A_Other := &p.Inst[pc].Out
   243  			p_A_Alt := &p.Inst[pc].Arg
   244  			// make sure a target is another Alt
   245  			instAlt := p.Inst[*p_A_Alt]
   246  			if !(instAlt.Op == syntax.InstAlt || instAlt.Op == syntax.InstAltMatch) {
   247  				p_A_Alt, p_A_Other = p_A_Other, p_A_Alt
   248  				instAlt = p.Inst[*p_A_Alt]
   249  				if !(instAlt.Op == syntax.InstAlt || instAlt.Op == syntax.InstAltMatch) {
   250  					continue
   251  				}
   252  			}
   253  			instOther := p.Inst[*p_A_Other]
   254  			// Analyzing both legs pointing to Alts is for another day
   255  			if instOther.Op == syntax.InstAlt || instOther.Op == syntax.InstAltMatch {
   256  				// too complicated
   257  				continue
   258  			}
   259  			// simple empty transition loop
   260  			// A:BC + B:DA => A:BC + B:DC
   261  			p_B_Alt := &p.Inst[*p_A_Alt].Out
   262  			p_B_Other := &p.Inst[*p_A_Alt].Arg
   263  			patch := false
   264  			if instAlt.Out == uint32(pc) {
   265  				patch = true
   266  			} else if instAlt.Arg == uint32(pc) {
   267  				patch = true
   268  				p_B_Alt, p_B_Other = p_B_Other, p_B_Alt
   269  			}
   270  			if patch {
   271  				*p_B_Alt = *p_A_Other
   272  			}
   273  
   274  			// empty transition to common target
   275  			// A:BC + B:DC => A:DC + B:DC
   276  			if *p_A_Other == *p_B_Alt {
   277  				*p_A_Alt = *p_B_Other
   278  			}
   279  		}
   280  	}
   281  	return p
   282  }
   283  
   284  // runeSlice exists to permit sorting the case-folded rune sets.
   285  type runeSlice []rune
   286  
   287  func (p runeSlice) Len() int           { return len(p) }
   288  func (p runeSlice) Less(i, j int) bool { return p[i] < p[j] }
   289  func (p runeSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
   290  
   291  var anyRuneNotNL = []rune{0, '\n' - 1, '\n' + 1, unicode.MaxRune}
   292  var anyRune = []rune{0, unicode.MaxRune}
   293  
   294  // makeOnePass creates a onepass Prog, if possible. It is possible if at any alt,
   295  // the match engine can always tell which branch to take. The routine may modify
   296  // p if it is turned into a onepass Prog. If it isn't possible for this to be a
   297  // onepass Prog, the Prog nil is returned. makeOnePass is recursive
   298  // to the size of the Prog.
   299  func makeOnePass(p *onePassProg) *onePassProg {
   300  	// If the machine is very long, it's not worth the time to check if we can use one pass.
   301  	if len(p.Inst) >= 1000 {
   302  		return nil
   303  	}
   304  
   305  	var (
   306  		instQueue    = newQueue(len(p.Inst))
   307  		visitQueue   = newQueue(len(p.Inst))
   308  		check        func(uint32, []bool) bool
   309  		onePassRunes = make([][]rune, len(p.Inst))
   310  	)
   311  
   312  	// check that paths from Alt instructions are unambiguous, and rebuild the new
   313  	// program as a onepass program
   314  	check = func(pc uint32, m []bool) (ok bool) {
   315  		ok = true
   316  		inst := &p.Inst[pc]
   317  		if visitQueue.contains(pc) {
   318  			return
   319  		}
   320  		visitQueue.insert(pc)
   321  		switch inst.Op {
   322  		case syntax.InstAlt, syntax.InstAltMatch:
   323  			ok = check(inst.Out, m) && check(inst.Arg, m)
   324  			// check no-input paths to InstMatch
   325  			matchOut := m[inst.Out]
   326  			matchArg := m[inst.Arg]
   327  			if matchOut && matchArg {
   328  				ok = false
   329  				break
   330  			}
   331  			// Match on empty goes in inst.Out
   332  			if matchArg {
   333  				inst.Out, inst.Arg = inst.Arg, inst.Out
   334  				matchOut, matchArg = matchArg, matchOut
   335  			}
   336  			if matchOut {
   337  				m[pc] = true
   338  				inst.Op = syntax.InstAltMatch
   339  			}
   340  
   341  			// build a dispatch operator from the two legs of the alt.
   342  			onePassRunes[pc], inst.Next = mergeRuneSets(
   343  				&onePassRunes[inst.Out], &onePassRunes[inst.Arg], inst.Out, inst.Arg)
   344  			if len(inst.Next) > 0 && inst.Next[0] == mergeFailed {
   345  				ok = false
   346  				break
   347  			}
   348  		case syntax.InstCapture, syntax.InstNop:
   349  			ok = check(inst.Out, m)
   350  			m[pc] = m[inst.Out]
   351  			// pass matching runes back through these no-ops.
   352  			onePassRunes[pc] = append([]rune{}, onePassRunes[inst.Out]...)
   353  			inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
   354  			for i := range inst.Next {
   355  				inst.Next[i] = inst.Out
   356  			}
   357  		case syntax.InstEmptyWidth:
   358  			ok = check(inst.Out, m)
   359  			m[pc] = m[inst.Out]
   360  			onePassRunes[pc] = append([]rune{}, onePassRunes[inst.Out]...)
   361  			inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
   362  			for i := range inst.Next {
   363  				inst.Next[i] = inst.Out
   364  			}
   365  		case syntax.InstMatch, syntax.InstFail:
   366  			m[pc] = inst.Op == syntax.InstMatch
   367  		case syntax.InstRune:
   368  			m[pc] = false
   369  			if len(inst.Next) > 0 {
   370  				break
   371  			}
   372  			instQueue.insert(inst.Out)
   373  			if len(inst.Rune) == 0 {
   374  				onePassRunes[pc] = []rune{}
   375  				inst.Next = []uint32{inst.Out}
   376  				break
   377  			}
   378  			runes := make([]rune, 0)
   379  			if len(inst.Rune) == 1 && syntax.Flags(inst.Arg)&syntax.FoldCase != 0 {
   380  				r0 := inst.Rune[0]
   381  				runes = append(runes, r0, r0)
   382  				for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) {
   383  					runes = append(runes, r1, r1)
   384  				}
   385  				sort.Sort(runeSlice(runes))
   386  			} else {
   387  				runes = append(runes, inst.Rune...)
   388  			}
   389  			onePassRunes[pc] = runes
   390  			inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
   391  			for i := range inst.Next {
   392  				inst.Next[i] = inst.Out
   393  			}
   394  			inst.Op = syntax.InstRune
   395  		case syntax.InstRune1:
   396  			m[pc] = false
   397  			if len(inst.Next) > 0 {
   398  				break
   399  			}
   400  			instQueue.insert(inst.Out)
   401  			runes := []rune{}
   402  			// expand case-folded runes
   403  			if syntax.Flags(inst.Arg)&syntax.FoldCase != 0 {
   404  				r0 := inst.Rune[0]
   405  				runes = append(runes, r0, r0)
   406  				for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) {
   407  					runes = append(runes, r1, r1)
   408  				}
   409  				sort.Sort(runeSlice(runes))
   410  			} else {
   411  				runes = append(runes, inst.Rune[0], inst.Rune[0])
   412  			}
   413  			onePassRunes[pc] = runes
   414  			inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
   415  			for i := range inst.Next {
   416  				inst.Next[i] = inst.Out
   417  			}
   418  			inst.Op = syntax.InstRune
   419  		case syntax.InstRuneAny:
   420  			m[pc] = false
   421  			if len(inst.Next) > 0 {
   422  				break
   423  			}
   424  			instQueue.insert(inst.Out)
   425  			onePassRunes[pc] = append([]rune{}, anyRune...)
   426  			inst.Next = []uint32{inst.Out}
   427  		case syntax.InstRuneAnyNotNL:
   428  			m[pc] = false
   429  			if len(inst.Next) > 0 {
   430  				break
   431  			}
   432  			instQueue.insert(inst.Out)
   433  			onePassRunes[pc] = append([]rune{}, anyRuneNotNL...)
   434  			inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
   435  			for i := range inst.Next {
   436  				inst.Next[i] = inst.Out
   437  			}
   438  		}
   439  		return
   440  	}
   441  
   442  	instQueue.clear()
   443  	instQueue.insert(uint32(p.Start))
   444  	m := make([]bool, len(p.Inst))
   445  	for !instQueue.empty() {
   446  		visitQueue.clear()
   447  		pc := instQueue.next()
   448  		if !check(pc, m) {
   449  			p = nil
   450  			break
   451  		}
   452  	}
   453  	if p != nil {
   454  		for i := range p.Inst {
   455  			p.Inst[i].Rune = onePassRunes[i]
   456  		}
   457  	}
   458  	return p
   459  }
   460  
   461  // compileOnePass returns a new *syntax.Prog suitable for onePass execution if the original Prog
   462  // can be recharacterized as a one-pass regexp program, or syntax.nil if the
   463  // Prog cannot be converted. For a one pass prog, the fundamental condition that must
   464  // be true is: at any InstAlt, there must be no ambiguity about what branch to  take.
   465  func compileOnePass(prog *syntax.Prog) (p *onePassProg) {
   466  	if prog.Start == 0 {
   467  		return nil
   468  	}
   469  	// onepass regexp is anchored
   470  	if prog.Inst[prog.Start].Op != syntax.InstEmptyWidth ||
   471  		syntax.EmptyOp(prog.Inst[prog.Start].Arg)&syntax.EmptyBeginText != syntax.EmptyBeginText {
   472  		return nil
   473  	}
   474  	// every instruction leading to InstMatch must be EmptyEndText
   475  	for _, inst := range prog.Inst {
   476  		opOut := prog.Inst[inst.Out].Op
   477  		switch inst.Op {
   478  		default:
   479  			if opOut == syntax.InstMatch {
   480  				return nil
   481  			}
   482  		case syntax.InstAlt, syntax.InstAltMatch:
   483  			if opOut == syntax.InstMatch || prog.Inst[inst.Arg].Op == syntax.InstMatch {
   484  				return nil
   485  			}
   486  		case syntax.InstEmptyWidth:
   487  			if opOut == syntax.InstMatch {
   488  				if syntax.EmptyOp(inst.Arg)&syntax.EmptyEndText == syntax.EmptyEndText {
   489  					continue
   490  				}
   491  				return nil
   492  			}
   493  		}
   494  	}
   495  	// Creates a slightly optimized copy of the original Prog
   496  	// that cleans up some Prog idioms that block valid onepass programs
   497  	p = onePassCopy(prog)
   498  
   499  	// checkAmbiguity on InstAlts, build onepass Prog if possible
   500  	p = makeOnePass(p)
   501  
   502  	if p != nil {
   503  		cleanupOnePass(p, prog)
   504  	}
   505  	return p
   506  }
   507
View as plain text