# 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 `(...)` `(?:...)` `(?<name>...)`, 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<i64>; }
```

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<i64>`

### `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<string>`
- `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<u16>): EsText
```

The EsText of INPUT: not plain (and empty) when it holds any surrogate.

Effects: fail.

### `esCompile`

```gizlang
function esCompile(source: Vec<u16>, 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<u16>, 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<Match>
```

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<Match>
```

The first match at or after byte `from`, with its groups.

Effects: fail.

### `Regex.matchAll`

```gizlang
function Regex.matchAll(self: Regex, text: string): Vec<Match>
```

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<string>
```

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<u16>, start: i64, sticky: bool): Option<Vec<i64>>
```

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<u16>, t: EsText, start: i64, sticky: bool): Option<Vec<i64>>
```

EsRegex.exec on a subject already prepared by esText.

Effects: fail.

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 (...) (?:...) (?<name>...), 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<i64>; }

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<i64>

`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<string>
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<u16>): EsText

The EsText of INPUT: not plain (and empty) when it holds any surrogate.

Effects: fail.

`esCompile`

gizlang

function esCompile(source: Vec<u16>, 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<u16>, 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<Match>

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<Match>

The first match at or after byte from, with its groups.

Effects: fail.

`Regex.matchAll`

gizlang

function Regex.matchAll(self: Regex, text: string): Vec<Match>

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<string>

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<u16>, start: i64, sticky: bool): Option<Vec<i64>>

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<u16>, t: EsText, start: i64, sticky: bool): Option<Vec<i64>>

EsRegex.exec on a subject already prepared by esText.

Effects: fail.