Regex in Go, RE2 and re2js

Ask Go’s regexp package whether ^(a+)+$ matches a line of 100,000 letters a followed by !, and it answers false within a limit it knows before it starts: the size of the compiled pattern times the length of the line. The package documentation promises that every match runs in time linear in the size of the input, a property it says most open source engines do not guarantee. The price is a list of constructs Go will not compile, and the compiler prints that list itself.

That trade shapes the whole package. Here you read the refusals and the reason behind them, choose the method that returns what you need, avoid the template rule that deletes text without an error, predict Go’s own rule for empty matches, use the two switches that change which text matches, and see what changes when the same patterns run in a browser.

Linear time, paid for with the features RE2 refuses

Go’s regexp accepts the syntax of RE2RE2: A regular-expression library and syntax from Google whose primary guarantees include match time linear in the input, which is why it leaves out backreferences and lookaround. Go's regexp package accepts its syntax., a library from Google whose README names linear match time as one of its primary guarantees, and checks every pattern when it compiles it. Give the compiler one small pattern for each construct a Perl-style engine offers, and its answers are the list of what the syntax leaves out:

// Go's regexp package checks every pattern when it compiles it, and refuses the constructs that RE2 leaves out.
// Each line shows a construct, a small pattern that uses it and what regexp.Compile answered. Every refusal starts
// with "error parsing regexp: ", so the program prints that prefix once and drops it from the lines.
package main

import (
	"fmt"
	"regexp"
	"strings"
)

func main() {
	probes := []struct{ feature, pattern string }{
		{"backreference", `(a)\1`},
		{"named backreference", `\k<n>`},
		{"lookahead", `(?=a)`},
		{"negative lookahead", `(?!a)`},
		{"lookbehind", `(?<=a)`},
		{"negative lookbehind", `(?<!a)`},
		{"possessive", `a++`},
		{"atomic group", `(?>a)`},
		{"end or final newline", `a\Z`},
		{"grapheme cluster", `\X`},
		{"free-spacing mode", `(?x)a`},
		{"count above 1000", `a{1001}`},
		{"end of last match", `\Ga`},
		{"named group (?<n>)", `(?<n>a)`},
		{"named group (?P<n>)", `(?P<n>a)`},
	}
	const prefix = "error parsing regexp: "
	fmt.Println("Every refusal below starts with:", strings.TrimSpace(prefix))
	for _, p := range probes {
		answer := "compiles"
		if _, err := regexp.Compile(p.pattern); err != nil {
			answer = strings.TrimPrefix(err.Error(), prefix)
		}
		fmt.Printf("%-21s %-8s %s\n", p.feature, p.pattern, answer)
	}
}

Every refusal below starts with: error parsing regexp:
backreference         (a)\1    invalid escape sequence: `\1`
named backreference   \k<n>    invalid escape sequence: `\k`
lookahead             (?=a)    invalid or unsupported Perl syntax: `(?=`
negative lookahead    (?!a)    invalid or unsupported Perl syntax: `(?!`
lookbehind            (?<=a)   invalid named capture: `(?<=a)`
negative lookbehind   (?<!a)   invalid named capture: `(?<!a)`
possessive            a++      invalid nested repetition operator: `++`
atomic group          (?>a)    invalid or unsupported Perl syntax: `(?>`
end or final newline  a\Z      invalid escape sequence: `\Z`
grapheme cluster      \X       invalid escape sequence: `\X`
free-spacing mode     (?x)a    invalid or unsupported Perl syntax: `(?x`
count above 1000      a{1001}  invalid repeat count: `{1001}`
end of last match     \Ga      invalid escape sequence: `\G`
named group (?<n>)    (?<n>a)  compiles
named group (?P<n>)   (?P<n>a) compiles

Thirteen of the fifteen patterns fail, and only the two spellings of a named group compile. RE2’s syntax page marks the refused forms NOT SUPPORTED, from backreferences, lookahead and lookbehind to possessive quantifiers, atomic groups, \Z, \G and \X, and its table of flags holds only i, m, s and U, so (?x) fails as well. The repetition limit comes from regexp/syntax, which rejects any counted form whose minimum or maximum goes above 1,000. Because the refusal comes from the compiler, a program learns of it when it builds the pattern, never halfway through a file of input.

Why give up so much? A backtracking engine follows one path through the pattern at a time and returns to a saved choice when that path fails, as how an engine finds a match shows step by step. Go follows every path at once. It compiles the pattern into a small program and keeps the set of instructions that are still alive at the current character; each character is read once and moves the whole set forward. Russ Cox’s article traces this multiple-state method to Ken Thompson’s 1968 paper and explains why it is linear: the simulation tracks which states are reachable, not the paths that reached them, so the set never holds more entries than the program has instructions. The same article notes that the best known ways to support backreferences need exponential search in the worst case. That is the price of linear-time matchinglinear-time matching: A guarantee that, for a fixed pattern, the time a match takes grows at most in proportion to the length of the text, whatever the text holds. Go's regexp gives it by following every path of the pattern at once.. Step through (a|ab)c on abc, the case the matching lesson solves by backing up, and watch both alternatives move forward together:

