regex.bend checks

raw source on the hub · import 0x34608bdcdd8721ab70b875a54ae9beca/regex.bend as Regex

Linear-time regular expressions: RE2 syntax, Pike VM, capture groups. Source: https://github.com/paymog/bend-kit/tree/main/regex

2 imports

import Base
import 0x6c784a08486e2e02415e89c5249e9e8a/unicode.bend as U

Types

type Item source · line 12 · raw

Data

A set member: a code point range, or a Unicode general category ("L", "Lu", ...).

Rng
```
@lo:U32 -> @hi:U32 -> Item
```
Prop
```
@neg:Bool -> @name:String -> Item
```

type Node source · line 17 · raw

Data

Assertion kinds: 0 start of text, 1 end of text, 2 word boundary, 3 not a word boundary.

NEmpty
```
Node
```

NSet

@neg:Bool -> @items:List<&2, Item> -> Node

NAssert
```
@k:U32 -> Node
```
NCat
```
@a:Node -> @b:Node -> Node
```
NAlt
```
@a:Node -> @b:Node -> Node
```
NPlus
```
@greedy:Bool -> @a:Node -> Node
```
NQuest
```
@greedy:Bool -> @a:Node -> Node
```
NGroup
```
@i:U32 -> @a:Node -> Node
```

type Tok source · line 27 · raw

Data

TAtom
```
@n:Node -> Tok
```
TOpen
```
@cap:Bool -> Tok
```
TClose
```
Tok
```
TBar
```
Tok
```

TRep

@min:U32 -> @max:Maybe<&2, U32> -> @greedy:Bool -> Tok

type Esc source · line 73 · raw

Data

EPoint
```
@c:U32 -> @rest:String -> Esc
```

EItems

@items:List<&2, Item> -> @rest:String -> Esc

EAssert
```
@k:U32 -> @rest:String -> Esc
```
EBad
```
Esc
```

type Cs source · line 161 · raw

Data

CsGo

@s:String -> @first:Bool -> @items:List<&2, Item> -> Cs

CsDone

@items:List<&2, Item> -> @rest:String -> Cs

CsFail
```
Cs
```

type Lx source · line 243 · raw

Data

LGo
```
@s:String -> @toks:List<&2, Tok> -> Lx
```
LDone
```
@toks:List<&2, Tok> -> Lx
```
LFail
```
Lx
```

type Num source · line 249 · raw

Data

A run of decimal digits: its value (capped at 100000), its length, and the rest.

Num
```
@v:U32 -> @n:U32 -> @rest:String -> Num
```

type Frame source · line 395 · raw

Data

An open group: its capture index (None for (?:...)), and the enclosing alternatives and sequence.

Frame

@cap:Maybe<&2, U32> -> @alts:List<&2, Node> -> @cur:List<&2, Node> -> Frame

type Ps source · line 399 · raw

Data

n: the next capture index. rep: the last token was a repetition. alts and cur are reversed.

Ps

@n:U32 -> @rep:Bool -> @stack:List<&2, Frame> -> @alts:List<&2, Node> -> @cur:List<&2, Node> -> Ps

PsFail
```
Ps
```

type Inst source · line 532 · raw

Data

ISet

@neg:Bool -> @items:List<&2, Item> -> Inst

IAssert
```
@k:U32 -> Inst
```
ISplit
```
@x:U32 -> @y:U32 -> Inst
```
IJmp
```
@x:U32 -> Inst
```
ISave
```
@k:U32 -> Inst
```
IMatch
```
Inst
```

type Trie source · line 584 · raw

@-V:Data -> Data

A binary trie keyed by n >= 1: the path is the bits of n below its top bit, low bit first, so key n costs log2(n) steps and small keys stay near the root.

TTip
```
@-V:Data -> Trie<V>
```

TNode

@-V:Data -> @val:Maybe<&2, V> -> @lo:Trie<V> -> @hi:Trie<V> -> Trie<V>

type Fs source · line 650 · raw

Data

The walk from pc 0 over the instructions that consume no char: the sets it reaches, or FsAny when it reaches an assertion or a match, so that any char may start a match.

