# gizlang:regex regular expressions with JavaScript's syntax and match results (leftmost match; alternatives and quantifiers prefer as written; lazy quantifiers; capture groups) over UTF-8 text, in time linear in the text. Structure (as RE2 and Rust's regex): a pattern parses to a tree over code-point sets. The tree compiles to a program over bytes: each set becomes the UTF-8 sequences of its code points, so every automaton reads one byte a step through a table of byte classes. regex() builds the automata of the pattern once and keeps them in the Regex value: - a DFA without captures (test, count, the end of a match); - a tagged DFA (Laurikari) that also keeps the capture positions in registers, with copy and set operations on its transitions, so exec finds the start, the end and the groups in one pass; both with a bounded number of states built ahead. A search that needs a state outside them adds it to its own copy (a lazy DFA whose cache is bounded and starts over when full, as in RE2). An assertion that one byte of look-ahead cannot decide uses a bounded backtracker that replays the program, each (instruction, position) at most once. So no pattern takes more than time linear in the text (there are no backreferences and no lookaround, as in RE2). Before the automata: a literal pattern is a substring search, an anchored literal is a comparison, literal alternatives use selective byte scans, a literal-delimited lazy single-set loop searches its delimiters directly, and a start state jumps to the next byte that can begin a match, or to a prefix. Syntax: JavaScript's (the one parser of ECMAScript mode below, in its Annex B form over code points): literals, `.`, classes, escapes, groups `(...)` `(?:...)` `(?...)`, modifiers `(?i:...)`, `|`, quantifiers with a lazy `?`, ^ and $. The parser marks the features a pattern uses (ES_USES); regex() refuses those the automata cannot run: lookaround, backreferences, a bound over 1000. Flags: `i` (ASCII case-insensitive), `s` (`.` takes line terminators), `m` (^ and $ at line terminators), `y` (a match starts only at the search position), and `g` and `u`, accepted as no-ops (every search API here is global; text is always Unicode). Anything else is an error, never a silent difference. ECMAScript mode (esCompile, EsRegex.exec, checkPattern, at the end of this file) is the JavaScript RegExp: the whole grammar of ECMA-262 over UTF-16 code units. A pattern the parser marked with none of ES_NOT_LINEAR runs on the automata above; the rest on a backtracking matcher. ```gizlang import * as Regex from "gizlang:regex"; ``` ## Types ### `RegexError` ```gizlang type RegexError = { offset: i64; message: string; } ``` A pattern that does not compile: the offset and what is wrong. - `offset`: `i64` - `message`: `string` ### `Match` ```gizlang type Match = { start: i64; end: i64; slots: Vec; } ``` A match: byte offsets of the whole match and, through group(i), of each capture group (none for a group that did not take part). - `start`: `i64` - `end`: `i64` - `slots`: `Vec` ### `Regex` ```gizlang type Regex ``` A compiled pattern. A search reads the tables of its automata as they are; it copies an automaton only when it needs a state that is not built yet. The tables are in the one item of `_parts`: a view of a field of a record in a Vec is a pointer into the Vec, while a view of a field of a record value makes the whole record take memory first. Opaque: create and use it through this module's functions. ### `EsRegex` ```gizlang type EsRegex ``` A compiled ECMAScript pattern. `groupNames[i]` is the name of group i (1-based; "" when unnamed; index 0 unused). Matching returns slots: start and end of the match and of each group, -1 for a group that did not take part. - `groupCount`: `i64` - `groupNames`: `Vec` - `unicode`: `bool` - `hasNames`: `bool` ### `EsText` ```gizlang type EsText = { text: bytes; ascii: bool; plain: bool; } ``` INPUT's UTF-8 for the automata: PLAIN when it holds no surrogate (otherwise the backtracker searches), ASCII when every unit is one byte. A caller searching one string often keeps it (EsRegex.execText). - `text`: `bytes` - `ascii`: `bool` - `plain`: `bool` ## Functions ### `literal` ```gizlang function literal(text: string): Regex ``` A regex literal `/pattern/flags`, its text as written (compiler: parser), compiled; one that does not compile faults, as TypeScript refuses it. Effects: fail. ### `regex` ```gizlang function regex(pattern: string, flags: string): Regex throws RegexError ``` Compiles `pattern` with `flags`; the error's offset is in bytes. Effects: fail. ### `canonicalize` ```gizlang function canonicalize(unicode: bool, c: i64): i64 ``` Canonicalize (22.2.2.7.3): simple case folding with u or v, else the single-unit toUppercase of the character (kept when the uppercase is longer, or moves a non-ASCII character into ASCII). Effects: fail. ### `esText` ```gizlang function esText(input: Vec): EsText ``` The EsText of INPUT: not plain (and empty) when it holds any surrogate. Effects: fail. ### `esCompile` ```gizlang function esCompile(source: Vec, flags: string): EsRegex throws RegexError ``` Compile SOURCE (UTF-16 code units of the pattern) with FLAGS (any of dgimsuyv). Effects: fail. ### `checkPattern` ```gizlang function checkPattern(source: Vec, flags: string): bool throws string ``` The early errors of a regular expression literal (13.2.7.2): whether SOURCE and FLAGS compile. Effects: fail. ## Methods ### `Match.group` ```gizlang function Match.group(self: Match, index: i64): Option ``` The span of capture group INDEX (0 is the whole match), or none when it did not take part in the match. Effects: fail. ### `Regex.test` ```gizlang function Regex.test(self: Regex, text: string): bool ``` Whether the pattern matches somewhere in TEXT. Effects: fail. ### `Regex.exec` ```gizlang function Regex.exec(self: Regex, text: string, from: i64): Option ``` The first match at or after byte `from`, with its groups. Effects: fail. ### `Regex.matchAll` ```gizlang function Regex.matchAll(self: Regex, text: string): Vec ``` Every match, left to right and not overlapping, with groups. Effects: fail. ### `Regex.count` ```gizlang function Regex.count(self: Regex, text: string): i64 ``` How many matches matchAll finds; only the DFA runs unless a match can be empty. Effects: fail. ### `Regex.replaceAll` ```gizlang function Regex.replaceAll(self: Regex, text: string, replacement: string): string ``` The text with every match replaced: in `replacement`, $& is the match, $1 to $99 a group (empty when it did not take part), $$ a dollar sign. Effects: fail. ### `Regex.split` ```gizlang function Regex.split(self: Regex, text: string): Vec ``` The text between matches (groups are not included). Effects: fail. ### `EsRegex.linearFor` ```gizlang function EsRegex.linearFor(self: EsRegex, sticky: bool): bool ``` Whether the automata search this pattern from an exec with STICKY, so execText takes a plain ASCII EsText alone. ### `EsRegex.exec` ```gizlang function EsRegex.exec(self: EsRegex, input: Vec, start: i64, sticky: bool): Option> ``` The first match of this pattern in INPUT at or after START (only at START when STICKY): the start and end of the match and of each group, -1 for an unmatched group. Effects: fail. ### `EsRegex.execText` ```gizlang function EsRegex.execText(self: EsRegex, input: Vec, t: EsText, start: i64, sticky: bool): Option> ``` EsRegex.exec on a subject already prepared by esText. Effects: fail.