Path 1 died at the b and nothing came back for it. On a long text the set can hold many paths, but never more than the program has instructions, so the work for each character has a ceiling set by the pattern alone. To report groups as well, Go’s matcher gives each live path a thread that carries its own group offsets (the package source, exec.go), the design Russ Cox’s second article calls a Pike VMPike VM: A way to run a compiled pattern that keeps at most one thread per instruction, each with its own group offsets, and moves them all forward one character at a time. Rob Pike first used it in the sam editor., after Rob Pike’s sam editor. For small patterns on short texts Go uses a backtracker instead, which marks every pair of an instruction and a position it has visited, so it never does the same work twice (backtrack.go).

The ceiling can be printed. The program below runs three pattern shapes that the module on performance and security returns to, each on a long text that does not match, and prints the answer with its bound instead of a time: the instructions of the compiled program times the positions of the text.

// Three pattern shapes that are slow in backtracking engines, run by Go on long texts that do not match. The program
// prints each answer and the bound that makes it come back: the compiled program's instructions times the positions
// of the text, because the engine handles each pair of an instruction and a position at most once. No timing is
// printed: the bound, not a stopwatch, is the point.
package main

import (
	"fmt"
	"regexp"
	"regexp/syntax"
	"strings"
)

// instructions compiles a pattern the way regexp.Compile does (parse, simplify, compile) and counts the program.
func instructions(pattern string) int {
	tree, err := syntax.Parse(pattern, syntax.Perl)
	if err != nil {
		panic(err)
	}
	prog, err := syntax.Compile(tree.Simplify())
	if err != nil {
		panic(err)
	}
	return len(prog.Inst)
}

func main() {
	cases := []struct{ pattern, text string }{
		{`^(a+)+$`, strings.Repeat("a", 100000) + "!"},
		{`(a|aa)*b`, strings.Repeat("a", 100000)},
		{`\s+$`, strings.Repeat(" ", 40000) + "x"},
	}
	for _, c := range cases {
		matched := regexp.MustCompile(c.pattern).MatchString(c.text)
		n, positions := instructions(c.pattern), len(c.text)+1
		fmt.Printf("%-9s on %d characters: match %v\n", c.pattern, len(c.text), matched)
		fmt.Printf("%-9s %d instructions x %d positions = at most %d pairs\n", "", n, positions, n*positions)
	}
}

^(a+)+$   on 100001 characters: match false
          9 instructions x 100002 positions = at most 900018 pairs
(a|aa)*b  on 100000 characters: match false
          10 instructions x 100001 positions = at most 1000010 pairs
\s+$      on 40001 characters: match false
          5 instructions x 40002 positions = at most 200010 pairs

^(a+)+$ compiles to 9 instructions, and 100,001 characters give 100,002 positions, so the engine has at most 900,018 pairs of an instruction and a position to handle before it can answer false. (a|aa)*b compiles to 10 instructions and \s+$ to 5. Double the text and the bound doubles too, give or take one position. Why such shapes can take a backtracking engine far longer, and how to defuse them there, belongs to the performance module; in Go no pattern can lift the ceiling above its program’s size times the text’s length. Go is not the only engine that makes this promise, and Regex in Java, .NET, Ruby and Rust shows which engines on those platforms do.

Pick the method by what you want back

Most of the package is one question asked in different shapes. The finding methods are named by a rule: Find for the first match or FindAll for every match, then String when the text is a string rather than a byte slice, Submatch to get the groups as well, and Index to get positions instead of text. With the calls that replace, split and name, this table covers everyday work on strings:

A count of -1 asks for every match, and a count of n for at most n. The return value that needs reading is the index list. The program below reads three invented lines of an access log with one pattern of named groupsnamed group: A capturing group that carries a name as well as a number, so the match reads back by name instead of by slot: (?<year>\d{4}) in JavaScript, PCRE2, Go, PHP, Java and .NET; (?P<year>\d{4}) in Python, Go, PHP and PCRE2. More in “Named groups across regex flavours”, written in both spellings Go accepts, (?P<time>…) and (?<method>…), side by side. It prints SubexpNames, then the list FindAllStringSubmatchIndex gives for each line, and slices two fields out of each line by the group numbers that SubexpIndex looked up:

// A short access log read with one pattern of named groups (both spellings Go accepts). For each match,
// FindAllStringSubmatchIndex returns one flat list of byte offsets: start and end of the whole match, then start
// and end of every group in order; -1 -1 marks a group that took no part in the match.
package main