Fs

@stack:List<&2, U32> -> @seen:List<&2, U32> -> @sets:List<&2, Inst> -> Fs

FsAny
```
Fs
```

type Regex source · line 690 · raw

Data

prog: the instructions by pc; fuel: enough steps for one closure; slots: two per group, group 0 included; start: the sets one of which the first char of a match is in, or None when a match may start anywhere.

Regex

@prog:Trie<Inst> -> @fuel:Nat -> @slots:Nat -> @start:Maybe<&2, List<&2, Inst>> -> Regex

type Th source · line 756 · raw

Data

A thread: its pc and its capture slots.

Th

@pc:U32 -> @caps:List<&2, Maybe<&2, U32>> -> Th

type Cl source · line 761 · raw

Data

The epsilon closure as a depth-first walk: stack is the work left, seen the pcs visited at this position, out the threads that wait on a char or match (reversed).

Cl

@stack:List<&2, Th> -> @seen:Trie<Unit> -> @out:List<&2, Th> -> Cl

type Sc source · line 816 · raw

Data

A scan of the threads at one char, in priority order: items are the threads that step past it (reversed), best the latest match. A match drops every later thread.

Sc

@items:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> @stop:Bool -> Sc

type Vm source · line 870 · raw

Data

The live threads and the best match so far.

Vm

@ths:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Vm

type Span source · line 933 · raw

Data

Span
```
@start:U32 -> @end:U32 -> Span
```

Definitions

def lit source · line 34 · raw

@+c:U32 -> Node

def is_digit source · line 37 · raw

@+c:U32 -> Bool

def is_word source · line 40 · raw

@+c:U32 -> Bool

def is_alnum source · line 43 · raw

@+c:U32 -> Bool

def perl.d source · line 47 · raw

List<&2, Item>

\d \w \s are ASCII, as in RE2.

def perl.D source · line 50 · raw

List<&2, Item>

def perl.w source · line 53 · raw

List<&2, Item>

def perl.W source · line 56 · raw

List<&2, Item>

def perl.s source · line 59 · raw

List<&2, Item>

def perl.S source · line 62 · raw

List<&2, Item>

def cats source · line 65 · raw

List<&2, String>

def prop.if source · line 79 · raw

@ok:Bool -> @neg:Bool -> @name:String -> @t:String -> Esc

def prop.ok source · line 86 · raw

@neg:Bool -> @+name:String -> @t:String -> Esc

def prop.name source · line 89 · raw

@s:String -> @neg:Bool -> @acc:String -> Esc

def prop source · line 99 · raw

@neg:Bool -> @s:String -> Esc

\pL or \p{Lu}; \P negates.

def esc.other source · line 109 · raw

@alnum:Bool -> @+c:U32 -> @t:String -> Esc

An escaped letter or digit with no meaning is an error, as in RE2.

def esc source · line 117 · raw

@s:String -> Esc

The text after a backslash.

def class.range source · line 166 · raw

@ok:Bool -> @+c:U32 -> @+d:U32 -> @u:String -> @items:List<&2, Item> -> Cs

def class.hi source · line 173 · raw

@e:Esc -> @+c:U32 -> @items:List<&2, Item> -> Cs

def class.lo source · line 185 · raw

@+c:U32 -> @t:String -> @items:List<&2, Item> -> Cs

c is one member; a "-" and a code point after it make a range.

def class.esc source · line 196 · raw

@e:Esc -> @items:List<&2, Item> -> Cs

def class.step source · line 208 · raw

@s:String -> @first:Bool -> @items:List<&2, Item> -> Cs

A "]" right after "[" or "[^" is a member.

def class.run source · line 224 · raw

@fuel:Nat -> @st:Cs -> Cs

fuel: every step eats at least one char.

def class source · line 237 · raw

@+s:String -> @first:Bool -> Cs

def num.add source · line 252 · raw

@+acc:U32 -> @+c:U32 -> U32

def num.go source · line 255 · raw

@t:String -> @+c:U32 -> @+acc:U32 -> @+n:U32 -> @dig:Bool -> Num

