regex

stdlib/extra/regex.hk: regular expressions, matched by a Pike VM.

One left-to-right pass over the input drives a set of live threads, and at each position an instruction runs at most once. That dedup is the whole design: matching costs the pattern times the text and no input can make it explode, and (a+)+$ against a long run of as therefore finishes in the time its length suggests and never the time a backtracker would take.

That guarantee is here for HANKI.md §23's reason and no tradition. The step budget (--max-steps) is bytecode-only, which leaves linear time as an AOT binary's one bound between a hostile pattern and unbounded work. A matcher is also the one decoder whose pattern is as likely to be untrusted as its input: every grep-shaped tool takes the pattern from its user.

The price is fixed and worth naming: no backreferences and no lookaround. Both make the language non-regular and cost the guarantee, and both are therefore refused at compile time with an error that says which one and why, and never read as something else.

Syntax

Written out here: every implementation differs at the edges.

abc the scalars a, b, c, in order . any one scalar [a-z0-9_] a class; [^…] inverts it. A ] in first position is a literal ], and a - last is a literal dash \d \w \s digit / word / whitespace, with \D \W \S inverted \n \t \r \0 the control escapes this language can spell \x a literal x, for any metacharacter e1|e2 ordered alternation: the earlier branch wins e e+ e? repetition; e{n}, e{n,}, e{n,m} give it a count e? any quantifier followed by ? is lazy: shortest first (e) a capturing group, numbered by opening parenthesis from 1 (?:e) a group that only groups ^ $ the start and the end of the whole input, never a line \b \B a word boundary and its negation

Matching is over Unicode scalars and never bytes: . is one scalar, and a class range compares scalars, which UTF-8 permits by comparing their text (byte order is code point order). [α-ω] therefore works. The \d/\w/\s shorthands are ASCII, as they are everywhere else in this stdlib. \s is space, tab, newline and carriage return; the form feed and vertical tab are absent because a Hanki string literal cannot spell them.

Bounds