import (
	"fmt"
	"regexp"
	"unicode/utf8"
)

const accessLog = `09:14:03 GET /orders/42 200 31ms user=asha
09:14:04 POST /cart 500 812ms
09:14:05 GET /menu/café 200 9ms user=ravi`

func main() {
	re := regexp.MustCompile(`(?m)^(?P<time>\S+) (?<method>[A-Z]+) (?<path>\S+) (?<status>\d{3}) (?<ms>\d+)ms(?: user=(?<user>\w+))?$`)
	fmt.Printf("names %q\n", re.SubexpNames())
	status, user := re.SubexpIndex("status"), re.SubexpIndex("user")
	fmt.Println("status is group", status, "and user is group", user)
	for _, m := range re.FindAllStringSubmatchIndex(accessLog, -1) {
		fmt.Println(m)
		start, end := m[2*status], m[2*status+1]
		who := "took no part"
		if m[2*user] >= 0 {
			who = accessLog[m[2*user]:m[2*user+1]]
		}
		fmt.Printf("  status %s at bytes %d to %d (character %d), user %s\n",
			accessLog[start:end], start, end, utf8.RuneCountInString(accessLog[:start]), who)
	}
}

names ["" "time" "method" "path" "status" "ms" "user"]
status is group 4 and user is group 6
[0 42 0 8 9 12 13 23 24 27 28 30 38 42]
  status 200 at bytes 24 to 27 (character 24), user asha
[43 72 43 51 52 56 57 62 63 66 67 70 -1 -1]
  status 500 at bytes 63 to 66 (character 63), user took no part
[73 115 73 81 82 85 86 97 98 101 102 103 111 115]
  status 200 at bytes 98 to 101 (character 97), user ravi

Read the first list two numbers at a time. 0 42 is the whole match, from byte 0 up to byte 42; then come the groups in the order their parentheses open: time at 0 to 8, method at 9 to 12, path at 13 to 23 and status at 24 to 27. Group k always sits at places 2k and 2k + 1 of the list, which is how the program finds status, group 4, at places 8 and 9. The second line ends in -1 -1: its optional user group took no part in the match, and the documentation gives a negative index exactly that meaning. The third line shows that the numbers count bytes, not characters. Its path holds café, and é takes two bytes in UTF-8, so the status begins at byte 98 but at character 97.

FindString has one trap of its own in the table: its "" can mean that nothing matched or that the pattern matched nothing, and the documentation sends you to FindStringIndex or FindStringSubmatch to tell the two apart.

Braces keep a template from swallowing text

A masking rule keeps the first two digits of an order number and hides the other four, so ORD-123456 should become ORD-12xxxx. The pattern (ORD-\d{2})\d{4} captures the part to keep, and the replacement stringreplacement string: The new text given to a replace function. It has its own escapes, so a dollar sign or a backslash in it may name part of the match instead of standing for itself. More in “Writing patterns in code: strings and escaping” puts group 1 back with four letters x after it. Here is the template $1xxxx in Go and in Python, beside the two other spellings people carry between languages:

// A masking rule: keep the first two digits of an order number and hide the other four. Go reads only $ in a
// template, and in $1xxxx it takes the name as far as letters, digits and underscores go: it asks for a group named
// 1xxxx, which the pattern does not have, and writes nothing in its place.
package main

import (
	"fmt"
	"regexp"
)

func main() {
	line := "order ORD-123456 shipped"
	re := regexp.MustCompile(`(ORD-\d{2})\d{4}`)
	for _, template := range []string{`$1xxxx`, `${1}xxxx`, `\1xxxx`} {
		fmt.Printf("%-16s \"%s\"\n", template, re.ReplaceAllString(line, template))
	}
	fmt.Printf("%-16s \"%s\"\n", "literal $1xxxx", re.ReplaceAllLiteralString(line, "$1xxxx"))
	fmt.Printf("%-16s \"%s\"\n", "$$1xxxx", re.ReplaceAllString(line, "$$1xxxx"))
	hide := func(m string) string { return m[:len(m)-4] + "xxxx" }
	fmt.Printf("%-16s \"%s\"\n", "a function", re.ReplaceAllStringFunc(line, hide))

	// The same rule in two letters: group 1 is a, and the text is ab.
	a := regexp.MustCompile(`(a)`)
	fmt.Printf("%q %q %q\n", a.ReplaceAllString("ab", "$1x"), a.ReplaceAllString("ab", "${1}x"), a.ReplaceAllLiteralString("ab", "$1x"))
}

$1xxxx           "order  shipped"
${1}xxxx         "order ORD-12xxxx shipped"
\1xxxx           "order \1xxxx shipped"
literal $1xxxx   "order $1xxxx shipped"
$$1xxxx          "order $1xxxx shipped"
a function       "order ORD-12xxxx shipped"
"b" "axb" "$1xb"