def num source · line 270 · raw

@s:String -> Num

def lex.rep source · line 278 · raw

@+min:U32 -> @max:Maybe<&2, U32> -> @t:String -> @toks:List<&2, Tok> -> Lx

A trailing "?" makes a repetition lazy.

def Num.n source · line 285 · raw

@m:Num -> U32

def lex.brace.max source · line 290 · raw

@none:Bool -> @+min:U32 -> @m:Num -> @orig:String -> @toks:List<&2, Tok> -> Lx

A "{" that does not start {n}, {n,} or {n,m} is a literal, as in RE2.

def lex.brace.min source · line 302 · raw

@none:Bool -> @m:Num -> @+orig:String -> @toks:List<&2, Tok> -> Lx

def lex.class source · line 319 · raw

@neg:Bool -> @r:Cs -> @toks:List<&2, Tok> -> Lx

def lex.esc source · line 328 · raw

@e:Esc -> @toks:List<&2, Tok> -> Lx

def lex.step source · line 339 · raw

@s:String -> @toks:List<&2, Tok> -> Lx

def lex source · line 378 · raw

@fuel:Nat -> @st:Lx -> Maybe<&2, List<&2, Tok>>

fuel: every step but the last eats at least one char.

def cat source · line 402 · raw

@a:Node -> @b:Node -> Node

def seq.go source · line 413 · raw

@xs:List<&2, Node> -> @acc:Node -> Node

def seq source · line 420 · raw

@xs:List<&2, Node> -> Node

def alt.go source · line 423 · raw

@xs:List<&2, Node> -> @acc:Node -> Node

def group source · line 430 · raw

@cap:Maybe<&2, U32> -> @a:Node -> Node

def rep.copies source · line 437 · raw

@k:Nat -> @+h:Node -> @acc:Node -> Node

def rep.opt source · line 444 · raw

@k:Nat -> @+g:Bool -> @+h:Node -> Node

def rep.inf source · line 452 · raw

@k:Nat -> @+g:Bool -> @+h:Node -> Node

x* is (x+)?, so an empty x cannot loop; x{n,} is n-1 copies then x+; x{n,m} is n copies then (x(x...)?)?, as RE2 builds them.

def rep.fin source · line 459 · raw

@max:Maybe<&2, U32> -> @+min:U32 -> @+g:Bool -> @+h:Node -> Node

def rep source · line 466 · raw

@+h:Node -> @+min:U32 -> @max:Maybe<&2, U32> -> @+g:Bool -> Node

def rep.ok source · line 470 · raw

@+min:U32 -> @max:Maybe<&2, U32> -> Bool

Counts go up to 1000, and a repetition cannot repeat, as in RE2.

def parse.rep source · line 477 · raw

@ok:Bool -> @cur:List<&2, Node> -> @+min:U32 -> @max:Maybe<&2, U32> -> @+g:Bool -> @+n:U32 -> @stack:List<&2, Frame> -> @alts:List<&2, Node> -> Ps

def parse.open source · line 488 · raw

@cap:Bool -> @+n:U32 -> @stack:List<&2, Frame> -> @alts:List<&2, Node> -> @cur:List<&2, Node> -> Ps

def parse.close source · line 495 · raw

@stack:List<&2, Frame> -> @+n:U32 -> @alts:List<&2, Node> -> @cur:List<&2, Node> -> Ps

def parse.tok source · line 502 · raw

@tok:Tok -> @+n:U32 -> @rep:Bool -> @stack:List<&2, Frame> -> @alts:List<&2, Node> -> @cur:List<&2, Node> -> Ps

def parse.step source · line 515 · raw

@st:Ps -> @tok:Tok -> Ps

def parse source · line 522 · raw

@toks:List<&2, Tok> -> @st:Ps -> Ps

def size source · line 540 · raw

@n:Node -> U32

def emit source · line 560 · raw

@n:Node -> @+pc:U32 -> @rest:List<&2, Inst> -> List<&2, Inst>

The instructions of n, placed at pc, in front of rest. ISplit tries x first.

