regex

Regular Expressions, Compiled — machines/regex.shoddy

Summary

Until this machine there was no pattern matching anywhere in the tree. str is literal throughout: Split cuts on a fixed separator, Replace swaps fixed text, and StartsWith compares a fixed prefix. The builtins underneath are literal too. So a caller faced a log line, a CSV field to validate, a config file of KEY = value, or a URL to pick apart — and the answer was made of Instr and Mid and an off-by-one.

regex is regular expressions — text patterns that describe which strings match — as a compiled value. RxRead parses a pattern to a tree, compiles the tree to a small instruction program, and hands the program back. Every match word takes that program, not a string. A virtual machine — a small program-runner built in software — runs the program over a subject. It advances one code unit at a time and never backtracks: it never backs up to retry an earlier choice.

Two promises follow from that. They are the reason to read further before reaching for a familiar dialect.

No input can end your session. There is not one call to Error in the file. A malformed pattern is Err(why, at) on the language's own Result. An absent match or an unset group is None() on its Option. There is no third outcome. This is the promise cuttle and reckoner already make, adopted here because these words are destined for the same keyboard. It is also why the errors page has no row for this machine. There is nothing to put in it.

No input can take exponential time. Matching cost is bounded by pattern size times subject length. The standard witness (a|a)*b against thirty as explores 2³⁰ paths in a backtracking engine. Here it returns at once, because there is no backtracking to be exponential in.

The price comes in the same breath: no backreferences, no lookaround. Those are not "not yet". They are the exact things a parallel state set structurally cannot express, and they are what buys the guarantee. Both are refused by name, at the offset where they were written.

The Story Behind the Machine

Stephen Kleene wrote Representation of Events in Nerve Nets and Finite Automata at RAND in 1951. Kleene was describing what a network of idealised neurons could recognise. The answer needed a notation, so he wrote one — and the operation that repeats an event any number of times still carries his name every time anyone types a star.

Ken Thompson, at Bell Labs, published Regular Expression Search Algorithm in CACM, June 1968. The part worth this section is not that he implemented Kleene's notation but how. Thompson did not interpret the pattern. He compiled it, at run time, into IBM 7094 machine code, and ran the input through the code. The parallel state set that makes the method linear follows from compiling to a program rather than walking a tree. The live states are the instructions the processor is currently inside. There is nowhere for a backtracker's stack to live, because there is no backtracker.

From there it went into ed, an early text editor. Its command g/re/p — globally, on lines matching this regular expression, print — was used often enough to be given its own name and its own file. Russ Cox's Regular Expression Matching Can Be Simple And Fast (2007) is the modern account. It is also the reason the variant used here is called a Pike VM — an engine that carries a list of live match threads forward instead of backtracking.

It is the right story for this tree twice over. A machine whose mill weaves Shoddy to C# and hands it to Roslyn is in no position to be precious about compiling a pattern to a program. And the ceiling this page states — no backreferences — is not an accident of effort or a corner left unfinished. It is the exact thing Thompson's construction cannot express, and the reason it can promise what a backtracker cannot. The limit and the guarantee are the same fact, read from two sides.

Why It's Useful

A rule you can state is a rule you can read back. Compare a postcode check written with Instr and Mid and three nested Ifs against the same check written as ^[A-Z]{1,2}\d[A-Z\d]? \d[A-Z]{2}$. The second one is the rule. A reader who has never seen the code can tell you whether it is right. That is most of what this machine is for.

It opens up three shapes of work, none of which the tree could do before:

Validation with a stated rule. An ISO date, an MPS row name, a KEY=VALUE line, a version number — asked as the rule rather than reconstructed from primitives.
Field extraction from semi-structured text. Log lines, netstat output, HTTP headers already fetched by https: anything regular that is not JSON, XML, HTML or CSV, all four of which the tree reads properly with their own machines.
Splitting on a rule. RxSplit on "runs of whitespace or a comma" is one call; with a literal separator it is three passes and a judgement call about which one wins.

And, seeded at the reckoner's keyboard: a calculator that can grep its own tape. RckTape is a List Of String, so RXFINDALL at a prompt makes the session's own record searchable.

Guide

Read the pattern once, match many times. RxRead is the only word here that can fail, and it answers the language's Result:

Include "regex.shoddy"