"""The masking rule in Python: its templates name a group with a backslash, \\1 or \\g<1>, so a dollar sign and a
pair of braces are plain text there and are written into the result as they are."""

import re

line = "order ORD-123456 shipped"
pattern = re.compile(r"(ORD-\d{2})\d{4}")
for template in ("$1xxxx", "${1}xxxx", r"\1xxxx", r"\g<1>xxxx"):
    print(f'{template:<16} "{pattern.sub(template, line)}"')
result = pattern.sub(lambda m: m[1] + "xxxx", line)
print(f'{"a function":<16} "{result}"')

$1xxxx           "order $1xxxx shipped"
${1}xxxx         "order ${1}xxxx shipped"
\1xxxx           "order ORD-12xxxx shipped"
\g<1>xxxx        "order ORD-12xxxx shipped"
a function       "order ORD-12xxxx shipped"

Go’s first line is the one to remember: the whole order number is gone, two spaces stand between order and shipped, and nothing reported an error. In a template Go reads $ and then a name, and the name runs as far as letters, digits and underscores go, so $1xxxx asks for a group named 1xxxx; the documentation of Expand uses $1x as its own example. The pattern has no such group, and a missing group becomes empty text. Braces end the name where you mean it: ${1}xxxx keeps ORD-12. A backslash means nothing to Go, so \1xxxx comes out as written. Python is the other way round: it reads only the backslash forms, \1 and \g<1>, and copies the dollar forms as text. JavaScript reads $1 followed by letters as group 1 and then text, and copies ${1} as it stands:

// The masking rule in JavaScript: a replacement reads $1 as group 1 and the letters after it as text. It has no ${1}
// form and gives a backslash no meaning, so those two spellings are written into the result as they are.
const line = 'order ORD-123456 shipped';
const re = /(ORD-\d{2})\d{4}/g;

for (const template of ['$1xxxx', '${1}xxxx', '\\1xxxx', '$$1xxxx']) {
  console.log(template.padEnd(16), `"${line.replace(re, template)}"`);
}
console.log('a function'.padEnd(16), `"${line.replace(re, (match, first) => first + 'xxxx')}"`);

$1xxxx           "order ORD-12xxxx shipped"
${1}xxxx         "order ${1}xxxx shipped"
\1xxxx           "order \1xxxx shipped"
$$1xxxx          "order $1xxxx shipped"
a function       "order ORD-12xxxx shipped"

Press Run, then Edit: turn the group into (?<keep>ORD-\d{2}), add the template $<keep>xxxx to the list and run it again. JavaScript names a group in a replacement with angle brackets, where Go writes ${keep} and Python \g<keep>; the porting lesson sets the spellings of every engine side by side. Lines four to six of the Go run are its other ways out: ReplaceAllLiteralString inserts its text unread, $$1xxxx writes a single dollar sign, and ReplaceAllStringFunc hands each match to a function, where no template rule can reach it. The final line repeats the porting lesson’s two-letter case: (a) with $1x on ab gives b, and with ${1}x gives axb.

Go skips the empty match right after a match

Replace every match of a* in baac with a dash. JavaScript and Python return -b--c-, and Go returns -b-c-. The star can match nothing, so a search finds empty matchesempty match: A match of length zero: the pattern succeeds at a position without taking any character, as x* does where no x stands. Global searches, splits and replacements report such matches, each engine by its own rules. More in “Repetition with *, +, ? and {m,n}” besides aa, and the engines disagree about one of them. Step through the four places a search for a* stops in baac:

Go’s documentation states the rule in one sentence: “Empty matches abutting a preceding match are ignored.” The empty match at position 3 begins exactly where aa ended, so Go never reports it. Python’s documentation says the opposite, with an example of its own: there, an empty match may follow straight after a non-empty one. The runs below print the matches, the replacement and the split in each language:

// a* can match nothing, so a search for it in "baac" finds empty matches besides aa. Go ignores an empty match that
// touches the match before it, which changes the list of matches and every replacement built on it.
package main

import (
	"fmt"
	"regexp"
)

func main() {
	text := "baac"
	star := regexp.MustCompile(`a*`)
	fmt.Println("matches at", star.FindAllStringIndex(text, -1))
	fmt.Printf("matches    %q\n", star.FindAllString(text, -1))
	fmt.Printf("replace    %q\n", star.ReplaceAllString(text, "-"))
	fmt.Printf("split      %q\n", star.Split(text, -1))
	fmt.Printf("on aaa     %q\n", star.ReplaceAllString("aaa", "-"))
	plus := regexp.MustCompile(`a+`)
	fmt.Printf("a+ replace %q\n", plus.ReplaceAllString(text, "-"))
}

