mxregexp.mx raw
1 // Package mxregexp matches a byte string against a regular expression.
2 //
3 // Legacy's -print-allocs takes a Go regexp and matches it against the
4 // function name, so the stage4 compiler needs the same semantics to select
5 // the same functions. Only a boolean answer is needed, which is why the
6 // matcher is a Thompson NFA simulation: it explores every alternative at
7 // once, so greediness and backtracking order cannot change the result and
8 // pathological patterns cannot blow up exponentially.
9 //
10 // Supported: literal bytes, '.', classes '[...]' with ranges, leading '^'
11 // negation and \d \D \w \W \s \S members, the repeats '*', '+', '?' (and
12 // their lazy '?' forms), '|', '(' ')', '^', '$', and a backslash escaping a
13 // metacharacter. Not supported: '{m,n}' repetition, '(?...)' flags and
14 // backreferences - each returns a non-empty error rather than a wrong
15 // answer.
16 //
17 // The parser is a self-mutating type, so its per-iteration scratch is
18 // declared before the loops that use it: a declaration inside a loop body
19 // would allocate in the receiver's sovereign arena once per iteration.
20 package mxregexp
21
22 // Instruction opcodes. Every instruction carries its successor in either
23 // next (single) or a/b (split); opMatch is terminal.
24 const (
25 opChar = int32(iota) // consume one byte equal to ch
26 opAny // consume one byte other than '\n'
27 opClass // consume one byte whose class entry is set
28 opJmp // continue at next
29 opSplit // continue at a, or at b
30 opBol // zero width: only at the start of the text
31 opEol // zero width: only at the end of the text
32 opMatch // accept
33 )
34
35 type inst struct {
36 op int32
37 ch int32 // opChar
38 class []uint8 // opClass: 256 entries, 1 = member
39 next int32 // successor for every single-successor op
40 a int32 // opSplit: preferred branch
41 b int32 // opSplit: alternative branch
42 }
43
44 // patch names a successor field that is still unknown: instruction idx,
45 // field 0 = next, 1 = b.
46 type patch struct {
47 idx int32
48 field int32
49 }
50
51 // frag is a partially built fragment plus the outlets that still need a
52 // successor.
53 type frag struct {
54 start int32
55 outs []patch
56 }
57
58 // program is a compiled pattern: insts with entry point start.
59 type program struct {
60 insts []inst
61 start int32
62 }
63
64 // Match reports whether pattern matches anywhere in s, like Go's
65 // regexp.MatchString. A non-empty err means the pattern uses syntax this
66 // matcher does not implement.
67 func Match(pattern, s string) (ok bool, err string) {
68 pa := &parser{pat: pattern}
69 f := pa.parseAlt()
70 if pa.err != "" {
71 return false, pa.err
72 }
73 if pa.pos != int32(len(pa.pat)) {
74 return false, "unbalanced ')' in pattern"
75 }
76 m := pa.emit(inst{op: opMatch, next: -1, a: -1, b: -1})
77 pa.patchAll(f.outs, m)
78 p := &program{insts: pa.prog, start: f.start}
79 return p.match(s), ""
80 }
81
82 // --- parsing and Thompson construction ---
83
84 type parser struct {
85 pat string
86 pos int32
87 prog []inst
88 err string
89 }
90
91 func (pa *parser) emit(in inst) (idx int32) {
92 pa.prog = ensureInst(pa.prog, 1)
93 idx = int32(len(pa.prog))
94 push(pa.prog, in)
95 return idx
96 }
97
98 // ensureInst is mxutil.Ensure for []inst. Ensure's element type must be
99 // comparable and inst holds a class slice, so the growth is spelled out here.
100 func ensureInst(s []inst, n int32) (r0 []inst) {
101 if n <= 0 || cap(s)-len(s) >= n {
102 return s
103 }
104 nc := cap(s) * 2
105 if nc < 16 {
106 nc = 16
107 }
108 for nc-len(s) < n {
109 nc = nc * 2
110 }
111 nb := []inst{:0:nc}
112 copy(nb[:len(s)], s)
113 return nb[:len(s)]
114 }
115
116 func (pa *parser) patchAll(outs []patch, target int32) {
117 for i := int32(0); i < int32(len(outs)); i++ {
118 if outs[i].field == 0 {
119 pa.prog[outs[i].idx].next = target
120 } else {
121 pa.prog[outs[i].idx].b = target
122 }
123 }
124 }
125
126 func joinPatches(x, y []patch) (r []patch) {
127 r = []patch{:int32(len(x)) + int32(len(y))}
128 for i := int32(0); i < int32(len(x)); i++ {
129 r[i] = x[i]
130 }
131 for i := int32(0); i < int32(len(y)); i++ {
132 r[int32(len(x))+i] = y[i]
133 }
134 return r
135 }
136
137 func (pa *parser) parseAlt() (f frag) {
138 var r frag
139 var sid int32
140 f = pa.parseConcat()
141 for pa.err == "" && pa.pos < int32(len(pa.pat)) && pa.pat[pa.pos] == '|' {
142 pa.pos++
143 r = pa.parseConcat()
144 sid = pa.emit(inst{op: opSplit, ch: -1, next: -1, a: f.start, b: r.start})
145 f = frag{start: sid, outs: joinPatches(f.outs, r.outs)}
146 }
147 return f
148 }
149
150 func (pa *parser) parseConcat() (f frag) {
151 empty := true
152 var ch byte
153 var r frag
154 var sid int32
155 for pa.err == "" && pa.pos < int32(len(pa.pat)) {
156 ch = pa.pat[pa.pos]
157 if ch == '|' || ch == ')' {
158 break
159 }
160 r = pa.parseRepeat()
161 if pa.err != "" {
162 break
163 }
164 if empty {
165 f = r
166 empty = false
167 } else {
168 pa.patchAll(f.outs, r.start)
169 f = frag{start: f.start, outs: r.outs}
170 }
171 }
172 if empty {
173 // An empty branch matches the empty string.
174 sid = pa.emit(inst{op: opJmp, ch: -1, next: -1, a: -1, b: -1})
175 f = frag{start: sid, outs: []patch{{idx: sid, field: 0}}}
176 }
177 return f
178 }
179
180 func (pa *parser) parseRepeat() (f frag) {
181 var ch byte
182 var sid int32
183 f = pa.parseAtom()
184 if pa.err != "" {
185 return f
186 }
187 for pa.pos < int32(len(pa.pat)) {
188 ch = pa.pat[pa.pos]
189 // '{' only begins a repetition when a digit follows; Go treats any
190 // other '{' as an ordinary literal, so "a{" must stay a match for
191 // the text "a{" rather than an error.
192 if ch == '{' && pa.pos+1 < int32(len(pa.pat)) && pa.pat[pa.pos+1] >= '0' && pa.pat[pa.pos+1] <= '9' {
193 pa.err = "'{m,n}' repetition is not supported"
194 return f
195 }
196 if ch != '*' && ch != '+' && ch != '?' {
197 break
198 }
199 pa.pos++
200 // A trailing '?' is the lazy form. Greediness cannot change whether
201 // a match exists, only which one is reported, so it is dropped.
202 if pa.pos < int32(len(pa.pat)) && pa.pat[pa.pos] == '?' {
203 pa.pos++
204 } else if pa.pos < int32(len(pa.pat)) && (pa.pat[pa.pos] == '*' || pa.pat[pa.pos] == '+') {
205 pa.err = "nested repetition operator"
206 return f
207 }
208 sid = pa.emit(inst{op: opSplit, ch: -1, next: -1, a: f.start, b: -1})
209 if ch == '+' {
210 // The loop body is entered once before the split back-edge.
211 pa.patchAll(f.outs, sid)
212 f = frag{start: f.start, outs: []patch{{idx: sid, field: 1}}}
213 continue
214 }
215 if ch == '*' {
216 pa.patchAll(f.outs, sid)
217 f = frag{start: sid, outs: []patch{{idx: sid, field: 1}}}
218 continue
219 }
220 f = frag{start: sid, outs: joinPatches(f.outs, []patch{{idx: sid, field: 1}})}
221 }
222 return f
223 }
224
225 func (pa *parser) parseAtom() (f frag) {
226 var idx int32
227 if pa.pos >= int32(len(pa.pat)) {
228 return frag{start: -1, outs: []patch{}}
229 }
230 ch := pa.pat[pa.pos]
231 switch ch {
232 case '(':
233 pa.pos++
234 if pa.pos < int32(len(pa.pat)) && pa.pat[pa.pos] == '?' {
235 pa.err = "'(?...)' flags are not supported"
236 return frag{start: -1, outs: []patch{}}
237 }
238 inner := pa.parseAlt()
239 if pa.err != "" {
240 return frag{start: -1, outs: []patch{}}
241 }
242 if pa.pos >= int32(len(pa.pat)) || pa.pat[pa.pos] != ')' {
243 pa.err = "missing ')'"
244 return frag{start: -1, outs: []patch{}}
245 }
246 pa.pos++
247 return inner
248 case ')':
249 pa.err = "unbalanced ')' in pattern"
250 return frag{start: -1, outs: []patch{}}
251 case '[':
252 return pa.parseClass()
253 case '.':
254 pa.pos++
255 idx = pa.emit(inst{op: opAny, ch: -1, next: -1, a: -1, b: -1})
256 return frag{start: idx, outs: []patch{{idx: idx, field: 0}}}
257 case '^':
258 pa.pos++
259 idx = pa.emit(inst{op: opBol, ch: -1, next: -1, a: -1, b: -1})
260 return frag{start: idx, outs: []patch{{idx: idx, field: 0}}}
261 case '$':
262 pa.pos++
263 idx = pa.emit(inst{op: opEol, ch: -1, next: -1, a: -1, b: -1})
264 return frag{start: idx, outs: []patch{{idx: idx, field: 0}}}
265 case '*', '+', '?':
266 pa.err = "missing operand before repeat operator"
267 return frag{start: -1, outs: []patch{}}
268 case '\\':
269 return pa.parseEscape()
270 }
271 pa.pos++
272 idx = pa.emit(inst{op: opChar, ch: int32(ch), next: -1, a: -1, b: -1})
273 return frag{start: idx, outs: []patch{{idx: idx, field: 0}}}
274 }
275
276 func (pa *parser) parseEscape() (f frag) {
277 pa.pos++
278 if pa.pos >= int32(len(pa.pat)) {
279 pa.err = "trailing backslash"
280 return frag{start: -1, outs: []patch{}}
281 }
282 ch := pa.pat[pa.pos]
283 pa.pos++
284 switch ch {
285 case 'd':
286 return pa.classFrag(digitClass())
287 case 'D':
288 return pa.classFrag(invertClass(digitClass()))
289 case 'w':
290 return pa.classFrag(wordClass())
291 case 'W':
292 return pa.classFrag(invertClass(wordClass()))
293 case 's':
294 return pa.classFrag(spaceClass())
295 case 'S':
296 return pa.classFrag(invertClass(spaceClass()))
297 case 'n':
298 return pa.literal('\n')
299 case 't':
300 return pa.literal('\t')
301 case 'r':
302 return pa.literal('\r')
303 case 'a':
304 return pa.literal(7)
305 case 'f':
306 return pa.literal('\f')
307 case 'v':
308 return pa.literal(11)
309 case 'b', 'B', 'A', 'z', 'Z', 'p', 'P', 'x', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
310 pa.err = "unsupported escape in pattern"
311 return frag{start: -1, outs: []patch{}}
312 }
313 return pa.literal(ch)
314 }
315
316 func (pa *parser) literal(ch byte) (f frag) {
317 i := pa.emit(inst{op: opChar, ch: int32(ch), next: -1, a: -1, b: -1})
318 return frag{start: i, outs: []patch{{idx: i, field: 0}}}
319 }
320
321 func (pa *parser) classFrag(cls []uint8) (f frag) {
322 i := pa.emit(inst{op: opClass, ch: -1, class: cls, next: -1, a: -1, b: -1})
323 return frag{start: i, outs: []patch{{idx: i, field: 0}}}
324 }
325
326 func (pa *parser) parseClass() (f frag) {
327 pa.pos++ // consume '['
328 cls := []uint8{:256}
329 negated := false
330 var ch byte
331 var ec byte
332 var hi byte
333 var b int32
334 if pa.pos < int32(len(pa.pat)) && pa.pat[pa.pos] == '^' {
335 negated = true
336 pa.pos++
337 }
338 first := true
339 for {
340 if pa.pos >= int32(len(pa.pat)) {
341 pa.err = "missing ']'"
342 return frag{start: -1, outs: []patch{}}
343 }
344 ch = pa.pat[pa.pos]
345 if ch == ']' && !first {
346 pa.pos++
347 break
348 }
349 first = false
350 if ch == '\\' {
351 pa.pos++
352 if pa.pos >= int32(len(pa.pat)) {
353 pa.err = "trailing backslash"
354 return frag{start: -1, outs: []patch{}}
355 }
356 ec = pa.pat[pa.pos]
357 pa.pos++
358 switch ec {
359 case 'd':
360 unionClass(cls, digitClass())
361 case 'D':
362 unionClass(cls, invertClass(digitClass()))
363 case 'w':
364 unionClass(cls, wordClass())
365 case 'W':
366 unionClass(cls, invertClass(wordClass()))
367 case 's':
368 unionClass(cls, spaceClass())
369 case 'S':
370 unionClass(cls, invertClass(spaceClass()))
371 case 'n':
372 cls['\n'] = 1
373 case 't':
374 cls['\t'] = 1
375 case 'r':
376 cls['\r'] = 1
377 case 'a':
378 cls[7] = 1
379 case 'f':
380 cls['\f'] = 1
381 case 'v':
382 cls[11] = 1
383 case 'b':
384 cls[8] = 1 // backspace inside a class
385 case 'A', 'z', 'Z', 'p', 'P', 'x', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
386 pa.err = "unsupported escape in class"
387 return frag{start: -1, outs: []patch{}}
388 default:
389 cls[ec] = 1
390 }
391 continue
392 }
393 pa.pos++
394 if pa.pos+1 < int32(len(pa.pat)) && pa.pat[pa.pos] == '-' && pa.pat[pa.pos+1] != ']' {
395 hi = pa.pat[pa.pos+1]
396 pa.pos += 2
397 if hi < ch {
398 pa.err = "invalid character class range"
399 return frag{start: -1, outs: []patch{}}
400 }
401 b = int32(ch)
402 for b <= int32(hi) {
403 cls[b] = 1
404 b++
405 }
406 continue
407 }
408 cls[ch] = 1
409 }
410 if negated {
411 for b = 0; b < 256; b++ {
412 if cls[b] == 1 {
413 cls[b] = 0
414 } else {
415 cls[b] = 1
416 }
417 }
418 }
419 return pa.classFrag(cls)
420 }
421
422 func digitClass() (c []uint8) {
423 c = []uint8{:256}
424 for b := int32('0'); b <= int32('9'); b++ {
425 c[b] = 1
426 }
427 return c
428 }
429
430 func wordClass() (c []uint8) {
431 c = []uint8{:256}
432 for b := int32('0'); b <= int32('9'); b++ {
433 c[b] = 1
434 }
435 for b := int32('A'); b <= int32('Z'); b++ {
436 c[b] = 1
437 }
438 for b := int32('a'); b <= int32('z'); b++ {
439 c[b] = 1
440 }
441 c['_'] = 1
442 return c
443 }
444
445 // spaceClass is Go's \s: [\t\n\f\r ].
446 func spaceClass() (c []uint8) {
447 c = []uint8{:256}
448 c['\t'] = 1
449 c['\n'] = 1
450 c['\f'] = 1
451 c['\r'] = 1
452 c[' '] = 1
453 return c
454 }
455
456 func unionClass(dst, src []uint8) {
457 for i := int32(0); i < 256; i++ {
458 if src[i] == 1 {
459 dst[i] = 1
460 }
461 }
462 }
463
464 func invertClass(src []uint8) (c []uint8) {
465 c = []uint8{:256}
466 for i := int32(0); i < 256; i++ {
467 if src[i] != 1 {
468 c[i] = 1
469 }
470 }
471 return c
472 }
473
474 // --- simulation ---
475
476 type vm struct {
477 p *program
478 s string
479 seen []int32
480 stack []int32
481 }
482
483 // match simulates the program over s. Threads are seeded at every position,
484 // which makes the search unanchored. seen is stamped per batch rather than
485 // cleared, so a state is entered at most once per position and a loop that
486 // consumes nothing terminates.
487 func (p *program) match(s string) (ok bool) {
488 n := int32(len(p.insts))
489 v := &vm{p: p, s: s, seen: []int32{:n}, stack: []int32{:n}}
490 for i := int32(0); i < n; i++ {
491 v.seen[i] = -1
492 }
493 clist := []int32{:n}
494 nlist := []int32{:n}
495 clen := int32(0)
496 nlen := int32(0)
497 gen := int32(0)
498 textLen := int32(len(s))
499 for pos := int32(0); ; pos++ {
500 gen++
501 clen = v.add(clist, clen, p.start, pos, gen)
502 for i := int32(0); i < clen; i++ {
503 if p.insts[clist[i]].op == opMatch {
504 return true
505 }
506 }
507 if pos >= textLen {
508 break
509 }
510 gen++
511 nlen = 0
512 c := s[pos]
513 for i := int32(0); i < clen; i++ {
514 in := p.insts[clist[i]]
515 consumed := false
516 switch in.op {
517 case opChar:
518 consumed = int32(c) == in.ch
519 case opAny:
520 consumed = c != '\n'
521 case opClass:
522 consumed = in.class[c] == 1
523 }
524 if consumed {
525 nlen = v.add(nlist, nlen, in.next, pos+1, gen)
526 }
527 }
528 clist, nlist = nlist, clist
529 clen, nlen = nlen, 0
530 }
531 return false
532 }
533
534 // add follows pc through every zero-width instruction reachable without
535 // consuming input, appending the resulting consuming-or-accepting states to
536 // list from index len0 and returning the new length. States are marked in
537 // seen on push, so the DFS stack never exceeds one entry per instruction.
538 func (v *vm) add(list []int32, len0, pc, pos, gen int32) (out int32) {
539 sp := int32(0)
540 var cur int32
541 var in inst
542 v.seen[pc] = gen
543 v.stack[sp] = pc
544 sp++
545 for sp > 0 {
546 sp--
547 cur = v.stack[sp]
548 in = v.p.insts[cur]
549 switch in.op {
550 case opJmp:
551 if v.seen[in.next] != gen {
552 v.seen[in.next] = gen
553 v.stack[sp] = in.next
554 sp++
555 }
556 case opSplit:
557 if v.seen[in.a] != gen {
558 v.seen[in.a] = gen
559 v.stack[sp] = in.a
560 sp++
561 }
562 if v.seen[in.b] != gen {
563 v.seen[in.b] = gen
564 v.stack[sp] = in.b
565 sp++
566 }
567 case opBol:
568 if pos == 0 && v.seen[in.next] != gen {
569 v.seen[in.next] = gen
570 v.stack[sp] = in.next
571 sp++
572 }
573 case opEol:
574 if pos == int32(len(v.s)) && v.seen[in.next] != gen {
575 v.seen[in.next] = gen
576 v.stack[sp] = in.next
577 sp++
578 }
579 default:
580 list[len0] = cur
581 len0++
582 }
583 }
584 return len0
585 }
586