def trie.get source · line 589 · raw

@-V:Data -> @t:Trie<V> -> @here:Bool -> @left:Bool -> @+n:U32 -> Maybe<&2, V>

here: n is 1. left: n is even.

def trie.put source · line 605 · raw

@-V:Data -> @fuel:Nat -> @t:Trie<V> -> @here:Bool -> @left:Bool -> @+n:U32 -> @v:V -> Trie<V>

fuel: a U32 key has at most 32 bits.

def trie.at source · line 633 · raw

@-V:Data -> @t:Trie<V> -> @+k:U32 -> Maybe<&2, V>

The value at key k, stored as n = k + 1.

def trie.set source · line 637 · raw

@-V:Data -> @t:Trie<V> -> @+k:U32 -> @v:V -> Trie<V>

def trie.from source · line 641 · raw

@-V:Data -> @xs:List<&2, V> -> @+k:U32 -> @t:Trie<V> -> Trie<V>

def first.inst source · line 654 · raw

@i:Maybe<&2, Inst> -> @+pc:U32 -> @stack:List<&2, U32> -> @seen:List<&2, U32> -> @sets:List<&2, Inst> -> Fs

def first.seen source · line 667 · raw

@hit:Bool -> @+prog:List<&2, Inst> -> @+pc:U32 -> @stack:List<&2, U32> -> @seen:List<&2, U32> -> @sets:List<&2, Inst> -> Fs

def first source · line 675 · raw

@fuel:Nat -> @+prog:List<&2, Inst> -> @st:Fs -> Maybe<&2, List<&2, Inst>>

fuel: each pc expands once and pushes at most two pcs.

def build source · line 693 · raw

@+node:Node -> @+n:U32 -> Regex

def compile.fin source · line 698 · raw

@st:Ps -> Maybe<&2, Regex>

def compile.parse source · line 709 · raw

@toks:Maybe<&2, List<&2, Tok>> -> Maybe<&2, Regex>

def compile source · line 717 · raw

@+pat:String -> Maybe<&2, Regex>

The pattern, or None for a syntax error.

def item.has source · line 723 · raw

@i:Item -> @+c:U32 -> Bool

def items.has source · line 730 · raw

@xs:List<&2, Item> -> @+c:U32 -> Bool

def word source · line 737 · raw

@m:Maybe<&2, Char> -> Bool

def assert.ok source · line 744 · raw

@k:U32 -> @+prev:Maybe<&2, Char> -> @+next:Maybe<&2, Char> -> Bool

def close.assert source · line 764 · raw

@ok:Bool -> @+pc:U32 -> @caps:List<&2, Maybe<&2, U32>> -> @stack:List<&2, Th> -> @seen:Trie<Unit> -> @out:List<&2, Th> -> Cl

def close.inst source · line 771 · raw

@i:Maybe<&2, Inst> -> @+pc:U32 -> @+caps:List<&2, Maybe<&2, U32>> -> @stack:List<&2, Th> -> @seen:Trie<Unit> -> @out:List<&2, Th> -> @+pos:U32 -> @+prev:Maybe<&2, Char> -> @+next:Maybe<&2, Char> -> Cl

def close.seen source · line 790 · raw

@hit:Bool -> @+prog:Trie<Inst> -> @+pc:U32 -> @caps:List<&2, Maybe<&2, U32>> -> @stack:List<&2, Th> -> @seen:Trie<Unit> -> @out:List<&2, Th> -> @+pos:U32 -> @+prev:Maybe<&2, Char> -> @+next:Maybe<&2, Char> -> Cl

ponytail: trie lookup and membership cost O(log m) per thread step, so a char costs O(m log m) for m instructions; a sparse set over an Array would make a step O(1).

def close.step source · line 797 · raw

@th:Th -> @stack:List<&2, Th> -> @+seen:Trie<Unit> -> @out:List<&2, Th> -> @+prog:Trie<Inst> -> @+pos:U32 -> @+prev:Maybe<&2, Char> -> @+next:Maybe<&2, Char> -> Cl

