backtrack.go

     1  // Copyright 2015 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  // backtrack is a regular expression search with submatch
     6  // tracking for small regular expressions and texts. It allocates
     7  // a bit vector with (length of input) * (length of prog) bits,
     8  // to make sure it never explores the same (character position, instruction)
     9  // state multiple times. This limits the search to run in time linear in
    10  // the length of the test.
    11  //
    12  // backtrack is a fast replacement for the NFA code on small
    13  // regexps when onepass cannot be used.
    14  
    15  package regexp
    16  
    17  import (
    18  	"regexp/syntax"
    19  	"sync"
    20  )
    21  
    22  // A job is an entry on the backtracker's job stack. It holds
    23  // the instruction pc and the position in the input.
    24  type job struct {
    25  	pc  uint32
    26  	arg bool
    27  	pos int
    28  }
    29  
    30  const (
    31  	visitedBits        = 32
    32  	maxBacktrackProg   = 500        // len(prog.Inst) <= max
    33  	maxBacktrackVector = 256 * 1024 // bit vector size <= max (bits)
    34  )
    35  
    36  // bitState holds state for the backtracker.
    37  type bitState struct {
    38  	end      int
    39  	cap      []int
    40  	matchcap []int
    41  	jobs     []job
    42  	visited  []uint32
    43  
    44  	inputs inputs
    45  }
    46  
    47  var bitStatePool sync.Pool
    48  
    49  func newBitState() *bitState {
    50  	b, ok := bitStatePool.Get().(*bitState)
    51  	if !ok {
    52  		b = new(bitState)
    53  	}
    54  	return b
    55  }
    56  
    57  func freeBitState(b *bitState) {
    58  	b.inputs.clear()
    59  	bitStatePool.Put(b)
    60  }
    61  
    62  // maxBitStateLen returns the maximum length of a string to search with
    63  // the backtracker using prog.
    64  func maxBitStateLen(prog *syntax.Prog) int {
    65  	if !shouldBacktrack(prog) {
    66  		return 0
    67  	}
    68  	return maxBacktrackVector / len(prog.Inst)
    69  }
    70  
    71  // shouldBacktrack reports whether the program is too
    72  // long for the backtracker to run.
    73  func shouldBacktrack(prog *syntax.Prog) bool {
    74  	return len(prog.Inst) <= maxBacktrackProg
    75  }
    76  
    77  // reset resets the state of the backtracker.
    78  // end is the end position in the input.
    79  // ncap is the number of captures.
    80  func (b *bitState) reset(prog *syntax.Prog, end int, ncap int) {
    81  	b.end = end
    82  
    83  	if cap(b.jobs) == 0 {
    84  		b.jobs = make([]job, 0, 256)
    85  	} else {
    86  		b.jobs = b.jobs[:0]
    87  	}
    88  
    89  	visitedSize := (len(prog.Inst)*(end+1) + visitedBits - 1) / visitedBits
    90  	if cap(b.visited) < visitedSize {
    91  		b.visited = make([]uint32, visitedSize, maxBacktrackVector/visitedBits)
    92  	} else {
    93  		b.visited = b.visited[:visitedSize]
    94  		for i := range b.visited {
    95  			b.visited[i] = 0
    96  		}
    97  	}
    98  
    99  	if cap(b.cap) < ncap {
   100  		b.cap = make([]int, ncap)
   101  	} else {
   102  		b.cap = b.cap[:ncap]
   103  	}
   104  	for i := range b.cap {
   105  		b.cap[i] = -1
   106  	}
   107  
   108  	if cap(b.matchcap) < ncap {
   109  		b.matchcap = make([]int, ncap)
   110  	} else {
   111  		b.matchcap = b.matchcap[:ncap]
   112  	}
   113  	for i := range b.matchcap {
   114  		b.matchcap[i] = -1
   115  	}
   116  }
   117  
   118  // shouldVisit reports whether the combination of (pc, pos) has not
   119  // been visited yet.
   120  func (b *bitState) shouldVisit(pc uint32, pos int) bool {
   121  	n := uint(int(pc)*(b.end+1) + pos)
   122  	if b.visited[n/visitedBits]&(1<<(n&(visitedBits-1))) != 0 {
   123  		return false
   124  	}
   125  	b.visited[n/visitedBits] |= 1 << (n & (visitedBits - 1))
   126  	return true
   127  }
   128  
   129  // push pushes (pc, pos, arg) onto the job stack if it should be
   130  // visited.
   131  func (b *bitState) push(re *Regexp, pc uint32, pos int, arg bool) {
   132  	// Only check shouldVisit when arg is false.
   133  	// When arg is true, we are continuing a previous visit.
   134  	if re.prog.Inst[pc].Op != syntax.InstFail && (arg || b.shouldVisit(pc, pos)) {
   135  		b.jobs = append(b.jobs, job{pc: pc, arg: arg, pos: pos})
   136  	}
   137  }
   138  
   139  // tryBacktrack runs a backtracking search starting at pos.
   140  func (re *Regexp) tryBacktrack(b *bitState, i input, pc uint32, pos int) bool {
   141  	longest := re.longest
   142  
   143  	b.push(re, pc, pos, false)
   144  	for len(b.jobs) > 0 {
   145  		l := len(b.jobs) - 1
   146  		// Pop job off the stack.
   147  		pc := b.jobs[l].pc
   148  		pos := b.jobs[l].pos
   149  		arg := b.jobs[l].arg
   150  		b.jobs = b.jobs[:l]
   151  
   152  		// Optimization: rather than push and pop,
   153  		// code that is going to Push and continue
   154  		// the loop simply updates ip, p, and arg
   155  		// and jumps to CheckAndLoop. We have to
   156  		// do the ShouldVisit check that Push
   157  		// would have, but we avoid the stack
   158  		// manipulation.
   159  		goto Skip
   160  	CheckAndLoop:
   161  		if !b.shouldVisit(pc, pos) {
   162  			continue
   163  		}
   164  	Skip:
   165  
   166  		inst := re.prog.Inst[pc]
   167  
   168  		switch inst.Op {
   169  		default:
   170  			panic("bad inst")
   171  		case syntax.InstFail:
   172  			panic("unexpected InstFail")
   173  		case syntax.InstAlt:
   174  			// Cannot just
   175  			//   b.push(inst.Out, pos, false)
   176  			//   b.push(inst.Arg, pos, false)
   177  			// If during the processing of inst.Out, we encounter
   178  			// inst.Arg via another path, we want to process it then.
   179  			// Pushing it here will inhibit that. Instead, re-push
   180  			// inst with arg==true as a reminder to push inst.Arg out
   181  			// later.
   182  			if arg {
   183  				// Finished inst.Out; try inst.Arg.
   184  				arg = false
   185  				pc = inst.Arg
   186  				goto CheckAndLoop
   187  			} else {
   188  				b.push(re, pc, pos, true)
   189  				pc = inst.Out
   190  				goto CheckAndLoop
   191  			}
   192  
   193  		case syntax.InstAltMatch:
   194  			// One opcode consumes runes; the other leads to match.
   195  			switch re.prog.Inst[inst.Out].Op {
   196  			case syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
   197  				// inst.Arg is the match.
   198  				b.push(re, inst.Arg, pos, false)
   199  				pc = inst.Arg
   200  				pos = b.end
   201  				goto CheckAndLoop
   202  			}
   203  			// inst.Out is the match - non-greedy
   204  			b.push(re, inst.Out, b.end, false)
   205  			pc = inst.Out
   206  			goto CheckAndLoop
   207  
   208  		case syntax.InstRune:
   209  			r, width := i.step(pos)
   210  			if !inst.MatchRune(r) {
   211  				continue
   212  			}
   213  			pos += width
   214  			pc = inst.Out
   215  			goto CheckAndLoop
   216  
   217  		case syntax.InstRune1:
   218  			r, width := i.step(pos)
   219  			if r != inst.Rune[0] {
   220  				continue
   221  			}
   222  			pos += width
   223  			pc = inst.Out
   224  			goto CheckAndLoop
   225  
   226  		case syntax.InstRuneAnyNotNL:
   227  			r, width := i.step(pos)
   228  			if r == '\n' || r == endOfText {
   229  				continue
   230  			}
   231  			pos += width
   232  			pc = inst.Out
   233  			goto CheckAndLoop
   234  
   235  		case syntax.InstRuneAny:
   236  			r, width := i.step(pos)
   237  			if r == endOfText {
   238  				continue
   239  			}
   240  			pos += width
   241  			pc = inst.Out
   242  			goto CheckAndLoop
   243  
   244  		case syntax.InstCapture:
   245  			if arg {
   246  				// Finished inst.Out; restore the old value.
   247  				b.cap[inst.Arg] = pos
   248  				continue
   249  			} else {
   250  				if inst.Arg < uint32(len(b.cap)) {
   251  					// Capture pos to register, but save old value.
   252  					b.push(re, pc, b.cap[inst.Arg], true) // come back when we're done.
   253  					b.cap[inst.Arg] = pos
   254  				}
   255  				pc = inst.Out
   256  				goto CheckAndLoop
   257  			}
   258  
   259  		case syntax.InstEmptyWidth:
   260  			flag := i.context(pos)
   261  			if !flag.match(syntax.EmptyOp(inst.Arg)) {
   262  				continue
   263  			}
   264  			pc = inst.Out
   265  			goto CheckAndLoop
   266  
   267  		case syntax.InstNop:
   268  			pc = inst.Out
   269  			goto CheckAndLoop
   270  
   271  		case syntax.InstMatch:
   272  			// We found a match. If the caller doesn't care
   273  			// where the match is, no point going further.
   274  			if len(b.cap) == 0 {
   275  				return true
   276  			}
   277  
   278  			// Record best match so far.
   279  			// Only need to check end point, because this entire
   280  			// call is only considering one start position.
   281  			if len(b.cap) > 1 {
   282  				b.cap[1] = pos
   283  			}
   284  			if old := b.matchcap[1]; old == -1 || (longest && pos > 0 && pos > old) {
   285  				copy(b.matchcap, b.cap)
   286  			}
   287  
   288  			// If going for first match, we're done.
   289  			if !longest {
   290  				return true
   291  			}
   292  
   293  			// If we used the entire text, no longer match is possible.
   294  			if pos == b.end {
   295  				return true
   296  			}
   297  
   298  			// Otherwise, continue on in hope of a longer match.
   299  			continue
   300  		}
   301  	}
   302  
   303  	return longest && len(b.matchcap) > 1 && b.matchcap[1] >= 0
   304  }
   305  
   306  // backtrack runs a backtracking search of prog on the input starting at pos.
   307  func (re *Regexp) backtrack(ib []byte, is string, pos int, ncap int, dstCap []int) []int {
   308  	startCond := re.cond
   309  	if startCond == ^syntax.EmptyOp(0) { // impossible
   310  		return nil
   311  	}
   312  	if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
   313  		// Anchored match, past beginning of text.
   314  		return nil
   315  	}
   316  
   317  	b := newBitState()
   318  	i, end := b.inputs.init(nil, ib, is)
   319  	b.reset(re.prog, end, ncap)
   320  
   321  	// Anchored search must start at the beginning of the input
   322  	if startCond&syntax.EmptyBeginText != 0 {
   323  		if len(b.cap) > 0 {
   324  			b.cap[0] = pos
   325  		}
   326  		if !re.tryBacktrack(b, i, uint32(re.prog.Start), pos) {
   327  			freeBitState(b)
   328  			return nil
   329  		}
   330  	} else {
   331  
   332  		// Unanchored search, starting from each possible text position.
   333  		// Notice that we have to try the empty string at the end of
   334  		// the text, so the loop condition is pos <= end, not pos < end.
   335  		// This looks like it's quadratic in the size of the text,
   336  		// but we are not clearing visited between calls to TrySearch,
   337  		// so no work is duplicated and it ends up still being linear.
   338  		width := -1
   339  		for ; pos <= end && width != 0; pos += width {
   340  			if len(re.prefix) > 0 {
   341  				// Match requires literal prefix; fast search for it.
   342  				advance := i.index(re, pos)
   343  				if advance < 0 {
   344  					freeBitState(b)
   345  					return nil
   346  				}
   347  				pos += advance
   348  			}
   349  
   350  			if len(b.cap) > 0 {
   351  				b.cap[0] = pos
   352  			}
   353  			if re.tryBacktrack(b, i, uint32(re.prog.Start), pos) {
   354  				// Match must be leftmost; done.
   355  				goto Match
   356  			}
   357  			_, width = i.step(pos)
   358  		}
   359  		freeBitState(b)
   360  		return nil
   361  	}
   362  
   363  Match:
   364  	dstCap = append(dstCap, b.matchcap...)
   365  	freeBitState(b)
   366  	return dstCap
   367  }
   368
View as plain text