Source file src/pkg/regexp/onepass.go

     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