def close source · line 802 · raw

@fuel:Nat -> @+prog:Trie<Inst> -> @+pos:U32 -> @+prev:Maybe<&2, Char> -> @+next:Maybe<&2, Char> -> @st:Cl -> List<&2, Th>

fuel: each pc expands once and pushes at most two threads.

def scan.set source · line 819 · raw

@hit:Bool -> @+pc:U32 -> @caps:List<&2, Maybe<&2, U32>> -> @items:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Sc

def scan.char source · line 826 · raw

@c:Maybe<&2, Char> -> @neg:Bool -> @set:List<&2, Item> -> @+pc:U32 -> @caps:List<&2, Maybe<&2, U32>> -> @items:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Sc

def scan.hit source · line 834 · raw

@any:Bool -> @caps:List<&2, Maybe<&2, U32>> -> @items:List<&2, Th> -> Sc

any: only whether a match exists counts, so a match also drops the earlier threads.

def scan.inst source · line 841 · raw

@i:Maybe<&2, Inst> -> @c:Maybe<&2, Char> -> @+any:Bool -> @+pc:U32 -> @caps:List<&2, Maybe<&2, U32>> -> @items:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Sc

def scan.go source · line 850 · raw

@stop:Bool -> @th:Th -> @+prog:Trie<Inst> -> @c:Maybe<&2, Char> -> @+any:Bool -> @items:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Sc

def scan.step source · line 858 · raw

@st:Sc -> @th:Th -> @+prog:Trie<Inst> -> @c:Maybe<&2, Char> -> @+any:Bool -> Sc

def scan source · line 862 · raw

@xs:List<&2, Th> -> @+prog:Trie<Inst> -> @+c:Maybe<&2, Char> -> @+any:Bool -> @st:Sc -> Sc

def seed source · line 874 · raw

@best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> @xs:List<&2, Th> -> @init:List<&2, Maybe<&2, U32>> -> List<&2, Th>

Until a match is found, a new thread starts at each position, below every other.

def starts source · line 881 · raw

@xs:List<&2, Inst> -> @+c:U32 -> Bool

def seed.skip source · line 891 · raw

@items:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> @start:Maybe<&2, List<&2, Inst>> -> @next:Maybe<&2, Char> -> Bool

No live thread and no match yet: the seed is the only thread, and it dies unless next is in start.

def run.seed source · line 900 · raw

@skip:Bool -> @items:List<&2, Th> -> @+best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> @+prev:Maybe<&2, Char> -> @+next:Maybe<&2, Char> -> Vm

def run.close source · line 907 · raw

@sc:Sc -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+pos:U32 -> @+prev:Maybe<&2, Char> -> @+next:Maybe<&2, Char> -> Vm

def run.step source · line 911 · raw

@st:Vm -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+pos:U32 -> @+c:Char -> @+next:Maybe<&2, Char> -> Vm

def run.end source · line 915 · raw

@sc:Sc -> Maybe<&2, List<&2, Maybe<&2, U32>>>

def run source · line 920 · raw

@s:String -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+pos:U32 -> @st:Vm -> Maybe<&2, List<&2, Maybe<&2, U32>>>

pos: the position of s's head. Once a match exists and no thread is live, the rest of s cannot change it.

def spans source · line 936 · raw

@caps:List<&2, Maybe<&2, U32>> -> List<&2, Maybe<&2, Span>>

def find.spans source · line 945 · raw

@m:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Maybe<&2, List<&2, Maybe<&2, Span>>>

def exec source · line 953 · raw

@re:Regex -> @+s:String -> @+any:Bool -> Maybe<&2, List<&2, Maybe<&2, U32>>>

slots: capture slots to keep; is_match keeps none, so each ISave is free.

def find source · line 959 · raw

@re:Regex -> @+s:String -> Maybe<&2, List<&2, Maybe<&2, Span>>>

The leftmost match in s: the span of group 0, then of each group; None for a group that did not take part.

def is_match source · line 963 · raw

@re:Regex -> @+s:String -> Bool

Stops at the first match of any priority and records no captures.