Black Lives Matter. Support the Equal Justice Initiative.

Source file src/regexp/syntax/prog.go

Documentation: regexp/syntax

     1  // Copyright 2011 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 syntax
     6  
     7  import (
     8  	"strconv"
     9  	"strings"
    10  	"unicode"
    11  )
    12  
    13  // Compiled program.
    14  // May not belong in this package, but convenient for now.
    15  
    16  // A Prog is a compiled regular expression program.
    17  type Prog struct {
    18  	Inst   []Inst
    19  	Start  int // index of start instruction
    20  	NumCap int // number of InstCapture insts in re
    21  }
    22  
    23  // An InstOp is an instruction opcode.
    24  type InstOp uint8
    25  
    26  const (
    27  	InstAlt InstOp = iota
    28  	InstAltMatch
    29  	InstCapture
    30  	InstEmptyWidth
    31  	InstMatch
    32  	InstFail
    33  	InstNop
    34  	InstRune
    35  	InstRune1
    36  	InstRuneAny
    37  	InstRuneAnyNotNL
    38  )
    39  
    40  var instOpNames = []string{
    41  	"InstAlt",
    42  	"InstAltMatch",
    43  	"InstCapture",
    44  	"InstEmptyWidth",
    45  	"InstMatch",
    46  	"InstFail",
    47  	"InstNop",
    48  	"InstRune",
    49  	"InstRune1",
    50  	"InstRuneAny",
    51  	"InstRuneAnyNotNL",
    52  }
    53  
    54  func (i InstOp) String() string {
    55  	if uint(i) >= uint(len(instOpNames)) {
    56  		return ""
    57  	}
    58  	return instOpNames[i]
    59  }
    60  
    61  // An EmptyOp specifies a kind or mixture of zero-width assertions.
    62  type EmptyOp uint8
    63  
    64  const (
    65  	EmptyBeginLine EmptyOp = 1 << iota
    66  	EmptyEndLine
    67  	EmptyBeginText
    68  	EmptyEndText
    69  	EmptyWordBoundary
    70  	EmptyNoWordBoundary
    71  )
    72  
    73  // EmptyOpContext returns the zero-width assertions
    74  // satisfied at the position between the runes r1 and r2.
    75  // Passing r1 == -1 indicates that the position is
    76  // at the beginning of the text.
    77  // Passing r2 == -1 indicates that the position is
    78  // at the end of the text.
    79  func EmptyOpContext(r1, r2 rune) EmptyOp {
    80  	var op EmptyOp = EmptyNoWordBoundary
    81  	var boundary byte
    82  	switch {
    83  	case IsWordChar(r1):
    84  		boundary = 1
    85  	case r1 == '\n':
    86  		op |= EmptyBeginLine
    87  	case r1 < 0:
    88  		op |= EmptyBeginText | EmptyBeginLine
    89  	}
    90  	switch {
    91  	case IsWordChar(r2):
    92  		boundary ^= 1
    93  	case r2 == '\n':
    94  		op |= EmptyEndLine
    95  	case r2 < 0:
    96  		op |= EmptyEndText | EmptyEndLine
    97  	}
    98  	if boundary != 0 { // IsWordChar(r1) != IsWordChar(r2)
    99  		op ^= (EmptyWordBoundary | EmptyNoWordBoundary)
   100  	}
   101  	return op
   102  }
   103  
   104  // IsWordChar reports whether r is consider a ``word character''
   105  // during the evaluation of the \b and \B zero-width assertions.
   106  // These assertions are ASCII-only: the word characters are [A-Za-z0-9_].
   107  func IsWordChar(r rune) bool {
   108  	return 'A' <= r && r <= 'Z' || 'a' <= r && r <= 'z' || '0' <= r && r <= '9' || r == '_'
   109  }
   110  
   111  // An Inst is a single instruction in a regular expression program.
   112  type Inst struct {
   113  	Op   InstOp
   114  	Out  uint32 // all but InstMatch, InstFail
   115  	Arg  uint32 // InstAlt, InstAltMatch, InstCapture, InstEmptyWidth
   116  	Rune []rune
   117  }
   118  
   119  func (p *Prog) String() string {
   120  	var b strings.Builder
   121  	dumpProg(&b, p)
   122  	return b.String()
   123  }
   124  
   125  // skipNop follows any no-op or capturing instructions.
   126  func (p *Prog) skipNop(pc uint32) *Inst {
   127  	i := &p.Inst[pc]
   128  	for i.Op == InstNop || i.Op == InstCapture {
   129  		i = &p.Inst[i.Out]
   130  	}
   131  	return i
   132  }
   133  
   134  // op returns i.Op but merges all the Rune special cases into InstRune
   135  func (i *Inst) op() InstOp {
   136  	op := i.Op
   137  	switch op {
   138  	case InstRune1, InstRuneAny, InstRuneAnyNotNL:
   139  		op = InstRune
   140  	}
   141  	return op
   142  }
   143  
   144  // Prefix returns a literal string that all matches for the
   145  // regexp must start with. Complete is true if the prefix
   146  // is the entire match.
   147  func (p *Prog) Prefix() (prefix string, complete bool) {
   148  	i := p.skipNop(uint32(p.Start))
   149  
   150  	// Avoid allocation of buffer if prefix is empty.
   151  	if i.op() != InstRune || len(i.Rune) != 1 {
   152  		return "", i.Op == InstMatch
   153  	}
   154  
   155  	// Have prefix; gather characters.
   156  	var buf strings.Builder
   157  	for i.op() == InstRune && len(i.Rune) == 1 && Flags(i.Arg)&FoldCase == 0 {
   158  		buf.WriteRune(i.Rune[0])
   159  		i = p.skipNop(i.Out)
   160  	}
   161  	return buf.String(), i.Op == InstMatch
   162  }
   163  
   164  // StartCond returns the leading empty-width conditions that must
   165  // be true in any match. It returns ^EmptyOp(0) if no matches are possible.
   166  func (p *Prog) StartCond() EmptyOp {
   167  	var flag EmptyOp
   168  	pc := uint32(p.Start)
   169  	i := &p.Inst[pc]
   170  Loop:
   171  	for {
   172  		switch i.Op {
   173  		case InstEmptyWidth:
   174  			flag |= EmptyOp(i.Arg)
   175  		case InstFail:
   176  			return ^EmptyOp(0)
   177  		case InstCapture, InstNop:
   178  			// skip
   179  		default:
   180  			break Loop
   181  		}
   182  		pc = i.Out
   183  		i = &p.Inst[pc]
   184  	}
   185  	return flag
   186  }
   187  
   188  const noMatch = -1
   189  
   190  // MatchRune reports whether the instruction matches (and consumes) r.
   191  // It should only be called when i.Op == InstRune.
   192  func (i *Inst) MatchRune(r rune) bool {
   193  	return i.MatchRunePos(r) != noMatch
   194  }
   195  
   196  // MatchRunePos checks whether the instruction matches (and consumes) r.
   197  // If so, MatchRunePos returns the index of the matching rune pair
   198  // (or, when len(i.Rune) == 1, rune singleton).
   199  // If not, MatchRunePos returns -1.
   200  // MatchRunePos should only be called when i.Op == InstRune.
   201  func (i *Inst) MatchRunePos(r rune) int {
   202  	rune := i.Rune
   203  
   204  	switch len(rune) {
   205  	case 0:
   206  		return noMatch
   207  
   208  	case 1:
   209  		// Special case: single-rune slice is from literal string, not char class.
   210  		r0 := rune[0]
   211  		if r == r0 {
   212  			return 0
   213  		}
   214  		if Flags(i.Arg)&FoldCase != 0 {
   215  			for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) {
   216  				if r == r1 {
   217  					return 0
   218  				}
   219  			}
   220  		}
   221  		return noMatch
   222  
   223  	case 2:
   224  		if r >= rune[0] && r <= rune[1] {
   225  			return 0
   226  		}
   227  		return noMatch
   228  
   229  	case 4, 6, 8:
   230  		// Linear search for a few pairs.
   231  		// Should handle ASCII well.
   232  		for j := 0; j < len(rune); j += 2 {
   233  			if r < rune[j] {
   234  				return noMatch
   235  			}
   236  			if r <= rune[j+1] {
   237  				return j / 2
   238  			}
   239  		}
   240  		return noMatch
   241  	}
   242  
   243  	// Otherwise binary search.
   244  	lo := 0
   245  	hi := len(rune) / 2
   246  	for lo < hi {
   247  		m := lo + (hi-lo)/2
   248  		if c := rune[2*m]; c <= r {
   249  			if r <= rune[2*m+1] {
   250  				return m
   251  			}
   252  			lo = m + 1
   253  		} else {
   254  			hi = m
   255  		}
   256  	}
   257  	return noMatch
   258  }
   259  
   260  // MatchEmptyWidth reports whether the instruction matches
   261  // an empty string between the runes before and after.
   262  // It should only be called when i.Op == InstEmptyWidth.
   263  func (i *Inst) MatchEmptyWidth(before rune, after rune) bool {
   264  	switch EmptyOp(i.Arg) {
   265  	case EmptyBeginLine:
   266  		return before == '\n' || before == -1
   267  	case EmptyEndLine:
   268  		return after == '\n' || after == -1
   269  	case EmptyBeginText:
   270  		return before == -1
   271  	case EmptyEndText:
   272  		return after == -1
   273  	case EmptyWordBoundary:
   274  		return IsWordChar(before) != IsWordChar(after)
   275  	case EmptyNoWordBoundary:
   276  		return IsWordChar(before) == IsWordChar(after)
   277  	}
   278  	panic("unknown empty width arg")
   279  }
   280  
   281  func (i *Inst) String() string {
   282  	var b strings.Builder
   283  	dumpInst(&b, i)
   284  	return b.String()
   285  }
   286  
   287  func bw(b *strings.Builder, args ...string) {
   288  	for _, s := range args {
   289  		b.WriteString(s)
   290  	}
   291  }
   292  
   293  func dumpProg(b *strings.Builder, p *Prog) {
   294  	for j := range p.Inst {
   295  		i := &p.Inst[j]
   296  		pc := strconv.Itoa(j)
   297  		if len(pc) < 3 {
   298  			b.WriteString("   "[len(pc):])
   299  		}
   300  		if j == p.Start {
   301  			pc += "*"
   302  		}
   303  		bw(b, pc, "\t")
   304  		dumpInst(b, i)
   305  		bw(b, "\n")
   306  	}
   307  }
   308  
   309  func u32(i uint32) string {
   310  	return strconv.FormatUint(uint64(i), 10)
   311  }
   312  
   313  func dumpInst(b *strings.Builder, i *Inst) {
   314  	switch i.Op {
   315  	case InstAlt:
   316  		bw(b, "alt -> ", u32(i.Out), ", ", u32(i.Arg))
   317  	case InstAltMatch:
   318  		bw(b, "altmatch -> ", u32(i.Out), ", ", u32(i.Arg))
   319  	case InstCapture:
   320  		bw(b, "cap ", u32(i.Arg), " -> ", u32(i.Out))
   321  	case InstEmptyWidth:
   322  		bw(b, "empty ", u32(i.Arg), " -> ", u32(i.Out))
   323  	case InstMatch:
   324  		bw(b, "match")
   325  	case InstFail:
   326  		bw(b, "fail")
   327  	case InstNop:
   328  		bw(b, "nop -> ", u32(i.Out))
   329  	case InstRune:
   330  		if i.Rune == nil {
   331  			// shouldn't happen
   332  			bw(b, "rune <nil>")
   333  		}
   334  		bw(b, "rune ", strconv.QuoteToASCII(string(i.Rune)))
   335  		if Flags(i.Arg)&FoldCase != 0 {
   336  			bw(b, "/i")
   337  		}
   338  		bw(b, " -> ", u32(i.Out))
   339  	case InstRune1:
   340  		bw(b, "rune1 ", strconv.QuoteToASCII(string(i.Rune)), " -> ", u32(i.Out))
   341  	case InstRuneAny:
   342  		bw(b, "any -> ", u32(i.Out))
   343  	case InstRuneAnyNotNL:
   344  		bw(b, "anynotnl -> ", u32(i.Out))
   345  	}
   346  }
   347  

View as plain text