Def Main()
    Select Case RxRead("(\w+)@(\w+\.\w+)", RxNoOpts())
        Case Ok(p)
            Print(RxTest(p, "write to me@example.com today"))    ' True
            Print(RxReplace(p, "a@b.c and d@e.f", "<$1 at $2>"))
        Case Err(why, at)
            Print(why & " at " & Str(at))

That Select Case is the whole ceremony, and it is paid once per pattern rather than once per call. There is deliberately no aborting twin — no RxParse that dies on a bad pattern so you can skip the match. alg, json, xml and csv each pair a total reader with an aborting *Parse. This machine knowingly departs from that house form. Those four read documents a program usually hard-codes; this one reads patterns a session usually types.

Asking. RxTest answers whether there is a match anywhere. RxFind answers the leftmost one as an Option, and takes no offset at all. That is the point of its existing beside RxFindFrom: the overwhelmingly common call has no argument that can be out of range. RxMatchAt is anchored at exactly one offset. RxFindAll answers every non-overlapping match.

Select Case RxFind(p, s)
    Case Some(h)
        Print(RxHitAt(h) & " for " & RxHitLen(h) & ": " & RxHitText(h))
    Case None
        Print("no match")

Captures, and the distinction worth having. A hit carries its span, its text, and one capture per capturing group — a capturing group is a parenthesised part of the pattern whose matched text is saved. There are always exactly RxCount(p) captures, in group order, never a short list. A group that did not participate is unset, which is not the same as a group that matched nothing:

Pattern and subject	Group 1	Group 2
`(a)\|(b)` against `"b"`	`None()` — never entered	`Some("b")`
`(a?)` against `""`	`Some("")` — entered, matched nothing	—

"Did not participate" and "matched nothing" are different facts, and the type keeps them different. RxGroup(h, n) reads one by number and answers Option Of String accordingly. Group 0 is the whole match, so it agrees with $0 in a template.

Rewriting. RxReplace does every match, RxReplaceFirst only the first. In a replacement, $0 is the whole match and $1–$9 are groups. $$ is a literal dollar, and so is a $ in front of anything else. A reference to an unset or nonexistent group expands to the empty string. The alternative would make RxReplace answer a Result, so that every caller matched on a failure mode which only fires when a group legitimately did not participate. RxReplaceWith takes a quotation per hit. It is the escape hatch for anything a template cannot say.

RxReplaceWith(p, s, Fn(h) => Upper(RxHitText(h)))

Options. RxNoOpts() is everything off. RxFoldOpts() turns on ASCII case folding — treating capital and small letters as the same. The record RxOpts(fold, dotAll, multiline) sets all three at once. The same three can be written as a prefix on the pattern itself — (?i), (?s), (?m) and their combinations. Where both are given the prefix wins, whole: it replaces the options argument rather than merging with it, because a rule that replaces is one a caller can state.

Escaping. RxQuote turns a string into a pattern that matches itself and nothing else. Use it any time part of a pattern came from somewhere you do not control.

Seeing the program. RxDisasm answers the compiled program as printable lines. It is not decoration. It is how a surprising answer gets diagnosed, and it is what "compiled to a program" actually means here.

Each(RxDisasm(p), Print)     ' for a(b|c)*

   1  SAVE   0
   2  CHAR   97 a
   3  SPLIT  4, 11
   4  SAVE   2
   5  SPLIT  6, 8
   6  CHAR   98 b
   7  JMP    9
   8  CHAR   99 c
   9  SAVE   3
  10  JMP    3
  11  SAVE   1
  12  MATCH

Slots 0 and 1 are the whole match, so capturing group k uses 2k and 2k+1. A SPLIT always explores its first target first. A lazy quantifier — one that matches as little as it can, where a greedy one matches as much as it can — is the same code with those two targets swapped. That is the entire difference between greedy and lazy anywhere in the machine.

What This Cannot Do

The ceiling is stated here rather than discovered. Most of it is the price of the guarantee rather than a gap in the work.

Refused by name, at the offset where it was written. Each of these produces an Err that says what it is, not "unexpected character":