matches at [[0 0] [1 3] [4 4]]
matches    ["" "aa" ""]
replace    "-b-c-"
split      ["b" "c"]
on aaa     "-"
a+ replace "b-c"

"""The same searches in Python: an empty match right after aa is still a match here, and re.split cuts at every
match, the empty ones included."""

import re

text = "baac"
print("matches at", [m.span() for m in re.finditer(r"a*", text)])
print("matches   ", re.findall(r"a*", text))
print("replace   ", repr(re.sub(r"a*", "-", text)))
print("split     ", re.split(r"a*", text))
print("on aaa    ", repr(re.sub(r"a*", "-", "aaa")))
print("a+ replace", repr(re.sub(r"a+", "-", text)))

matches at [(0, 0), (1, 3), (3, 3), (4, 4)]
matches    ['', 'aa', '', '']
replace    '-b--c-'
split      ['', 'b', '', 'c', '']
on aaa     '--'
a+ replace 'b-c'

// The same searches in JavaScript: after aa ends at position 3, a global search still reports the empty match there,
// so the replacement writes two dashes between b and c.
const text = 'baac';
const spans = [...text.matchAll(/a*/g)].map((m) => [m.index, m.index + m[0].length]);
console.log('matches at', JSON.stringify(spans));
console.log('matches   ', JSON.stringify(text.match(/a*/g)));
console.log('replace   ', JSON.stringify(text.replace(/a*/g, '-')));
console.log('split     ', JSON.stringify(text.split(/a*/)));
console.log('a+ replace', JSON.stringify(text.replace(/a+/g, '-')));

matches at [[0,0],[1,3],[3,3],[4,4]]
matches    ["","aa","",""]
replace    "-b--c-"
split      ["b","c"]
a+ replace "b-c"

Side by side, the three runs give this table:

Every Go method that walks the list of matches follows the rule, so a replacement, a split and FindAllString all lose the same empty match. The split column differs for a second reason, since each language decides on its own which empty pieces to keep; the quantifiers lesson shows the same differences on axxb. The last line of each run is the way around them: a+ cannot match nothing, and all three engines return b-c.

A pattern that can match nothing is where the three engines part ways, so it is also where a port needs its test inputs:

Two switches that change the match, not the time limit

Every engine of this lesson so far picks the leftmost-firstleftmost-first: A rule for choosing among matches: take the earliest start, then the match a backtracking search finds first, which follows the order of the alternatives. JavaScript, Python and PCRE2 use it. More in “How an engine finds a match, step by step” match: among the matches that start earliest, the one a backtracking search would find first. Go offers a second rule. CompilePOSIX compiles a pattern for leftmost-longestleftmost-longest: A rule for choosing among matches: take the earliest start, then the longest match from it, whatever the order of the alternatives. POSIX specifies it. More in “How an engine finds a match, step by step” matching, the rule POSIX specifies, and the method Longest switches an already compiled pattern to it. A tokenizer whose keywords are written shortest first shows the difference, and the same run tries the U flag and the syntax CompilePOSIX accepts:

// Three switches that change which text matches, not how fast it is found: CompilePOSIX and Longest take the longest
// of the matches that start at the same place, and (?U) swaps the greedy and lazy forms of every quantifier.
package main

import (
	"fmt"
	"regexp"
)

func main() {
	keywords := `in|int|interface`
	first := regexp.MustCompile(keywords)
	posix := regexp.MustCompilePOSIX(keywords)
	longest := regexp.MustCompile(keywords)
	longest.Longest()
	for _, word := range []string{"interface", "int", "into"} {
		fmt.Printf("%-9s Compile %-5q CompilePOSIX %-11q Longest %q\n",
			word, first.FindString(word), posix.FindString(word), longest.FindString(word))
	}

	tags := "<b>bold</b> text"
	for _, p := range []string{`<.+>`, `<.+?>`, `(?U)<.+>`, `(?U)<.+?>`} {
		fmt.Printf("%-10s %q\n", p, regexp.MustCompile(p).FindString(tags))
	}
	// The U flag is not Java's Unicode switch: \w stays ASCII, and every match is one character long.
	fmt.Printf("%-10s %q\n", `(?U)\w+`, regexp.MustCompile(`(?U)\w+`).FindAllString("go नमस्ते", -1))

	// CompilePOSIX also narrows the syntax to POSIX extended regular expressions.
	for _, p := range []string{`\d+`, `(?i)go`, `[0-9]+`, `[[:digit:]]+`} {
		answer := "compiles"
		if _, err := regexp.CompilePOSIX(p); err != nil {
			answer = err.Error()
		}
		fmt.Printf("CompilePOSIX %-12s %s\n", p, answer)
	}
}