Two, both inherent and neither configurable, and both reported as ordinary compile errors and never as a fault: a pattern may nest 128 deep (json.hk's tradition) and compile to 10000 instructions. Between them they stop a pattern exhausting the host stack on the AOT tier, which no other bound does. Neither bounds matching, which the engine already bounds.

Not in this version

Named groups, a case-insensitive flag, and anchored-search variants are additions for later. Compile is a pure function, and a caller who wants a pattern folded at build time can bind it in meta; there is no separate comptime path to learn.

Replacements

replace and replace_all take a Replacement and no string, built by Regex.replacement against the pattern it will be used with:

$0 the whole match $n the nth group; the digits are read as one number, which puts $12 in reach of a twelve-group pattern $$ a literal dollar

Anything else is literal text. A group that took no part in the match expands to the empty string, as it does everywhere else.

The two steps are what leave replace total. A reference to a group the pattern does not have is a typo in a string the caller wrote, and the only place that can catch it is the one that knows the group count. It is therefore refused when the replacement is built, and never by giving every call site a Result to unwrap. Both steps are pure, and a literal pattern and a literal replacement fold from a top-level binding and the typo becomes a build error.

RegexError

struct RegexError
  at: int
  reason: string
end

Why a pattern would not compile. at is the byte offset the problem was found at, which lets a caller point at it.

impl Display<RegexError>

to_string

def to_string(self) -> string

Renders as <reason> at offset <at>.

RegexError(at=2, reason="nothing to repeat").to_string() => "nothing to repeat at offset 2"

impl Eq<RegexError>

eq?

def eq?(self, other: Self) -> bool

Equal when both the offset and the reason match.

RegexError(at=1, reason="x").eq?(RegexError(at=1, reason="x")) => true

Match

struct Match
  start: int
  stop: int
  text: string
end

Where a match landed: the half-open byte range [start, stop) and the text it covers.

impl Eq<Match>

eq?

def eq?(self, other: Self) -> bool

Equal when the range and the text both match.

Match(start=0, stop=1, text="a").eq?(Match(start=0, stop=1, text="a")) => true

impl Display<Match>

to_string

def to_string(self) -> string

Renders as <text>@<start>..<stop>.

Match(start=1, stop=3, text="bc").to_string() => "bc@1..3"

Captures

struct Captures
  groups: List<Option<Match>>
end

Every group of one match. groups.get(0) is the whole match; group n is the nth ( in the pattern, counted by opening parenthesis.

impl Captures

get

def get(self, index: int) -> Option<Match>

Group index, or None when the index is out of range or that group took no part in the match.

compile("(\\d+)-(\\d+)").map(|r| r.captures("7-42").and_then(|c| c.get(2)).map(|m| m.text)) => Ok(Some("42"))

length

prop length(self) -> int

How many groups this has, including group 0.

compile("(a)(b)").map(|r| r.captures("ab").map(|c| c.length)) => Ok(Some(3))

_ScalarRange

struct _ScalarRange
  lo: string
  hi: string
end

One inclusive scalar range. Scalars compare as single-scalar strings: UTF-8 byte order is code point order, and lo <= c <= hi reads the same on both.

_CharClass

struct _CharClass
  ranges: List<_ScalarRange>
  negated: bool
end

A [...] set: the ranges it admits, and whether membership is inverted.

_Anchor

type _Anchor
  AtStart
  AtEnd
  AtWordBoundary
  AtNotWordBoundary
end

A zero-width assertion.

_Quantified

struct _Quantified
  inner: _Node
  min: int
  max: Option<int>
  lazy: bool
end

A quantified node: inner repeated min to max times, max None meaning unbounded. lazy prefers the shortest match.

_Node

type _Node
  ReEmpty
  ReLiteral(string)
  ReAny
  ReSet(_CharClass)
  ReConcat(List<_Node>)
  ReAlternate(List<_Node>)
  ReRepeat(_Quantified)
  ReGroup(Option<int>, _Node)
  ReAnchor(_Anchor)
end

_Inst

type _Inst
  OpChar(string)
  OpClass(_CharClass)
  OpAny
  OpSplit(int, int)
  OpJump(int)
  OpSave(int)
  OpAssert(_Anchor)
  OpAccept
end

Regex

opaque Regex
  _program: List<_Inst>
  _group_count: int
end

A compiled pattern, ready to match many inputs.

_Part

type _Part
  RepText(string)
  RepGroup(int)
end

One piece of a compiled replacement: text to emit as written, or the group to expand there.

Replacement

opaque Replacement
  _parts: List<_Part>
end

A replacement compiled against a particular pattern, ready to expand against many matches. Built by Regex.replacement, which is where a reference to a group the pattern does not have is refused, which lets replace and replace_all take one of these and be total.

maxdepth

def _max_depth() -> int

How deeply a pattern may nest before compiling is refused.

maxprogram_length

def _max_program_length() -> int

How long a compiled program may get before compiling is refused.

_Step

struct _Step
  text: string
  width: int
end

One scalar and the bytes it occupies.

scalarat

def _scalar_at(s: string, i: int) -> Option<_Step>

The scalar starting at byte offset i, or None at or past the end. slice rounds a mid-scalar stop down, and a too-short window comes back empty and the width grows until the whole scalar fits.

scalarbefore

def _scalar_before(s: string, i: int) -> Option<string>

The scalar ending at byte offset i. slice rounds a mid-scalar start down to the scalar's first byte, and one window is enough.

_absent?

def _absent?<T>(o: Option<T>) -> bool

digitranges

def _digit_ranges() -> List<_ScalarRange>

wordranges

def _word_ranges() -> List<_ScalarRange>

spaceranges

def _space_ranges() -> List<_ScalarRange>

inclass?

def _in_class?(k: _CharClass, c: string) -> bool

wordscalar?

def _word_scalar?(c: string) -> bool

_Parsed

struct _Parsed
  node: _Node
  next: int
  groups: int
end

A parsed subtree: the node, the offset just past it, and how many capturing groups have been allocated up to and including it.

parsealternate

def _parse_alternate(p: string, start: int, groups: int, depth: int) -> Result<_Parsed, RegexError>

e1|e2|…: the top of the grammar, and what a group's body parses as.

parseconcat

def _parse_concat(p: string, start: int, groups: int, depth: int) -> Result<_Parsed, RegexError>

A run of quantified atoms, ending at |, ), or the end of the pattern.

parserepeat

def _parse_repeat(p: string, start: int, groups: int, depth: int) -> Result<_Parsed, RegexError>

An atom and the quantifier that may follow it.

parsequantifier

def _parse_quantifier(p: string, atom: _Parsed) -> Result<_Parsed, RegexError>

_Bounds

struct _Bounds
  min: int
  max: Option<int>
  next: int
end

The {n} / {n,} / {n,m} bounds, read from the opening brace.

parsecounted

def _parse_counted(p: string, brace: int) -> Result<_Bounds, RegexError>

_Digits

struct _Digits
  value: int
  next: int
end

readdigits

def _read_digits(p: string, start: int) -> _Digits

digitvalue

def _digit_value(c: string) -> int

finishquantifier

def _finish_quantifier(p: string, atom: _Parsed, after: int, min: int, max: Option<int>) -> Result<_Parsed, RegexError>

Wrap atom in the quantifier that follows it, and refuse a second one - a** is a typo, and possessive a*+ is not a thing this engine has.

parseatom

def _parse_atom(p: string, i: int, groups: int, depth: int) -> Result<_Parsed, RegexError>

parsegroup

def _parse_group(p: string, open_at: int, groups: int, depth: int) -> Result<_Parsed, RegexError>

_lookbehind?

def _lookbehind?(p: string, open_at: int) -> bool

(?<= and (?<! look behind; (?<name> is a named group, and saying "lookaround" about it would send the reader off after the wrong thing.

nolookaround

def _no_lookaround(at: int) -> RegexError

closegroup

def _close_group(p: string, open_at: int, body_at: int, slot: Option<int>, groups: int, depth: int) -> Result<_Parsed, RegexError>

parseescape

def _parse_escape(p: string, at: int, groups: int) -> Result<_Parsed, RegexError>

_shorthand

def _shorthand(c: string) -> Option<_CharClass>

\d / \w / \s and their negations, as a class.

escapeliteral

def _escape_literal(p: string, at: int) -> Result<_Step, RegexError>

The scalar an escape stands for. A letter or digit that means nothing is an error and never itself, which stops a pattern matching the wrong text unannounced.

escapeother

def _escape_other(p: string, at: int, c: string) -> Result<_Step, RegexError>

The escapes that are not one of the four control spellings: a digit is a backreference, a letter that means nothing is a typo, and anything else - a metacharacter or punctuation, stands for itself.

_alphanumeric?

def _alphanumeric?(c: string) -> bool

parseclass

def _parse_class(p: string, open_at: int, groups: int) -> Result<_Parsed, RegexError>

_ClassScan

struct _ClassScan
  ranges: List<_ScalarRange>
  next: int
end

classranges

def _class_ranges(p: string, start: int, open_at: int) -> Result<_ClassScan, RegexError>

_ClassItem

struct _ClassItem
  shorthand: Option<_CharClass>
  text: string
  next: int
end

One class member: either a shorthand set or a single scalar.

classitem

def _class_item(p: string, i: int) -> Result<_ClassItem, RegexError>

classrange

def _class_range(p: string, lo: _ClassItem, acc: List<_ScalarRange>) -> Result<_ClassScan, RegexError>

A scalar, and the -hi that may follow it. A - right before the closing bracket is a literal dash and no open range.

_size

def _size(n: _Node) -> int

repeatsize

def _repeat_size(q: _Quantified) -> int

_split

def _split(a: int, b: int, lazy: bool) -> _Inst

_emit

def _emit(n: _Node, pc: int) -> List<_Inst>

emitsequence

def _emit_sequence(xs: List<_Node>, pc: int) -> List<_Inst>

emitalternate

def _emit_alternate(xs: List<_Node>, pc: int) -> List<_Inst>

e1|e2|…: a split into the first branch and everything after it, the first branch jumping clear of the rest. Ordered: the earlier branch wins.

emitrepeat

def _emit_repeat(q: _Quantified, pc: int) -> List<_Inst>

emitcopies

def _emit_copies(inner: _Node, pc: int, count: int) -> List<_Inst>

emitstar

def _emit_star(inner: _Node, pc: int, lazy: bool) -> List<_Inst>

emitoptionals

def _emit_optionals(inner: _Node, pc: int, count: int, lazy: bool) -> List<_Inst>

count nested optionals: (x(x)?)? and never x?x?, which leaves the bounded tail of x{n,m} unable to skip an inner copy and take an outer one.

compile

def compile(pattern: string) -> Result<Regex, RegexError>

Compile pattern, or say why it cannot be. Compiling once and matching many times is what to reach for: re-reading the pattern per input would be the dominant cost of any scan over more than a line.

compile("^\\d+$").map(|r| r.matches?("2026")) => Ok(true)
compile("a(").map(|_| "ok").map_err(|e| e.reason) => Err("unclosed group")

escape

def escape(s: string) -> string

Quote every metacharacter in s, which makes the result a pattern matching s alone. The direction a value takes when it was never written as a pattern: a path in a generated pattern, a filename in an alternation, whatever a stranger typed into a search box.

The quoted set is this engine's metacharacters, \\ . ^ $ | ? * + ( ) [ ] { }, and no list borrowed from another. That is not fussiness: a backslash before a letter or digit is a compile error here (\\q is an unknown escape, \\1 a refused backreference), and quoting more than this would produce patterns that do not compile. Quoting less would produce patterns that compile and match the wrong text, which is worse.

escape("hello") => "hello"
escape("") => ""
escape("a.c") => "a\\.c"
escape("/tmp/run.42.log") => "/tmp/run\\.42\\.log"
escape(".*+?") => "\\.\\*\\+\\?"
compile(escape("a.c")).map(|r| r.matches?("a.c")) => Ok(true)
compile(escape("a.c")).map(|r| r.matches?("abc")) => Ok(false)

_metacharacter?

def _metacharacter?(c: string) -> bool

Every scalar _parse_atom and the quantifier parser treat as syntax, plus the two closers that are only syntax inside a class or a repeat but cost nothing to quote and would matter if either grew.

_assemble

def _assemble(root: _Node, groups: int) -> Result<Regex, RegexError>

_Thread

struct _Thread
  pc: int
  slots: Map<int, int>
end

_ThreadList

struct _ThreadList
  threads: List<_Thread>
  seen: Set<int>
end

The threads live at one input position, plus the program counters already added there. The dedup IS the linear-time guarantee: without it a position could run the same instruction once per path that reaches it.

emptylist

def _empty_list() -> _ThreadList

addthread

def _add_thread(program: List<_Inst>, list: _ThreadList, pc: int, slots: Map<int, int>, input: string, pos: int) -> _ThreadList

Follow every zero-width step from pc and park the threads that need input on list. An explicit stack and no recursion: a long chain of splits would otherwise cost host stack proportional to the program.

_holds?

def _holds?(a: _Anchor, input: string, pos: int) -> bool

wordbefore?

def _word_before?(input: string, pos: int) -> bool

wordat?

def _word_at?(input: string, pos: int) -> bool

_consumes?

def _consumes?(program: List<_Inst>, pc: int, s: string) -> bool

Whether the instruction at pc consumes the scalar s.

_run

def _run(program: List<_Inst>, input: string, from: int) -> Option<Map<int, int>>

One left-to-right pass from from, returning the leftmost-first match's slots. Threads run in priority order, and the first OpAccept reached wins and the lower-priority threads behind it are dropped.

parsereplacement

def _parse_replacement(spec: string, groups: int) -> Result<List<_Part>, RegexError>

Compile spec against a pattern with groups capture groups.

$0 is the whole match and $n the nth group; $$ is a literal dollar. The digits after a $ are read as one number, which puts $12 in reach of a pattern with twelve groups, and is why a reference has to be checked and never assumed to be one digit. Everything else is literal text.

Two things are refused here and never at expansion time: a $ that no digit and no second $ follows, and a reference past the pattern's last group. Both are typos in a string the caller wrote, and this is the one place that knows the group count.

_expand

def _expand(parts: List<_Part>, caps: Captures) -> string

parts expanded against one match's groups. A group that took no part in the match expands to the empty string: a valid reference to something that is not there, which is a different thing from the reference errors _parse_replacement refuses.

_advance

def _advance(input: string, m: Match) -> Option<int>

Where the next scan starts after a match ending at m, or None when the scan is done. An empty match advances one scalar, and a pattern that can match nothing still terminates. Shared by every left-to-right walk, since getting this rule wrong in one of them is how such a walk hangs.

slotmatch

def _slot_match(slots: Map<int, int>, input: string, index: int) -> Option<Match>

impl Regex

matches?

def matches?(self, input: string) -> bool

Whether the pattern occurs anywhere in input.

compile("\\bcat\\b").map(|r| r.matches?("the cat sat")) => Ok(true)
compile("\\bcat\\b").map(|r| r.matches?("concatenate")) => Ok(false)

find

def find(self, input: string) -> Option<Match>

The leftmost match, or None.

compile("\\d+").map(|r| r.find("a12b345").map(|m| m.text)) => Ok(Some("12"))
compile("\\d+").map(|r| r.find("abc")) => Ok(None)

find_all

def find_all(self, input: string) -> List<Match>

Every non-overlapping match, left to right. An empty match advances the scan by one scalar, and a pattern that can match nothing still terminates.

compile("\\d+").map(|r| r.find_all("a1b22c333").map(|m| m.text)) => Ok(["1", "22", "333"])

capturesall

def _captures_all(self, input: string) -> List<Captures>

find_all's walk, with each match's groups and not the match itself. Private because replace_all is what needs it: the expansion has to see the slots of the match it is expanding against, and the whole-match walk cannot supply them.

captures

def captures(self, input: string) -> Option<Captures>

The leftmost match with its capture groups.

compile("(\\w+)@(\\w+)").map(|r| r.captures("ada@example").and_then(|c| c.get(1)).map(|m| m.text)) => Ok(Some("ada"))

replacement

def replacement(self, spec: string) -> Result<Replacement, RegexError>

Compile spec as a replacement for this pattern.

$0 is the whole match and $n the nth group; $$ is a literal dollar, and everything else is literal text. The digits after a $ are read as one number, which puts $12 in reach of a twelve-group pattern.

Checking here and never at replace time is what leaves replace total: a reference to a group the pattern does not have is a typo in a string the caller wrote, and this is the only place that knows the group count. compile and this are both pure, and a literal pattern and a literal replacement both fold from a top-level binding and the typo becomes a build error.

compile("(\\w+)").and_then(|r| r.replacement("[$1]").map(|p| r.replace("hi", p))) => Ok("[hi]")
compile("(a)").and_then(|r| r.replacement("$2")).map(|_| "built") => Err(RegexError(at=0, reason="no group 2 in this pattern"))
compile("(a)").and_then(|r| r.replacement("$x")).map(|_| "built") => Err(RegexError(at=0, reason="expected a group number or a second $"))

replace

def replace(self, input: string, replacement: Replacement) -> string

input with the first match replaced by replacement expanded against that match's groups.

compile("(\\d+)").and_then(|r| r.replacement("[$1]").map(|p| r.replace("a1b2", p))) => Ok("a[1]b2")
compile("(\\w+) (\\w+)").and_then(|r| r.replacement("$2 $1").map(|p| r.replace("hello world", p))) => Ok("world hello")

replace_all

def replace_all(self, input: string, replacement: Replacement) -> string

input with every match replaced, each expansion against its own match's groups.

compile("(\\d)").and_then(|r| r.replacement("<$1>").map(|p| r.replace_all("a1b2", p))) => Ok("a<1>b<2>")
compile("\\s+").and_then(|r| r.replacement(" ").map(|p| r.replace_all("a  b   c", p))) => Ok("a b c")

split

def split(self, input: string) -> List<string>

input cut at every match, the matches themselves dropped.

compile(",\\s*").map(|r| r.split("a, b,c")) => Ok(["a", "b", "c"])

_gaps

def _gaps(ms: List<Match>, input: string) -> List<string>

The text between successive matches: one more piece than there are matches, which is what split returns and what replace_all joins the replacement between.

sizeof_source

def _size_of_source(p: string) -> int