Construct	Why not
Backreferences `\1`, `\k<n>`	The engine does not backtrack. A backreference needs the engine to remember where it has been, in a way a parallel state set structurally cannot.
Lookahead `(?=` `(?!`	The same reason, forwards.
Lookbehind `(?<=` `(?<!`	The same reason, backwards; the engine reads forward only.
Atomic groups `(?>`, possessive `a*+`	Both forbid backtracking that never happens.
Named groups `(?<name>`	Groups are numbered by opening paren, left to right, from 1.
Conditionals, recursion `(?R)`	Far past what this is; both need a second engine.
`\A \z \Z \G`	Write `^` and `$`; there is no carried match anchor.
POSIX classes `[:alpha:]`, Unicode properties `\p{L}`	The character domain is ASCII-classed — below.
The `x` (extended) flag	There is no whitespace-insensitive mode.
Scoped inline flags `(?i:...)`, `a(?i)b`	Flags are a prefix of the whole pattern and nowhere else. A scoped flag means threading a mode through the compiler and compiling classes differently per branch.

Implementing them means a second engine and a per-pattern choice between the two. That is how real libraries do it, and exactly the complexity this machine exists instead of. Refusing by name means a caller learns the ceiling from the tool rather than from a wrong answer.

The character domain is UTF-16 code units, classed as ASCII. A code unit is one 16-bit piece of a string — the unit Len, Mid, Instr and Codes count in the runtime, so subjects and patterns are indexed the same way. A non-BMP character — one outside the basic 16-bit range — is two code units, and . matches one of them. \d is 0–9. \w adds A–Z, a–z and _. \s is tab, LF, VT, FF, CR and space. Case folding maps A–Z to a–z and nothing else. That is exactly what the runtime's own Upper and Lower do, so no Turkish-dotless caveat is needed here: no such folding is claimed. Codepoint-level matching would need a codepoint-level Mid in the runtime, which is a different proposal.

NUL is matchable, and a reader who knows Chr(0) is the empty string should not assume otherwise. NUL is the character whose code is zero. Codes reports a NUL code unit as 0 like any other, and FromCodes builds one, so a Shoddy string can carry a NUL. The engine compares numbers, so it matches a NUL with no special case at all. \0 and \x00 are ordinary literals here. The one obligation that creates falls on the machine, which never calls Chr: a code turned into a character through Chr would lose a NUL silently and put the hole back.

Leftmost-first, not leftmost-longest. Among matches starting at the earliest position, the answer is the one a backtracker would have found first. Alternation prefers its left branch. A greedy quantifier prefers one more repetition, a lazy one prefers one fewer, applied outside-in. The one-line witness: a|ab against "abc" matches "a", not "ab". This is Perl and PCRE semantics rather than POSIX's, and it is what makes a lazy quantifier mean anything at all.

The empty-match rule, worked. A pattern that can match empty would otherwise make every all-matches word run forever. After a match of length 0 at k, the next search starts at k+1. After a match of length greater than 0 ending at k, the next search also starts at k+1, so matches never overlap. The number of matches over a subject of length n is therefore at most n+1, always. This is the one result callers find surprising, so here it is in full — RxFindAll of a* over "baa" is three hits, not two and not one:

#	Search starts at	Match	Next start
1	1	`""`, length 0 (the `b` is not an `a`)	2, by the empty rule
2	2	`"aa"`, length 2, ending at 3	4, by the non-overlap rule
3	4	`""`, length 0 — position `Len(s) + 1`, past the end	5, which stops the walk

RxFindAll, RxReplace and RxSplit all share one match walk, so all three obey this identically. Implemented three times it would agree twice.

An out-of-range search start is clamped, and that is a contract rather than a mask. A start below 1 is clamped to 1, and a fractional one is floored. Both rules are stated here, and both produce the value the caller meant. A start past Len(s) + 1 answers None(), which is a true statement: nothing starts there. The standing objection to silent masking is a plausible wrong answer three words from its cause — and a search start below 1 has exactly one sensible reading.

The size ceiling is quadratic in the pattern, not in the subject. Per subject position, the machine sweeps every instruction it can reach without consuming a character — an epsilon closure — over at most m instructions, with a visited-set test per instruction. The visited set is an array that SetNth clones. So the cost is O(n × m) steps and O(n × m²) cell operations. Measured:

Pattern	Subject	Time
28 instructions — a log-line pattern with four groups	2000 characters	25 ms
204 instructions	1000 characters	693 ms
1994 instructions — `a{1990}b`	1000 characters	3114 ms

So the honest statement of the ceiling is patterns of a few dozen instructions over subjects of a few thousand characters. That is the first row, and it is what the machine is for. Past that the quadratic-in-m term is felt. A counted repetition compiles by duplication, so {m,n} multiplies the program by n. RxMaxCode() caps the compiled program at 2000 instructions and refuses past it at parse time, naming the number rather than building a program the machine would then crawl through. RxMaxPat() caps the pattern text and RxMaxDepth() its nesting, for the same reason.