interface Compile "in"  CompilePOSIX "interface" Longest "interface"
int       Compile "in"  CompilePOSIX "int"       Longest "int"
into      Compile "in"  CompilePOSIX "int"       Longest "int"
<.+>       "<b>bold</b>"
<.+?>      "<b>"
(?U)<.+>   "<b>"
(?U)<.+?>  "<b>bold</b>"
(?U)\w+    ["g" "o"]
CompilePOSIX \d+          error parsing regexp: invalid escape sequence: `\d`
CompilePOSIX (?i)go       error parsing regexp: missing argument to repetition operator: `?`
CompilePOSIX [0-9]+       compiles
CompilePOSIX [[:digit:]]+ compiles

On interface, in|int|interface gives in under Compile, because in is written first and matches, and interface under CompilePOSIX and Longest, because it is the longest match from position 0. How an engine finds a match compares the two rules on a|ab. CompilePOSIX also narrows the syntax to POSIX extended expressions: the last lines show \d refused, and (?i) refused with a message about a repetition operator, because in that syntax a question mark can only repeat what comes before it. Write [0-9] or [[:digit:]] there instead. Both rules keep the package’s linear bound; only the match they report changes.

The second switch is a flag. (?U) swaps the greedy and the lazy form of every quantifier: in the run, (?U)<.+> stops at the first > and returns <b>, while (?U)<.+?> turns greedy and returns <b>bold</b>. regexp/syntax lists the flag as U, ungreedy, and PCRE2 and PHP know the same ungreedy modeungreedy mode: An option of PCRE2, PHP (the U modifier) and Go, also set with (?U) in a pattern, that swaps the two forms: a quantifier without a question mark is lazy and one with it is greedy. JavaScript and Python have no such mode. More in “Greedy and lazy quantifiers”, which greedy and lazy quantifiers compares across engines.

A reader who sees only the pattern sees neither switch: CompilePOSIX and Longest live in the code that compiles it, and a (?U) at its start is easy to miss. Leave a comment where either one is set.

The same syntax in a browser, with JavaScript habits

A pattern that runs in a Go service often has to run in a page as well: a preview of a log filter, or a check on a form before it is sent. The browser’s own RegExp is the JavaScript flavour, not RE2. re2js is a JavaScript library that ports the RE2 engine; its README says it reaches full architectural parity with Go’s regexp package and guarantees linear time in the browser and in Node.js. Set against Go, its README states this:

The syntax and the time bound travel with the pattern, and the conventions around it do not. A template written for Go’s ReplaceAllString meets JavaScript’s rules in re2js’s default mode, and the README says nothing about the empty-match rule of the last section, so both belong in a differential test: the same patterns and the same texts through both engines, with every output compared, as the porting lesson builds one. Its RE2Set is a match setmatch set: A group of patterns compiled together so that one pass over a text reports which of them match, as RE2::Set in RE2 and RE2Set in re2js do. Go's regexp package has no such type., the idea behind RE2’s own RE2::Set: many patterns compiled together and checked in one pass, which Go’s standard package does not offer.

Practise: filters that Go can compile

The exercise asks for five filters over an access log, written in JavaScript or Python, where every pattern must also be one Go would compile. Its sample tests check the lines each filter keeps and search each pattern for the constructs of the first section, and two of the filters need a few lines of code beside their pattern.

09:14:04 ERROR POST /cart 503 1240ms req=b7c2
09:14:07 FATAL POST /pay 500 2050ms req=e5f6 retry=e5f6

// filters.mjs: five filters over the lines of an access log. Every pattern they use must be one that Go's regexp
// would compile too, so that the Go service can run the same rules. Keep each pattern in PATTERNS: the tests read it.

// Starter: these patterns work in JavaScript, but two of them use constructs Go refuses, and some filters keep the
// wrong lines.
export const PATTERNS = {
  failure: /ERROR|FATAL/,
  serverError: / 5\d\d/,
  slow: / [1-9]\d{3}ms/,
  notHealth: /^(?!.* \/health)/,
  retry: / req=(\w+) retry=\1/,
};

/** The lines whose level is ERROR or FATAL. */
export function failures(lines) {
  return lines.filter((line) => PATTERNS.failure.test(line));
}

/** The lines whose status is from 500 to 599. */
export function serverErrors(lines) {
  return lines.filter((line) => PATTERNS.serverError.test(line));
}

/** The lines whose request took 1000 ms or more. */
export function slow(lines) {
  return lines.filter((line) => PATTERNS.slow.test(line));
}

/** Every line except the requests for /health and the paths below it. */
export function withoutHealthChecks(lines) {
  return lines.filter((line) => PATTERNS.notHealth.test(line));
}

/** The lines whose retry= id is exactly their own req= id. */
export function retries(lines) {
  return lines.filter((line) => PATTERNS.retry.test(line));
}

