1# regexp - regular expressions, in the shape of Go's regexp package.2#3# The pattern is parsed into a tree, compiled into a small program and run by4# a Pike VM: a Thompson NFA simulation carrying the capture slots along. Every5# thread advances one character at a time and there is at most one thread per6# instruction, so matching takes O(len(text) * len(program)) whatever the7# pattern, with none of the exponential blowups of a backtracking engine.8#9# Supported syntax:10#11# . any character, a newline too under the s flag12# [abc] class, with ranges and negation as [^a-z]13# [[:alpha:]] POSIX class, [[:^alpha:]] to negate it14# \d \w \s digit, word and space classes, uppercase to negate15# \b \B word boundary16# ^ $ beginning and end of the text, of the line under m17# \A \z beginning and end of the text, whatever the flags18# x* x+ x? repetition, append ? for the lazy form19# x{n,m} counted repetition, {n} and {n,} too20# (x) capturing group, (?:x) plain group21# (?P<n>x) named group, (?<n>x) spells the same thing22# (?i) (?i:x) flags, i m s U, until the group ends or for x alone23# \Q...\E literal text, whatever punctuation it holds24# \n \x7f \177 escapes, by name, by hexadecimal, by octal25# a|b alternation26#27# The text is walked one byte at a time, so a pattern speaks of bytes and not28# of runes: . matches a byte and a range like [α-ω] means nothing.2930io = import("io")3132# --- syntax tree ---3334nEmpty = 035nChar = 136nAny = 237nClass = 338nSeq = 439nAlt = 540nRepeat = 641nGroup = 742nBegin = 843nEnd = 944nWordB = 1045nNoWordB = 114647node = fn(t) {48 n = new()49 n.t = t50 return n51}5253isDigit = fn(c) { c >= "0" && c <= "9" }54isWord = fn(c) { isDigit(c) || (c >= "a" && c <= "z") || (c >= "A" && c <= "Z") || c == "_" }55isOctal = fn(c) { c >= "0" && c <= "7" }56isHex = fn(c) { isDigit(c) || (c >= "a" && c <= "f") || (c >= "A" && c <= "F") }5758# code and char turn a byte into its number and back. A string holds no zero59# byte, so 1 is the lowest character there is and the classes start there.60code = fn(c) { bytes(c)[0] }61char = fn(n) { string(bytes([n])) }6263lowest = char(1)64highest = char(255)6566toLower = fn(c) { if c >= "A" && c <= "Z" { char(code(c) + 32) } else { c } }67toUpper = fn(c) { if c >= "a" && c <= "z" { char(code(c) - 32) } else { c } }6869# A class is a list of [lo, hi] ranges plus the negation flag.70classOf = fn(ranges, negated) {71 n = node(nClass)72 n.ranges = ranges73 n.negated = negated74 return n75}7677# complement returns the ranges that the given ones leave out. A negated class78# nested in another one, as the D of [\D.] or the ^ of [[:^space:]], has no79# negation flag of its own to carry, so it is turned inside out instead.80complement = fn(ranges) {81 inside = []82 for i = 0; i < 256; ++i {83 inside = append(inside, false)84 }8586 for i = 0; i < len(ranges); ++i {87 for c = code(ranges[i][0]); c <= code(ranges[i][1]); ++c {88 inside[c] = true89 }90 }9192 out = []93 lo = -19495 for c = 1; c < 256; ++c {96 if !inside[c] && lo == -1 {97 lo = c98 } else if inside[c] && lo != -1 {99 out = append(out, [char(lo), char(c - 1)])100 lo = -1101 }102 }103104 if lo != -1 {105 out = append(out, [char(lo), highest])106 }107 return out108}109110# fold widens the ranges so that a letter matches in either case, which is111# what the i flag asks for. A negated class is folded before it is negated,112# so that [^a] under i turns down A as well.113fold = fn(ranges) {114 out = ranges115116 for i = 0; i < len(ranges); ++i {117 lo = ranges[i][0]118 hi = ranges[i][1]119120 a = if lo > "a" { lo } else { "a" }121 b = if hi < "z" { hi } else { "z" }122 if a <= b {123 out = append(out, [toUpper(a), toUpper(b)])124 }125126 a = if lo > "A" { lo } else { "A" }127 b = if hi < "Z" { hi } else { "Z" }128 if a <= b {129 out = append(out, [toLower(a), toLower(b)])130 }131 }132133 return out134}135136# The POSIX classes, spelled [[:name:]] inside a class.137posixClasses = new()138posixClasses.alnum = [["0", "9"], ["A", "Z"], ["a", "z"]]139posixClasses.alpha = [["A", "Z"], ["a", "z"]]140posixClasses.ascii = [[lowest, char(127)]]141posixClasses.blank = [["\t", "\t"], [" ", " "]]142posixClasses.cntrl = [[lowest, char(31)], [char(127), char(127)]]143posixClasses.digit = [["0", "9"]]144posixClasses.graph = [[char(33), char(126)]]145posixClasses.lower = [["a", "z"]]146posixClasses.print = [[char(32), char(126)]]147posixClasses.punct = [[char(33), char(47)], [char(58), char(64)], [char(91), char(96)], [char(123), char(126)]]148posixClasses.space = [["\t", "\r"], [" ", " "]]149posixClasses.upper = [["A", "Z"]]150posixClasses.word = [["0", "9"], ["A", "Z"], ["_", "_"], ["a", "z"]]151posixClasses.xdigit = [["0", "9"], ["A", "F"], ["a", "f"]]152153# escapeClass returns the class an escape stands for, or null.154escapeClass = fn(c) {155 spaces = [[" ", " "], ["\t", "\t"], ["\n", "\n"], ["\r", "\r"], ["\v", "\v"], ["\f", "\f"]]156 words = [["a", "z"], ["A", "Z"], ["0", "9"], ["_", "_"]]157158 if c == "d" { return classOf([["0", "9"]], false) }159 if c == "D" { return classOf([["0", "9"]], true) }160 if c == "w" { return classOf(words, false) }161 if c == "W" { return classOf(words, true) }162 if c == "s" { return classOf(spaces, false) }163 if c == "S" { return classOf(spaces, true) }164 return null165}166167# escapeChar returns the character an escape by name stands for, or null when168# the escape is not one of them.169escapeChar = fn(c) {170 if c == "a" { return "\a" }171 if c == "n" { return "\n" }172 if c == "t" { return "\t" }173 if c == "r" { return "\r" }174 if c == "v" { return "\v" }175 if c == "f" { return "\f" }176 return null177}178179# --- parser ---180#181# The grammar, lowest precedence first:182#183# alt := seq ("|" seq)*184# seq := repeat*185# repeat := atom ("*" | "+" | "?" | "{n,m}") "?"?186# atom := "(" alt ")" | "[" class "]" | "." | "^" | "$" | escape | char187#188# The flags are held by the parser and not by the tree: (?i) is a word said189# once and obeyed until the enclosing group ends, so the parser remembers it190# and every node it builds afterwards is born already folded.191192newFlags = fn() {193 f = new()194 f.i = false195 f.m = false196 f.s = false197 f.ungreedy = false198 return f199}200201copyFlags = fn(f) {202 g = new()203 g.i = f.i204 g.m = f.m205 g.s = f.s206 g.ungreedy = f.ungreedy207 return g208}209210parser = fn(pattern, posix) {211 p = new()212 p.src = pattern213 p.i = 0214 p.ngroups = 0215 p.posix = posix216 p.names = [""]217 p.flags = newFlags()218219 p.done = fn() { p.i >= len(p.src) }220 p.peek = fn() { if p.done() { "" } else { p.src[p.i] } }221 p.next = fn() {222 c = p.peek()223 ++p.i224 return c225 }226227 p.at = fn(k) { if p.i + k < len(p.src) { p.src[p.i + k] } else { "" } }228229 # perlOnly turns down the escapes and the groups that POSIX does not know,230 # the way CompilePOSIX promises a plain ERE and nothing more.231 p.perlOnly = fn(what) {232 if p.posix {233 return error("regexp: {what} is not POSIX ERE syntax")234 }235 return null236 }237238 # parseNumber reads a run of digits in the given base, at most n of them.239 p.parseNumber = fn(base, n, isdigit) {240 v = 0241 k = 0242243 for k < n && !p.done() && isdigit(p.peek()) {244 d = p.next()245 v = v * base + if isDigit(d) {246 code(d) - code("0")247 } else {248 code(toLower(d)) - code("a") + 10249 }250 ++k251 }252253 return if k == 0 { null } else { v }254 }255256 # escapeLiteral returns the character an escape stands for, once the class257 # escapes and the assertions have had their turn. An unknown escape of a258 # letter or a digit is an error, as it is in Go: it is room left for the259 # escapes yet to be given a meaning.260 p.escapeLiteral = fn(esc) {261 named = escapeChar(esc)262 if named != null {263 return named264 }265266 if esc == "x" {267 if p.peek() == `{` {268 p.next()269 v = p.parseNumber(16, 8, isHex)270 if v == null || p.peek() != `}` {271 return error("regexp: invalid hexadecimal escape")272 }273 p.next()274 if v < 1 || v > 255 {275 return error("regexp: hexadecimal escape out of the byte range")276 }277 return char(v)278 }279280 v = p.parseNumber(16, 2, isHex)281 if v == null {282 return error("regexp: invalid escape sequence \\x")283 }284 if v == 0 {285 return error("regexp: no string holds the zero byte")286 }287 return char(v)288 }289290 # \0 opens an octal escape, \1 to \7 only when a second digit follows:291 # a lone one would be a backreference and no NFA can honour it.292 if isOctal(esc) {293 if esc != "0" && !isOctal(p.peek()) {294 return error("regexp: backreferences are not supported")295 }296 --p.i297 v = p.parseNumber(8, 3, isOctal)298 if v == 0 {299 return error("regexp: no string holds the zero byte")300 }301 return char(v)302 }303304 if isWord(esc) {305 return error("regexp: invalid escape sequence \\{esc}")306 }307 return esc308 }309310 # parsePosix reads the [:name:] that stands inside a class, having seen311 # the opening [ of it, and returns the ranges it names.312 p.parsePosix = fn() {313 p.next()314 p.next()315316 neg = false317 if p.peek() == "^" {318 neg = true319 p.next()320 }321322 name = ""323 for !p.done() && p.peek() != ":" {324 name = name + p.next()325 }326 if p.at(0) != ":" || p.at(1) != "]" {327 return error("regexp: missing closing :] in [:{name}:]")328 }329 p.next()330 p.next()331332 ranges = posixClasses[name]333 if ranges == null {334 return error("regexp: unknown POSIX class [:{name}:]")335 }336 return if neg { complement(ranges) } else { ranges }337 }338339 p.parseClass = fn() {340 negated = false341 if p.peek() == "^" {342 negated = true343 p.next()344 }345346 ranges = []347 first = true348349 # A ] right at the start is a literal one, as in Go.350 for !p.done() && (p.peek() != "]" || first) {351 first = false352353 if p.peek() == "[" && p.at(1) == ":" {354 if failed(posix = p.parsePosix()) {355 return posix356 }357 for k = 0; k < len(posix); ++k {358 ranges = append(ranges, posix[k])359 }360 continue361 }362363 c = p.next()364365 if c == "\\" && !p.done() {366 esc = p.next()367 cls = escapeClass(esc)368369 if cls != null {370 if failed(err = p.perlOnly("\\{esc}")) {371 return err372 }373 # A negated class inside a class keeps no flag of its own,374 # so it goes in turned inside out.375 sub = if cls.negated { complement(cls.ranges) } else { cls.ranges }376 for k = 0; k < len(sub); ++k {377 ranges = append(ranges, sub[k])378 }379 continue380 }381382 if failed(c = p.escapeLiteral(esc)) {383 return c384 }385 }386387 if p.peek() == "-" && p.at(1) != "]" && p.at(1) != "" {388 p.next()389 hi = p.next()390 if hi == "\\" && !p.done() {391 if failed(hi = p.escapeLiteral(p.next())) {392 return hi393 }394 }395 if hi < c {396 return error("regexp: invalid character range {c}-{hi}")397 }398 ranges = append(ranges, [c, hi])399 } else {400 ranges = append(ranges, [c, c])401 }402 }403404 if p.done() {405 return error("regexp: missing closing ]")406 }407 p.next()408409 if len(ranges) == 0 {410 return error("regexp: empty character class")411 }412 if p.flags.i {413 ranges = fold(ranges)414 }415 return classOf(ranges, negated)416 }417418 # parseCount reads {n}, {n,} and {n,m}. It tells apart a brace that opens419 # no count at all, which is a literal brace and gives null, from a count420 # that is written wrong, which is an error.421 p.parseCount = fn() {422 digits = ""423 for !p.done() && isDigit(p.peek()) {424 digits = digits + p.next()425 }426 if len(digits) == 0 {427 return null428 }429430 out = new()431 out.min = int(digits)432 out.max = out.min433434 if p.peek() == "," {435 p.next()436 digits = ""437 for !p.done() && isDigit(p.peek()) {438 digits = digits + p.next()439 }440 out.max = if len(digits) == 0 { -1 } else { int(digits) }441 }442443 if p.peek() != `}` {444 return null445 }446 p.next()447448 if out.max != -1 && out.max < out.min {449 return error("regexp: invalid repetition count")450 }451 return out452 }453454 # charNode makes the node for a plain character. Under the i flag the455 # letter becomes the class of its two cases, so that nothing downstream456 # has to know about folding.457 p.charNode = fn(ch) {458 if p.flags.i {459 lo = toLower(ch)460 up = toUpper(ch)461 if lo != up {462 return classOf([[lo, lo], [up, up]], false)463 }464 }465466 n = node(nChar)467 n.ch = ch468 return n469 }470471 p.anyNode = fn() {472 n = node(nAny)473 n.nl = p.flags.s474 return n475 }476477 # setFlags reads the letters of a (?imsU-imsU) and turns them on or off.478 p.setFlags = fn() {479 neg = false480 seen = false481482 for !p.done() {483 c = p.peek()484 if c == ")" || c == ":" {485 if !seen {486 return error("regexp: missing argument to (?)")487 }488 return null489 }490491 p.next()492 if c == "-" {493 if neg {494 return error("regexp: invalid flags")495 }496 neg = true497 continue498 }499500 on = !neg501 if c == "i" {502 p.flags.i = on503 } else if c == "m" {504 p.flags.m = on505 } else if c == "s" {506 p.flags.s = on507 } else if c == "U" {508 p.flags.ungreedy = on509 } else {510 return error("regexp: unknown flag {c}")511 }512 seen = true513 }514515 return error("regexp: missing closing )")516 }517518 # parseName reads the name of a (?P<name>x) up to its closing angle.519 p.parseName = fn() {520 name = ""521 for !p.done() && p.peek() != ">" {522 c = p.next()523 if !isWord(c) {524 return error("regexp: invalid named capture group")525 }526 name = name + c527 }528529 if p.done() {530 return error("regexp: missing closing > in a named group")531 }532 p.next()533534 if len(name) == 0 {535 return error("regexp: a capture group cannot have an empty name")536 }537 for k = 0; k < len(p.names); ++k {538 if p.names[k] == name {539 return error("regexp: duplicate capture group name {name}")540 }541 }542 return name543 }544545 # parseGroup reads what follows an open parenthesis. The flags in force546 # are saved and given back at the closing one, so that a (?i) said inside547 # a group is forgotten outside of it.548 p.parseGroup = fn() {549 capturing = true550 name = ""551 saved = copyFlags(p.flags)552553 if p.peek() == "?" {554 if failed(err = p.perlOnly("(?")) {555 return err556 }557 p.next()558559 c = p.peek()560 if c == ":" {561 p.next()562 capturing = false563 } else if c == "P" || c == "<" {564 if c == "P" {565 p.next()566 if p.peek() == "=" {567 return error("regexp: backreferences are not supported")568 }569 if p.peek() != "<" {570 return error("regexp: invalid named capture group")571 }572 }573 p.next()574 if failed(name = p.parseName()) {575 return name576 }577 } else {578 # A (?flags) group holds nothing and matches nothing: it only579 # leaves the flags changed behind it.580 if failed(err = p.setFlags()) {581 return err582 }583 if p.next() == ")" {584 return node(nEmpty)585 }586 capturing = false587 }588 }589590 index = 0591 if capturing {592 ++p.ngroups593 index = p.ngroups594 p.names = append(p.names, name)595 }596597 if failed(inner = p.parseAlt()) {598 return inner599 }600 if p.peek() != ")" {601 return error("regexp: missing closing )")602 }603 p.next()604 p.flags = saved605606 n = node(nGroup)607 n.sub = inner608 n.index = index609 return n610 }611612 p.parseAtom = fn() {613 c = p.next()614615 if c == "(" { return p.parseGroup() }616 if c == "[" { return p.parseClass() }617 if c == "." { return p.anyNode() }618619 if c == "^" || c == "$" {620 n = node(if c == "^" { nBegin } else { nEnd })621 n.line = p.flags.m622 return n623 }624625 if c == "\\" {626 if p.done() {627 return error("regexp: trailing backslash")628 }629630 esc = p.next()631 if esc == "b" || esc == "B" || esc == "A" || esc == "z" {632 if failed(err = p.perlOnly("\\{esc}")) {633 return err634 }635 if esc == "b" { return node(nWordB) }636 if esc == "B" { return node(nNoWordB) }637638 n = node(if esc == "A" { nBegin } else { nEnd })639 n.line = false640 return n641 }642643 cls = escapeClass(esc)644 if cls != null {645 if failed(err = p.perlOnly("\\{esc}")) {646 return err647 }648 return cls649 }650651 if failed(ch = p.escapeLiteral(esc)) {652 return ch653 }654 return p.charNode(ch)655 }656657 if c == ")" {658 return error("regexp: unexpected )")659 }660 if c == "*" || c == "+" || c == "?" {661 return error("regexp: nothing to repeat before {c}")662 }663664 return p.charNode(c)665 }666667 p.parseRepeat = fn() {668 if failed(atom = p.parseAtom()) {669 return atom670 }671 return p.applyRepeat(atom)672 }673674 # applyRepeat reads the operators that follow an atom, if any at all.675 p.applyRepeat = fn(atom) {676 for {677 c = p.peek()678 min = 0679 max = -1680681 if c == "*" {682 p.next()683 } else if c == "+" {684 p.next()685 min = 1686 } else if c == "?" {687 p.next()688 max = 1689 } else if c == `{` {690 # A brace that isn't a count is a literal brace.691 save = p.i692 p.next()693 count = p.parseCount()694695 if failed(count) {696 return count697 }698699 # Not a count: the brace is a character like any other.700 if count == null {701 p.i = save702 return atom703 }704 min = count.min705 max = count.max706 } else {707 return atom708 }709710 n = node(nRepeat)711 n.sub = atom712 n.min = min713 n.max = max714 n.lazy = p.flags.ungreedy715716 if p.peek() == "?" {717 if failed(err = p.perlOnly("a lazy repetition")) {718 return err719 }720 p.next()721 n.lazy = !n.lazy722 }723724 # a** means nothing, Go rejects it too.725 c = p.peek()726 if c == "*" || c == "+" || c == "?" {727 return error("regexp: double repetition")728 }729730 atom = n731 }732 }733734 # parseQuoted reads the text of a \Q...\E, the closing \E being optional735 # at the end of the pattern.736 p.parseQuoted = fn() {737 p.next()738 p.next()739740 lit = ""741 for !p.done() {742 if p.peek() == "\\" && p.at(1) == "E" {743 p.next()744 p.next()745 return lit746 }747 lit = lit + p.next()748 }749750 return lit751 }752753 p.parseSeq = fn() {754 items = []755756 for !p.done() && p.peek() != "|" && p.peek() != ")" {757 # \Q...\E is a run of characters and not a single atom, so a star758 # after it repeats the last one of them, as it would anywhere else.759 if p.peek() == "\\" && (p.at(1) == "Q" || p.at(1) == "E") {760 if failed(err = p.perlOnly("\\Q")) {761 return err762 }763 if p.at(1) == "E" {764 p.next()765 p.next()766 continue767 }768769 lit = p.parseQuoted()770 for k = 0; k < len(lit); ++k {771 item = p.charNode(lit[k])772 if k == len(lit) - 1 {773 if failed(item = p.applyRepeat(item)) {774 return item775 }776 }777 items = append(items, item)778 }779 continue780 }781782 if failed(item = p.parseRepeat()) {783 return item784 }785 items = append(items, item)786 }787788 if len(items) == 0 { return node(nEmpty) }789 if len(items) == 1 { return items[0] }790791 n = node(nSeq)792 n.items = items793 return n794 }795796 p.parseAlt = fn() {797 if failed(left = p.parseSeq()) {798 return left799 }800801 for p.peek() == "|" {802 p.next()803 if failed(right = p.parseSeq()) {804 return right805 }806807 n = node(nAlt)808 n.left = left809 n.right = right810 left = n811 }812813 return left814 }815816 return p817}818819# --- program ---820#821# opChar, opClass and opAny consume a character, everything else is an822# epsilon transition resolved while adding a thread to the current list.823824opChar = 0825opClass = 1826opAny = 2827opSplit = 3828opJmp = 4829opSave = 5830opAssert = 6831opMatch = 7832833# Assertions, checked against the position without consuming anything.834aBegin = 0835aEnd = 1836aWordB = 2837aNoWordB = 3838aBeginLine = 4839aEndLine = 5840841compiler = fn() {842 c = new()843 c.prog = []844845 c.emit = fn(op) {846 ins = new()847 ins.op = op848 ins.x = 0849 ins.y = 0850 c.prog = append(c.prog, ins)851 return len(c.prog) - 1852 }853854 c.at = fn(pc) { c.prog[pc] }855 c.here = fn() { len(c.prog) }856857 c.compile = fn(n) {858 t = n.t859860 if t == nEmpty {861 return null862 }863864 if t == nChar {865 pc = c.emit(opChar)866 c.at(pc).ch = n.ch867 return null868 }869870 if t == nAny {871 pc = c.emit(opAny)872 c.at(pc).nl = n.nl873 return null874 }875876 if t == nClass {877 pc = c.emit(opClass)878 c.at(pc).ranges = n.ranges879 c.at(pc).negated = n.negated880 return null881 }882883 if t == nBegin || t == nEnd || t == nWordB || t == nNoWordB {884 pc = c.emit(opAssert)885 c.at(pc).x = if t == nBegin {886 if n.line { aBeginLine } else { aBegin }887 } else if t == nEnd {888 if n.line { aEndLine } else { aEnd }889 } else if t == nWordB {890 aWordB891 } else {892 aNoWordB893 }894 return null895 }896897 if t == nSeq {898 for i = 0; i < len(n.items); ++i {899 c.compile(n.items[i])900 }901 return null902 }903904 if t == nGroup {905 if n.index == 0 {906 return c.compile(n.sub)907 }908909 open = c.emit(opSave)910 c.at(open).x = n.index * 2911 c.compile(n.sub)912 close = c.emit(opSave)913 c.at(close).x = n.index * 2 + 1914 return null915 }916917 if t == nAlt {918 # split L1, L2 ; L1: left ; jmp end ; L2: right ; end:919 split = c.emit(opSplit)920 c.at(split).x = c.here()921 c.compile(n.left)922923 jmp = c.emit(opJmp)924 c.at(split).y = c.here()925 c.compile(n.right)926 c.at(jmp).x = c.here()927 return null928 }929930 if t == nRepeat {931 return c.compileRepeat(n)932 }933934 return null935 }936937 # The mandatory copies are laid out one after the other, the optional938 # ones each guarded by a split.939 c.compileRepeat = fn(n) {940 for i = 0; i < n.min; ++i {941 c.compile(n.sub)942 }943944 if n.max == -1 {945 # star: split body, end ; body ; split body, end ; end:946 #947 # The split that opens the loop and the one that closes it are two948 # instructions and not one jumped back to. A thread walks an949 # instruction once per position, so a body that matched nothing950 # would find the single split already walked and die there, when951 # what it should do is leave the loop: that is the difference952 # between (|a)* matching nothing, as it does in Go, and matching a.953 entry = c.emit(opSplit)954 body = c.here()955 c.compile(n.sub)956 loop = c.emit(opSplit)957 exit = c.here()958959 c.setSplit(entry, body, 0, n.lazy)960 c.setSplitExit(entry, exit, n.lazy)961 c.setSplit(loop, body, 0, n.lazy)962 c.setSplitExit(loop, exit, n.lazy)963 return null964 }965966 # A bounded repetition: one guarded copy for every optional round.967 splits = []968 for i = n.min; i < n.max; ++i {969 split = c.emit(opSplit)970 c.setSplit(split, c.here(), 0, n.lazy)971 splits = append(splits, split)972 c.compile(n.sub)973 }974975 end = c.here()976 for i = 0; i < len(splits); ++i {977 c.setSplitExit(splits[i], end, n.lazy)978 }979 return null980 }981982 # A greedy split tries the body first, a lazy one the exit.983 c.setSplit = fn(pc, body, exit, lazy) {984 if lazy {985 c.at(pc).y = body986 } else {987 c.at(pc).x = body988 }989 }990991 c.setSplitExit = fn(pc, exit, lazy) {992 if lazy {993 c.at(pc).x = exit994 } else {995 c.at(pc).y = exit996 }997 }998999 return c1000}10011002compileProgram = fn(tree, ngroups) {1003 c = compiler()10041005 start = c.emit(opSave)1006 c.at(start).x = 01007 c.compile(tree)1008 end = c.emit(opSave)1009 c.at(end).x = 11010 c.emit(opMatch)10111012 return c.prog1013}10141015# --- Pike VM ---10161017inRanges = fn(ins, ch) {1018 found = false10191020 for i = 0; i < len(ins.ranges); ++i {1021 if ch >= ins.ranges[i][0] && ch <= ins.ranges[i][1] {1022 found = true1023 break1024 }1025 }10261027 return if ins.negated { !found } else { found }1028}10291030assertHolds = fn(kind, text, pos) {1031 if kind == aBegin {1032 return pos == 01033 }1034 if kind == aEnd {1035 return pos == len(text)1036 }1037 if kind == aBeginLine {1038 return pos == 0 || text[pos - 1] == "\n"1039 }1040 if kind == aEndLine {1041 return pos == len(text) || text[pos] == "\n"1042 }10431044 before = pos > 0 && isWord(text[pos - 1])1045 after = pos < len(text) && isWord(text[pos])10461047 if kind == aWordB {1048 return before != after1049 }1050 return before == after1051}10521053copyCaps = fn(caps) {1054 out = []1055 for i = 0; i < len(caps); ++i {1056 out = append(out, caps[i])1057 }1058 return out1059}10601061# addThread follows the epsilon transitions and appends the threads that are1062# waiting for a character. The order of insertion is the priority order, so1063# the leftmost alternative wins like it does in Go.1064addThread = fn(list, seen, pc, text, pos, caps, prog) {1065 if seen[pc] {1066 return list1067 }1068 seen[pc] = true10691070 ins = prog[pc]10711072 if ins.op == opJmp {1073 return addThread(list, seen, ins.x, text, pos, caps, prog)1074 }10751076 if ins.op == opSplit {1077 list = addThread(list, seen, ins.x, text, pos, caps, prog)1078 return addThread(list, seen, ins.y, text, pos, caps, prog)1079 }10801081 if ins.op == opSave {1082 saved = caps[ins.x]1083 caps[ins.x] = pos1084 list = addThread(list, seen, pc + 1, text, pos, caps, prog)1085 caps[ins.x] = saved1086 return list1087 }10881089 if ins.op == opAssert {1090 if !assertHolds(ins.x, text, pos) {1091 return list1092 }1093 return addThread(list, seen, pc + 1, text, pos, caps, prog)1094 }10951096 th = new()1097 th.pc = pc1098 th.caps = copyCaps(caps)1099 return append(list, th)1100}11011102newSeen = fn(n) {1103 seen = []1104 for i = 0; i < n; ++i {1105 seen = append(seen, false)1106 }1107 return seen1108}11091110# run tries to match starting exactly at pos, returning the capture slots or1111# null. The threads are all advanced together, one character at a time.1112#1113# When longest is false the first thread to match ends the round and the ones1114# of lower priority are dropped, which is the leftmost first match Perl and Go1115# give. When it is true every thread is heard out and the match that reaches1116# furthest wins, which is the leftmost longest match POSIX asks for.1117run = fn(prog, text, pos, nslots, longest) {1118 caps = []1119 for i = 0; i < nslots; ++i {1120 caps = append(caps, -1)1121 }11221123 clist = addThread([], newSeen(len(prog)), 0, text, pos, caps, prog)1124 matched = null1125 i = pos11261127 for {1128 if len(clist) == 0 {1129 return matched1130 }11311132 nlist = []1133 seen = newSeen(len(prog))1134 ch = if i < len(text) { text[i] } else { "" }11351136 for t = 0; t < len(clist); ++t {1137 th = clist[t]1138 ins = prog[th.pc]11391140 if ins.op == opMatch {1141 if !longest {1142 # A thread of higher priority matched: the ones after it1143 # are alternatives we no longer care about.1144 matched = th.caps1145 break1146 }1147 if matched == null || th.caps[1] > matched[1] {1148 matched = th.caps1149 }1150 continue1151 }11521153 if i >= len(text) {1154 continue1155 }11561157 if ins.op == opChar && ch == ins.ch {1158 nlist = addThread(nlist, seen, th.pc + 1, text, i + 1, th.caps, prog)1159 } else if ins.op == opAny && (ins.nl || ch != "\n") {1160 nlist = addThread(nlist, seen, th.pc + 1, text, i + 1, th.caps, prog)1161 } else if ins.op == opClass && inRanges(ins, ch) {1162 nlist = addThread(nlist, seen, th.pc + 1, text, i + 1, th.caps, prog)1163 }1164 }11651166 if i >= len(text) {1167 return matched1168 }11691170 clist = nlist1171 ++i1172 }11731174 return matched1175}11761177# --- expansion ---11781179# capture returns what the group called name, or numbered by it, took hold of.1180# A name nobody answers to and a group that stayed out of the match both give1181# the empty string, the way Go's expansion does.1182capture = fn(src, caps, names, name) {1183 index = -11184 numeric = true11851186 for i = 0; i < len(name); ++i {1187 if !isDigit(name[i]) {1188 numeric = false1189 break1190 }1191 }11921193 if numeric {1194 index = int(name)1195 } else {1196 for i = 0; i < len(names); ++i {1197 if names[i] == name {1198 index = i1199 break1200 }1201 }1202 }12031204 if index < 0 || index * 2 + 1 >= len(caps) || caps[index * 2] < 0 {1205 return ""1206 }1207 return slice(src, caps[index * 2], caps[index * 2 + 1])1208}12091210# expand appends to dst the template with every $name and every ${name} put1211# for what that group captured. A $ that opens no name stands for itself and1212# $$ is a single one.1213expand = fn(dst, template, src, caps, names) {1214 out = dst1215 i = 012161217 for i < len(template) {1218 if template[i] != "$" {1219 out = out + template[i]1220 ++i1221 continue1222 }12231224 j = i + 11225 if j < len(template) && template[j] == "$" {1226 out = out + "$"1227 i = j + 11228 continue1229 }12301231 brace = j < len(template) && template[j] == `{`1232 if brace {1233 ++j1234 }12351236 name = ""1237 for j < len(template) && isWord(template[j]) {1238 name = name + template[j]1239 ++j1240 }12411242 if brace {1243 if j >= len(template) || template[j] != `}` {1244 name = ""1245 } else {1246 ++j1247 }1248 }12491250 # A malformed reference is text like any other and the scan carries1251 # on right after the dollar.1252 if len(name) == 0 {1253 out = out + "$"1254 ++i1255 continue1256 }12571258 out = out + capture(src, caps, names, name)1259 i = j1260 }12611262 return out1263}12641265# --- public API ---12661267makeRegexp = fn(pattern, tree, ngroups, names, posix) {1268 re = new()1269 re.pattern = pattern1270 re.ngroups = ngroups1271 re.names = names1272 re.posix = posix1273 re.longest = posix1274 re.prog = compileProgram(tree, ngroups)1275 re.nslots = (ngroups + 1) * 212761277 re.String = fn() { re.pattern }12781279 # NumSubexp returns the number of capturing groups.1280 re.NumSubexp = fn() { re.ngroups }12811282 # SubexpNames returns the name of every group, empty for the ones that1283 # were never given one. The first entry stands for the whole match and is1284 # always empty, so that a name sits at the index of its group.1285 re.SubexpNames = fn() { re.names }12861287 # SubexpIndex returns the number of the group called name, or -1.1288 re.SubexpIndex = fn(name) {1289 if len(name) > 0 {1290 for i = 1; i < len(re.names); ++i {1291 if re.names[i] == name {1292 return i1293 }1294 }1295 }1296 return -11297 }12981299 # Copy returns a Regexp that matches the same pattern, so that a Longest1300 # said on the one leaves the other one alone.1301 re.Copy = fn() {1302 other = compile(re.pattern, re.posix)1303 other.longest = re.longest1304 return other1305 }13061307 # MarshalText writes the Regexp out as the pattern it was compiled from.1308 re.MarshalText = fn() { bytes(re.pattern) }13091310 # UnmarshalText makes the Regexp the one that the given pattern spells.1311 re.UnmarshalText = fn(b) {1312 if failed(other = compile(string(b), re.posix)) {1313 return other1314 }13151316 re.pattern = other.pattern1317 re.prog = other.prog1318 re.names = other.names1319 re.ngroups = other.ngroups1320 re.nslots = other.nslots1321 re.longest = other.longest1322 return null1323 }13241325 # Longest asks the searches that follow for the leftmost longest match1326 # instead of the leftmost first one, as POSIX wants it. It changes the1327 # regexp itself, so say it before searching and not in the middle.1328 re.Longest = fn() { re.longest = true }13291330 # LiteralPrefix returns [prefix, complete]: the text every match must1331 # begin with, and whether the pattern is that text and nothing else.1332 re.LiteralPrefix = fn() {1333 prefix = ""13341335 for pc = 0; pc < len(re.prog); ++pc {1336 ins = re.prog[pc]13371338 if ins.op == opSave {1339 continue1340 }1341 if ins.op == opChar {1342 prefix = prefix + ins.ch1343 continue1344 }1345 return [prefix, ins.op == opMatch]1346 }13471348 return [prefix, false]1349 }13501351 # findFrom returns the capture slots of the first match that begins at or1352 # after pos. The program is anchored where it starts, so the beginning is1353 # tried one position at a time.1354 re.findFrom = fn(s, pos) {1355 for i = pos; i <= len(s); ++i {1356 caps = run(re.prog, s, i, re.nslots, re.longest)1357 if caps != null {1358 return caps1359 }1360 }1361 return null1362 }13631364 # FindStringSubmatchIndex returns the index pairs of the leftmost match1365 # and of its groups, null when there is no match.1366 re.FindStringSubmatchIndex = fn(s) { re.findFrom(s, 0) }13671368 # FindStringIndex returns the start and the end of the leftmost match.1369 re.FindStringIndex = fn(s) {1370 caps = re.FindStringSubmatchIndex(s)1371 return if caps == null { null } else { [caps[0], caps[1]] }1372 }13731374 # FindString returns the text of the leftmost match, empty if there is none.1375 re.FindString = fn(s) {1376 idx = re.FindStringIndex(s)1377 return if idx == null { "" } else { slice(s, idx[0], idx[1]) }1378 }13791380 capsToStrings = fn(s, caps) {1381 out = []1382 for i = 0; i < len(caps); i = i + 2 {1383 if caps[i] == -1 {1384 out = append(out, null)1385 } else {1386 out = append(out, slice(s, caps[i], caps[i + 1]))1387 }1388 }1389 return out1390 }13911392 # FindStringSubmatch returns the match and its groups. A group that took1393 # no part in the match is null.1394 re.FindStringSubmatch = fn(s) {1395 caps = re.FindStringSubmatchIndex(s)1396 return if caps == null { null } else { capsToStrings(s, caps) }1397 }13981399 # MatchString reports whether s contains a match.1400 re.MatchString = fn(s) { re.FindStringSubmatchIndex(s) != null }14011402 re.Match = fn(b) { re.MatchString(string(b)) }14031404 # The reader side of the family. Go reads only as far as it must, this1405 # reads the stream to its end and searches what it read.1406 #1407 # ponytail: an endless reader would never return here, which no stream a1408 # file or a connection gives ever is. Searching as the bytes come in is1409 # what to write the day one is.1410 re.FindReaderSubmatchIndex = fn(r) {1411 if failed(data = io.ReadAll(r)) {1412 return data1413 }1414 return re.FindStringSubmatchIndex(string(data))1415 }14161417 re.FindReaderIndex = fn(r) {1418 caps = re.FindReaderSubmatchIndex(r)1419 if failed(caps) {1420 return caps1421 }1422 return if caps == null { null } else { [caps[0], caps[1]] }1423 }14241425 re.MatchReader = fn(r) {1426 caps = re.FindReaderSubmatchIndex(r)1427 if failed(caps) {1428 return caps1429 }1430 return caps != null1431 }14321433 # allMatches returns the captures of every match, at most n when n >= 0.1434 # It returns a list instead of taking a callback because a closure that1435 # appends to a list of its enclosing scope would append to its own copy.1436 re.allMatches = fn(s, n) {1437 out = []1438 pos = 01439 prev = -114401441 for pos <= len(s) {1442 if n >= 0 && len(out) >= n {1443 return out1444 }14451446 caps = re.findFrom(s, pos)1447 if caps == null {1448 return out1449 }14501451 if caps[1] == caps[0] {1452 # An empty match where the last one ended says nothing new, so1453 # it is dropped; either way it steps one character forward, or1454 # the same position would keep matching for ever.1455 if caps[0] != prev {1456 out = append(out, caps)1457 }1458 pos = caps[1] + 11459 } else {1460 out = append(out, caps)1461 pos = caps[1]1462 }14631464 prev = caps[1]1465 }14661467 return out1468 }14691470 nOrAll = fn(n) { if n == null { -1 } else { n } }14711472 # FindAllString returns up to n matches, all of them when n is -1.1473 re.FindAllString = fn(s, n) {1474 ms = re.allMatches(s, nOrAll(n))1475 out = []14761477 for i = 0; i < len(ms); ++i {1478 out = append(out, slice(s, ms[i][0], ms[i][1]))1479 }1480 return if len(out) == 0 { null } else { out }1481 }14821483 re.FindAllStringIndex = fn(s, n) {1484 ms = re.allMatches(s, nOrAll(n))1485 out = []14861487 for i = 0; i < len(ms); ++i {1488 out = append(out, [ms[i][0], ms[i][1]])1489 }1490 return if len(out) == 0 { null } else { out }1491 }14921493 re.FindAllStringSubmatch = fn(s, n) {1494 ms = re.allMatches(s, nOrAll(n))1495 out = []14961497 for i = 0; i < len(ms); ++i {1498 out = append(out, capsToStrings(s, ms[i]))1499 }1500 return if len(out) == 0 { null } else { out }1501 }15021503 re.FindAllStringSubmatchIndex = fn(s, n) {1504 ms = re.allMatches(s, nOrAll(n))1505 return if len(ms) == 0 { null } else { ms }1506 }15071508 # The byte side of the family. A pattern reads bytes as a string reads1509 # them, so each of these asks its string twin and dresses the answer back1510 # up in bytes.1511 toBytes = fn(x) { if x == null { null } else { bytes(x) } }15121513 listToBytes = fn(l) {1514 if l == null {1515 return null1516 }15171518 out = []1519 for i = 0; i < len(l); ++i {1520 out = append(out, toBytes(l[i]))1521 }1522 return out1523 }15241525 re.Find = fn(b) {1526 s = string(b)1527 idx = re.FindStringIndex(s)1528 return if idx == null { null } else { bytes(slice(s, idx[0], idx[1])) }1529 }15301531 re.FindIndex = fn(b) { re.FindStringIndex(string(b)) }1532 re.FindSubmatch = fn(b) { listToBytes(re.FindStringSubmatch(string(b))) }1533 re.FindSubmatchIndex = fn(b) { re.FindStringSubmatchIndex(string(b)) }1534 re.FindAll = fn(b, n) { listToBytes(re.FindAllString(string(b), n)) }1535 re.FindAllIndex = fn(b, n) { re.FindAllStringIndex(string(b), n) }1536 re.FindAllSubmatchIndex = fn(b, n) { re.FindAllStringSubmatchIndex(string(b), n) }15371538 re.FindAllSubmatch = fn(b, n) {1539 ms = re.FindAllStringSubmatch(string(b), n)1540 if ms == null {1541 return null1542 }15431544 out = []1545 for i = 0; i < len(ms); ++i {1546 out = append(out, listToBytes(ms[i]))1547 }1548 return out1549 }15501551 # ExpandString appends to dst the template with every $1 and ${name} of it1552 # put for what that group of match captured in s.1553 re.ExpandString = fn(dst, template, s, match) { expand(dst, template, s, match, re.names) }15541555 re.Expand = fn(dst, template, src, match) {1556 return bytes(expand(string(dst), string(template), string(src), match, re.names))1557 }15581559 # replaceAll rebuilds s with what f makes of the captures of every match1560 # standing where the match was.1561 re.replaceAll = fn(s, f) {1562 ms = re.allMatches(s, -1)1563 out = ""1564 last = 015651566 for i = 0; i < len(ms); ++i {1567 out = out + slice(s, last, ms[i][0]) + f(ms[i])1568 last = ms[i][1]1569 }15701571 return out + slice(s, last, len(s))1572 }15731574 # ReplaceAllStringFunc replaces every match with what f returns for it.1575 re.ReplaceAllStringFunc = fn(s, f) {1576 return re.replaceAll(s, fn(caps) { f(slice(s, caps[0], caps[1])) })1577 }15781579 # ReplaceAllString replaces every match with repl, in which $1 and1580 # ${name} stand for what the groups captured.1581 re.ReplaceAllString = fn(s, repl) {1582 return re.replaceAll(s, fn(caps) { expand("", repl, s, caps, re.names) })1583 }15841585 # ReplaceAllLiteralString replaces every match with repl taken word for1586 # word, no dollar of it meaning anything.1587 re.ReplaceAllLiteralString = fn(s, repl) { re.replaceAll(s, fn(caps) { repl }) }15881589 re.ReplaceAll = fn(b, repl) { bytes(re.ReplaceAllString(string(b), string(repl))) }1590 re.ReplaceAllLiteral = fn(b, repl) { bytes(re.ReplaceAllLiteralString(string(b), string(repl))) }15911592 re.ReplaceAllFunc = fn(b, f) {1593 s = string(b)1594 return bytes(re.replaceAll(s, fn(caps) { string(f(bytes(slice(s, caps[0], caps[1])))) }))1595 }15961597 # Split slices s around every match, into at most n pieces when n >= 0.1598 re.Split = fn(s, n) {1599 limit = nOrAll(n)1600 if limit == 0 {1601 return null1602 }1603 if len(re.pattern) > 0 && len(s) == 0 {1604 return [""]1605 }16061607 ms = re.allMatches(s, limit)1608 out = []1609 beg = 01610 end = 016111612 for i = 0; i < len(ms); ++i {1613 if limit > 0 && len(out) >= limit - 1 {1614 break1615 }16161617 end = ms[i][0]1618 # A match at the very beginning leaves no piece before it.1619 if ms[i][1] != 0 {1620 out = append(out, slice(s, beg, end))1621 }1622 beg = ms[i][1]1623 }16241625 if end != len(s) {1626 out = append(out, slice(s, beg, len(s)))1627 }1628 return out1629 }16301631 return re1632}16331634compile = fn(pattern, posix) {1635 p = parser(pattern, posix)16361637 if failed(tree = p.parseAlt()) {1638 return tree1639 }1640 if !p.done() {1641 return error("regexp: unexpected {p.peek()}")1642 }16431644 return makeRegexp(pattern, tree, p.ngroups, p.names, posix)1645}16461647# Compile parses a pattern and returns a Regexp, or an error.1648Compile = fn(pattern) { compile(pattern, false) }16491650# CompilePOSIX is Compile for a plain POSIX ERE: none of the escapes and the1651# groups Perl added, and the leftmost longest match instead of the first one.1652CompilePOSIX = fn(pattern) { compile(pattern, true) }16531654# MustCompile is Compile, but it stops the program on an invalid pattern.1655MustCompile = fn(pattern) {1656 re = Compile(pattern)1657 if failed(re) {1658 exit(string(re), 1)1659 }1660 return re1661}16621663# MustCompilePOSIX is CompilePOSIX, but it stops the program on an invalid1664# pattern.1665MustCompilePOSIX = fn(pattern) {1666 re = CompilePOSIX(pattern)1667 if failed(re) {1668 exit(string(re), 1)1669 }1670 return re1671}16721673# QuoteMeta returns a pattern that matches the literal text of s.1674QuoteMeta = fn(s) {1675 meta = "\\.+*?()|[]{}^$"1676 out = ""16771678 for i = 0; i < len(s); ++i {1679 for j = 0; j < len(meta); ++j {1680 if s[i] == meta[j] {1681 out = out + "\\"1682 break1683 }1684 }1685 out = out + s[i]1686 }16871688 return out1689}16901691# --- package level shortcuts ---16921693MatchString = fn(pattern, s) {1694 re = Compile(pattern)1695 if failed(re) {1696 return re1697 }1698 return re.MatchString(s)1699}17001701Match = fn(pattern, b) { MatchString(pattern, string(b)) }17021703MatchReader = fn(pattern, r) {1704 re = Compile(pattern)1705 if failed(re) {1706 return re1707 }1708 return re.MatchReader(r)1709}