What is not on the ceiling is any input shape. There is no adversarial subject. No pattern makes the machine take an order of magnitude longer than its size predicts. That is the trade: a modest constant everywhere, in exchange for no cliff anywhere.

And nothing here rewrites any other machine. json, xml, html, csv and mps have hand-written readers because their grammars are not regular; alg and reckoner likewise. None of them is a candidate, and none of them was changed to add this.

Word Reference

Every word is prefixed Rx — types, variants and field accessors included. A field accessor is an exported global word, so an unprefixed Start or Min would become a bare word in every program that includes this machine.

Reading a pattern

Word	What it does
RxRead(pat, how)	The only word here that can fail, and the only `Result` in the machine. `Ok(prog)`, or `Err(why, at)` with `at` the 1-based offset of the offending character — `0` where there is no meaningful position.
RxNoOpts()	Options with everything off: the dot stops at a newline, `^` and `$` are the ends of the whole subject, case is compared exactly.
RxFoldOpts()	The same with ASCII case folding on.
RxOpts(fold, dotAll, multi)	The options record itself, for setting all three at once.
RxMaxCode() / RxMaxPat() / RxMaxDepth()	The three ceilings, so a caller or a suite can ask what the limit is rather than discover it. 2000 instructions, 2000 pattern characters, 100 levels of nesting.

Asking

Word	What it does
RxTest(p, s)	Whether `p` matches anywhere in `s`. `Boolean`.
RxFind(p, s)	The leftmost match, as `Some(hit)` or `None()`. Takes no offset, which is the point of its existing beside the next one.
RxFindFrom(p, s, from)	The leftmost match at or after `from`. A start below 1 is clamped to 1, a fractional one floored, one past the end answers `None()`.
RxMatchAt(p, s, at)	A match anchored at exactly one offset: it starts there or nowhere.
RxFindAll(p, s)	Every non-overlapping match, in order, as a `List Of RxHit`. Obeys the empty-match rule above.

Reading a hit

Word	What it does
RxHitAt(h) / RxHitLen(h) / RxHitText(h)	The 1-based start, the length in code units, and the matched text.
RxHitCaps(h)	The captures, as a `List Of RxCap` — always exactly `RxCount(p)` of them, in group order.
RxGroup(h, n)	One capture by number, as `Option Of String`. Group `0` is the whole match. A group that did not participate and a group that does not exist are both `None()`; `RxCount` tells those two apart.
RxGroupOr(h, n, dflt)	The same with a fallback, for callers that do not need the distinction.
RxGot(at, text) / RxUnset()	The two kinds of capture. `RxUnset()` is not `RxGot(k, "")`.

Rewriting

Word	What it does
RxReplace(p, s, rep)	Every match replaced. `$0`–`$9` and `$$` in the template; an unset or absent group expands to the empty string.
RxReplaceFirst(p, s, rep)	Only the leftmost match replaced.
RxReplaceWith(p, s, f)	A quotation `[ RxHit -- String ]` run per hit — the escape hatch for anything a template cannot say.
RxSplit(p, s)	The pieces between matches, leading and trailing empties kept. A pattern matching the whole subject gives `{ "", "" }`. Capturing groups are not emitted into the result. Python always emits them and JavaScript sometimes does, and both make the return type "sometimes separators, sometimes not". `RxFindAll` is the word for callers who want the separators.

Helping

Word	What it does
RxQuote(s)	`s` escaped so that, used as a pattern, it matches itself and nothing else. Controls and NUL come back as `\xHH`.
RxSource(p)	The pattern text the program was read from.
RxCount(p)	How many capturing groups the pattern has.
RxDisasm(p)	The compiled program as printable lines. It answers them; it does not print them.

Who Uses It

No machine and no mill includes it yet. Its words are already at the reckoner's prompt through its seed, and a mill that puts them to work will appear here.

The Machines It Uses

None — and deliberately so. Every word this machine needs is a builtin: Codes and FromCodes for the character domain, Nth and Dim and SetNth for the program and the visited set, Concat and Prepend and Reverse for the thread lists. So including regex drags nothing else into a program. There is no machine underneath it whose ceiling becomes this one's.