import { test, assert } from 'mysmartcopilot:test';
import { PATTERNS, failures, serverErrors, slow, withoutHealthChecks, retries } from './filters.mjs';

const LOG = [
  '09:14:03 INFO GET /orders/42 200 31ms req=a1f3',
  '09:14:04 ERROR POST /cart 503 1240ms req=b7c2',
  '09:14:05 INFO GET /health 200 2ms req=c9d0',
  '09:14:06 WARN GET /orders/43 404 18ms req=d4e1',
  '09:14:07 FATAL POST /pay 500 2050ms req=e5f6 retry=e5f6',
  '09:14:08 INFO GET /docs/ERROR 200 512ms req=f0a1',
  '09:14:09 INFO GET /health/db 200 3ms req=a2b3',
  '09:14:10 INFO GET /healthcare/plans 200 999ms req=b3c4',
  '09:14:11 WARN POST /pay 502 1000ms req=c4d5 retry=c4d6',
  '09:14:12 INFO POST /pay 200 12000ms req=ab12 retry=ab123',
];

// The lines with these numbers, counting from 1, in order.
const lines = (...numbers) => numbers.map((n) => LOG[n - 1]);

// The constructs Go's regexp refuses to compile, found in the source text of a pattern.
function notInGo(source) {
  const found = [];
  const kept = source.replace(/\\\\/g, ''); // an escaped backslash starts nothing
  const plain = kept.replace(/\\./g, '_'); // an escaped character is a literal
  if (/\\[1-9]|\\k</.test(kept) || /\(\?P=/.test(plain)) found.push('a backreference');
  if (/\(\?<?[=!]/.test(plain)) found.push('a lookaround');
  if (/\(\?>/.test(plain)) found.push('an atomic group');
  if (/[*+?}]\+/.test(plain)) found.push('a possessive quantifier');
  return found;
}

test('failures: the level is ERROR or FATAL, not a word in the path', () => {
  assert.deepEqual(failures(LOG), lines(2, 5));
});

test('serverErrors: a status from 500 to 599, not a duration such as 512ms', () => {
  assert.deepEqual(serverErrors(LOG), lines(2, 5, 9));
});

test('slow: 1000 ms or more, with no upper limit', () => {
  assert.deepEqual(slow(LOG), lines(2, 5, 9, 10));
});

test('withoutHealthChecks: drops /health and /health/db, keeps /healthcare/plans', () => {
  assert.deepEqual(withoutHealthChecks(LOG), lines(1, 2, 4, 5, 6, 8, 9, 10));
});

test('retries: the retry= id is exactly the req= id', () => {
  assert.deepEqual(retries(LOG), lines(5));
});

test('every pattern in PATTERNS is one Go would compile', () => {
  const names = Object.keys(PATTERNS);
  assert.ok(names.length >= 5, 'PATTERNS should hold the pattern of every filter');
  for (const name of names) {
    const pattern = PATTERNS[name];
    assert.ok(pattern instanceof RegExp, `PATTERNS.${name} should be a regular expression`);
    assert.deepEqual(notInGo(pattern.source), [], `PATTERNS.${name} is /${pattern.source}/`);
  }
});

"""filters.py: five filters over the lines of an access log. Every pattern they use must be one that Go's regexp
would compile too, so that the Go service can run the same rules. Keep each pattern in PATTERNS: the tests read it."""

import re

# Starter: these patterns work in Python, but two of them use constructs Go refuses, and some filters keep the wrong
# lines.
PATTERNS = {
    "failure": re.compile(r"ERROR|FATAL"),
    "server_error": re.compile(r" 5\d\d"),
    "slow": re.compile(r" [1-9]\d{3}ms"),
    "not_health": re.compile(r"^(?!.* /health)"),
    "retry": re.compile(r" req=(\w+) retry=\1"),
}


def failures(lines):
    """The lines whose level is ERROR or FATAL."""
    return [line for line in lines if PATTERNS["failure"].search(line)]


def server_errors(lines):
    """The lines whose status is from 500 to 599."""
    return [line for line in lines if PATTERNS["server_error"].search(line)]


def slow(lines):
    """The lines whose request took 1000 ms or more."""
    return [line for line in lines if PATTERNS["slow"].search(line)]


def without_health_checks(lines):
    """Every line except the requests for /health and the paths below it."""
    return [line for line in lines if PATTERNS["not_health"].search(line)]


def retries(lines):
    """The lines whose retry= id is exactly their own req= id."""
    return [line for line in lines if PATTERNS["retry"].search(line)]

import re

from filters import PATTERNS, failures, retries, server_errors, slow, without_health_checks

LOG = [
    "09:14:03 INFO GET /orders/42 200 31ms req=a1f3",
    "09:14:04 ERROR POST /cart 503 1240ms req=b7c2",
    "09:14:05 INFO GET /health 200 2ms req=c9d0",
    "09:14:06 WARN GET /orders/43 404 18ms req=d4e1",
    "09:14:07 FATAL POST /pay 500 2050ms req=e5f6 retry=e5f6",
    "09:14:08 INFO GET /docs/ERROR 200 512ms req=f0a1",
    "09:14:09 INFO GET /health/db 200 3ms req=a2b3",
    "09:14:10 INFO GET /healthcare/plans 200 999ms req=b3c4",
    "09:14:11 WARN POST /pay 502 1000ms req=c4d5 retry=c4d6",
    "09:14:12 INFO POST /pay 200 12000ms req=ab12 retry=ab123",
]


def lines(*numbers):
    """The lines with these numbers, counting from 1, in order."""
    return [LOG[n - 1] for n in numbers]


def not_in_go(source):
    """The constructs Go's regexp refuses to compile, found in the source text of a pattern."""
    found = []
    kept = source.replace("\\\\", "")  # an escaped backslash starts nothing
    plain = re.sub(r"\\.", "_", kept)  # an escaped character is a literal
    if re.search(r"\\[1-9]|\\k<", kept) or "(?P=" in plain:
        found.append("a backreference")
    if re.search(r"\(\?<?[=!]", plain):
        found.append("a lookaround")
    if "(?>" in plain:
        found.append("an atomic group")
    if re.search(r"[*+?}]\+", plain):
        found.append("a possessive quantifier")
    return found


def test_failures():
    """failures: the level is ERROR or FATAL, not a word in the path"""
    assert failures(LOG) == lines(2, 5)


def test_server_errors():
    """server_errors: a status from 500 to 599, not a duration such as 512ms"""
    assert server_errors(LOG) == lines(2, 5, 9)


def test_slow():
    """slow: 1000 ms or more, with no upper limit"""
    assert slow(LOG) == lines(2, 5, 9, 10)


def test_without_health_checks():
    """without_health_checks: drops /health and /health/db, keeps /healthcare/plans"""
    assert without_health_checks(LOG) == lines(1, 2, 4, 5, 6, 8, 9, 10)


def test_retries():
    """retries: the retry= id is exactly the req= id"""
    assert retries(LOG) == lines(5)


def test_every_pattern_compiles_in_go():
    """every pattern in PATTERNS is one Go would compile"""
    assert len(PATTERNS) >= 5, "PATTERNS should hold the pattern of every filter"
    for name, pattern in PATTERNS.items():
        assert isinstance(pattern, re.Pattern), f"PATTERNS[{name!r}] should be a compiled pattern"
        assert not_in_go(pattern.pattern) == [], f"PATTERNS[{name!r}] is {pattern.pattern!r}"

Then comes the self-check. It asks first about the idea you have shown least so far, and every choice it offers says why it is right or what it misses:

Interview questions

Warm-up: which constructs does Go’s regexp refuse, and what does it get in return?

It refuses whatever needs more than a set of positions to match: backreferences such as \1 and \k<name>, lookahead and lookbehind, possessive quantifiers and atomic groups, a few escapes such as \Z, \G and \X, the x flag, and counted repetitions above 1,000. In return the package can promise that a match takes time linear in the length of the text, whatever the pattern, because it follows every path through the compiled pattern at once instead of trying one and backing up. regexp.Compile returns the refusal as an error, such as invalid or unsupported Perl syntax, so a bad pattern is caught when the program builds it. A lookbehind gives a misleading message, invalid named capture, because (?< starts a named group in Go. Whatever a refused construct did moves into code: a second pattern, or a comparison of two groups.

Two design questions take these rules into real work: moving a text-rewriting job from Python to Go, and letting users type their own filter patterns. Each row below opens on its first step; decide yours before you read it.

Key takeaways

• Go’s regexp bounds every match by the compiled pattern’s size times the text’s length, because it follows all paths at once, and pays for it by refusing backreferences, lookaround, possessive and atomic forms and counts above 1,000 when the pattern compiles.
• The finding methods are named Find or FindAll, then String, Submatch and Index, and FindAllStringSubmatchIndex returns byte offsets in pairs, group k at places 2k and 2k + 1, with -1 for a group that took no part.
• In a Go template, $name takes the longest name it can, so $1xxxx deletes text without an error; ${1}, $$, ReplaceAllLiteralString and ReplaceAllStringFunc say what you mean.
• Go ignores an empty match that starts where the previous match ended, so a* gives -b-c- on baac where JavaScript and Python give -b--c-, and + makes the three agree.
• CompilePOSIX and Longest switch Go to leftmost-longest matching, and (?U) makes quantifiers lazy by default, which is not what the same flag means in Java.
• re2js carries RE2’s syntax and linear bound into the browser with JavaScript-style replacement strings, so a pattern shared with Go needs a differential test of its outputs.