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