Source file src/pkg/regexp/syntax/prog.go
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 "bytes" 9 "strconv" 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 // An EmptyOp specifies a kind or mixture of zero-width assertions. 41 type EmptyOp uint8 42 43 const ( 44 EmptyBeginLine EmptyOp = 1 << iota 45 EmptyEndLine 46 EmptyBeginText 47 EmptyEndText 48 EmptyWordBoundary 49 EmptyNoWordBoundary 50 ) 51 52 // EmptyOpContext returns the zero-width assertions 53 // satisfied at the position between the runes r1 and r2. 54 // Passing r1 == -1 indicates that the position is 55 // at the beginning of the text. 56 // Passing r2 == -1 indicates that the position is 57 // at the end of the text. 58 func EmptyOpContext(r1, r2 rune) EmptyOp { 59 var op EmptyOp 60 if r1 < 0 { 61 op |= EmptyBeginText | EmptyBeginLine 62 } 63 if r1 == '\n' { 64 op |= EmptyBeginLine 65 } 66 if r2 < 0 { 67 op |= EmptyEndText | EmptyEndLine 68 } 69 if r2 == '\n' { 70 op |= EmptyEndLine 71 } 72 if IsWordChar(r1) != IsWordChar(r2) { 73 op |= EmptyWordBoundary 74 } else { 75 op |= EmptyNoWordBoundary 76 } 77 return op 78 } 79 80 // IsWordChar reports whether r is consider a ``word character'' 81 // during the evaluation of the \b and \B zero-width assertions. 82 // These assertions are ASCII-only: the word characters are [A-Za-z0-9_]. 83 func IsWordChar(r rune) bool { 84 return 'A' <= r && r <= 'Z' || 'a' <= r && r <= 'z' || '0' <= r && r <= '9' || r == '_' 85 } 86 87 // An Inst is a single instruction in a regular expression program. 88 type Inst struct { 89 Op InstOp 90 Out uint32 // all but InstMatch, InstFail 91 Arg uint32 // InstAlt, InstAltMatch, InstCapture, InstEmptyWidth 92 Rune []rune 93 } 94 95 func (p *Prog) String() string { 96 var b bytes.Buffer 97 dumpProg(&b, p) 98 return b.String() 99 } 100 101 // skipNop follows any no-op or capturing instructions 102 // and returns the resulting pc. 103 func (p *Prog) skipNop(pc uint32) *Inst { 104 i := &p.Inst[pc] 105 for i.Op == InstNop || i.Op == InstCapture { 106 pc = i.Out 107 i = &p.Inst[pc] 108 } 109 return i 110 } 111 112 // op returns i.Op but merges all the Rune special cases into InstRune 113 func (i *Inst) op() InstOp { 114 op := i.Op 115 switch op { 116 case InstRune1, InstRuneAny, InstRuneAnyNotNL: 117 op = InstRune 118 } 119 return op 120 } 121 122 // Prefix returns a literal string that all matches for the 123 // regexp must start with. Complete is true if the prefix 124 // is the entire match. 125 func (p *Prog) Prefix() (prefix string, complete bool) { 126 i := p.skipNop(uint32(p.Start)) 127 128 // Avoid allocation of buffer if prefix is empty. 129 if i.op() != InstRune || len(i.Rune) != 1 { 130 return "", i.Op == InstMatch 131 } 132 133 // Have prefix; gather characters. 134 var buf bytes.Buffer 135 for i.op() == InstRune && len(i.Rune) == 1 && Flags(i.Arg)&FoldCase == 0 { 136 buf.WriteRune(i.Rune[0]) 137 i = p.skipNop(i.Out) 138 } 139 return buf.String(), i.Op == InstMatch 140 } 141 142 // StartCond returns the leading empty-width conditions that must 143 // be true in any match. It returns ^EmptyOp(0) if no matches are possible. 144 func (p *Prog) StartCond() EmptyOp { 145 var flag EmptyOp 146 pc := uint32(p.Start) 147 i := &p.Inst[pc] 148 Loop: 149 for { 150 switch i.Op { 151 case InstEmptyWidth: 152 flag |= EmptyOp(i.Arg) 153 case InstFail: 154 return ^EmptyOp(0) 155 case InstCapture, InstNop: 156 // skip 157 default: 158 break Loop 159 } 160 pc = i.Out 161 i = &p.Inst[pc] 162 } 163 return flag 164 } 165 166 // MatchRune returns true if the instruction matches (and consumes) r. 167 // It should only be called when i.Op == InstRune. 168 func (i *Inst) MatchRune(r rune) bool { 169 rune := i.Rune 170 171 // Special case: single-rune slice is from literal string, not char class. 172 if len(rune) == 1 { 173 r0 := rune[0] 174 if r == r0 { 175 return true 176 } 177 if Flags(i.Arg)&FoldCase != 0 { 178 for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) { 179 if r == r1 { 180 return true 181 } 182 } 183 } 184 return false 185 } 186 187 // Peek at the first few pairs. 188 // Should handle ASCII well. 189 for j := 0; j < len(rune) && j <= 8; j += 2 { 190 if r < rune[j] { 191 return false 192 } 193 if r <= rune[j+1] { 194 return true 195 } 196 } 197 198 // Otherwise binary search. 199 lo := 0 200 hi := len(rune) / 2 201 for lo < hi { 202 m := lo + (hi-lo)/2 203 if c := rune[2*m]; c <= r { 204 if r <= rune[2*m+1] { 205 return true 206 } 207 lo = m + 1 208 } else { 209 hi = m 210 } 211 } 212 return false 213 } 214 215 // As per re2's Prog::IsWordChar. Determines whether rune is an ASCII word char. 216 // Since we act on runes, it would be easy to support Unicode here. 217 func wordRune(r rune) bool { 218 return r == '_' || 219 ('A' <= r && r <= 'Z') || 220 ('a' <= r && r <= 'z') || 221 ('0' <= r && r <= '9') 222 } 223 224 // MatchEmptyWidth returns true if the instruction matches 225 // an empty string between the runes before and after. 226 // It should only be called when i.Op == InstEmptyWidth. 227 func (i *Inst) MatchEmptyWidth(before rune, after rune) bool { 228 switch EmptyOp(i.Arg) { 229 case EmptyBeginLine: 230 return before == '\n' || before == -1 231 case EmptyEndLine: 232 return after == '\n' || after == -1 233 case EmptyBeginText: 234 return before == -1 235 case EmptyEndText: 236 return after == -1 237 case EmptyWordBoundary: 238 return wordRune(before) != wordRune(after) 239 case EmptyNoWordBoundary: 240 return wordRune(before) == wordRune(after) 241 } 242 panic("unknown empty width arg") 243 } 244 245 func (i *Inst) String() string { 246 var b bytes.Buffer 247 dumpInst(&b, i) 248 return b.String() 249 } 250 251 func bw(b *bytes.Buffer, args ...string) { 252 for _, s := range args { 253 b.WriteString(s) 254 } 255 } 256 257 func dumpProg(b *bytes.Buffer, p *Prog) { 258 for j := range p.Inst { 259 i := &p.Inst[j] 260 pc := strconv.Itoa(j) 261 if len(pc) < 3 { 262 b.WriteString(" "[len(pc):]) 263 } 264 if j == p.Start { 265 pc += "*" 266 } 267 bw(b, pc, "\t") 268 dumpInst(b, i) 269 bw(b, "\n") 270 } 271 } 272 273 func u32(i uint32) string { 274 return strconv.FormatUint(uint64(i), 10) 275 } 276 277 func dumpInst(b *bytes.Buffer, i *Inst) { 278 switch i.Op { 279 case InstAlt: 280 bw(b, "alt -> ", u32(i.Out), ", ", u32(i.Arg)) 281 case InstAltMatch: 282 bw(b, "altmatch -> ", u32(i.Out), ", ", u32(i.Arg)) 283 case InstCapture: 284 bw(b, "cap ", u32(i.Arg), " -> ", u32(i.Out)) 285 case InstEmptyWidth: 286 bw(b, "empty ", u32(i.Arg), " -> ", u32(i.Out)) 287 case InstMatch: 288 bw(b, "match") 289 case InstFail: 290 bw(b, "fail") 291 case InstNop: 292 bw(b, "nop -> ", u32(i.Out)) 293 case InstRune: 294 if i.Rune == nil { 295 // shouldn't happen 296 bw(b, "rune <nil>") 297 } 298 bw(b, "rune ", strconv.QuoteToASCII(string(i.Rune))) 299 if Flags(i.Arg)&FoldCase != 0 { 300 bw(b, "/i") 301 } 302 bw(b, " -> ", u32(i.Out)) 303 case InstRune1: 304 bw(b, "rune1 ", strconv.QuoteToASCII(string(i.Rune)), " -> ", u32(i.Out)) 305 case InstRuneAny: 306 bw(b, "any -> ", u32(i.Out)) 307 case InstRuneAnyNotNL: 308 bw(b, "anynotnl -> ", u32(i.Out)) 309 } 310 }