std/regex

6 exports, from std/regex.vyrn.

A regular expression that searches, counts and replaces.

=~ only answers whether a whole string matches a constant pattern. The walk is Vyrn, not a builtin, so every engine runs one source and agrees on offsets and counts.

Supports literals, ., classes ([abc], [a-z], [^>]), alternation, grouping, * + ?, and \ escapes. A Thompson NFA with no backtracking, so the time is linear in the pattern size times the input for every pattern. A search runs it as a lazy DFA: one table read per byte. Refuses anchors, non-greedy repeats and counted repetition. It has no backreferences or lookaround: \1 is the byte 1.

Leftmost-longest (POSIX): a|ab against ab matches ab, where a backtracking engine answers a.

Offsets are bytes, and every match starts and ends on a character boundary: . and a negated class match one whole UTF-8 character. A class that lists a non-ASCII character is a set of its bytes.

Dependencies

The import graph shows the whole library.

Imports: strings
Imported by: no other std module

Regex type

type Regex = {
    op: Array<Int64>,
    a: Array<Int64>,
    b: Array<Int64>,
    cls: Array<ByteSet>,
    start: Int64,
    // `classOf[c]` is byte `c`'s class, 0 to `classCount - 1`: two bytes in one
    // class take the same step from every set of pcs. The class of `c` is at
    // most `c`, so a `UInt8` holds it.
    classOf: Array<UInt8>,
    classCount: Int64,
}

Match type

type Match = { at: Int64, end: Int64 }

One match: a half-open byte range of the haystack.

compile fn

fn compile(pattern: String) -> Result<Regex, String>

Compiles pattern, or says what is wrong with it. Compile once and search often: the whole cost of a pattern is paid here.

find fn

fn find(re: Regex, hay: String, from: Int64) -> Option<Match>

The first match at or after from, or None.

countMatches fn

fn countMatches(re: Regex, hay: String) -> Int64

How many non-overlapping matches re has in hay: aa in aaa is one. An empty match advances by one byte.

replaceAll fn

fn replaceAll(re: Regex, hay: String, with: String) -> String

hay with every non-overlapping match replaced by with, taken literally: there are no captures, so no $1.

Tests

12 test blocks in std/regex.vyrn. CI runs all of them.

Test names

a literal is found, counted and replaced
alternation takes the longest branch, which is POSIX's rule
a class matches its members and a negated one everything else
a dot and a negated class match a whole character
the three repeats
a star is greedy
an escape is the byte after it, not the metacharacter
the patterns regex-redux counts
a group is a term the repeats apply to
find says where, and searching from there finds the next
what it refuses, it refuses by name
the lazy DFA finds every match the Thompson simulation finds

Examples

1 program in examples/ import this module. Each runs as WebAssembly and as a native binary.

examples/regexredux.vyrn