regex.bend checks

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

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

3 imports

import Base
import 0x6c784a08486e2e02415e89c5249e9e8a/unicode.bend as U
import 0x49814d83de8f70993a43e1002be29ecd/bytes.bend as Bytes

Types

type Item source · line 13 · 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 18 · 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 28 · 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 74 · 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 162 · 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 244 · raw

Data

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

type Num source · line 250 · 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 396 · 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 400 · 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 533 · 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 585 · 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 651 · 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 Ew source · line 692 · raw

Data

Bit-parallel NFA for is_match: bit pc stands for the set at pc, waiting on the next char. The epsilon walk from a pc: the sets it reaches and whether it reaches the match, where at0 says the position is the start of the text and at1 the end.

Ew

@stack:List<&2, U32> -> @seen:List<&2, U32> -> @mask:U32 -> @hit:Bool -> Ew

type Bit source · line 761 · raw

Data

The set at bit mask; follow: the sets live after it takes a char; fin, end: whether the match is then reached inside the text, or at its end.

Bit

@mask:U32 -> @neg:Bool -> @items:List<&2, Item> -> @follow:U32 -> @fin:Bool -> @end:Bool -> Bit

type Bits source · line 766 · raw

Data

at0: the sets live at the start of the text, and hit0 whether the empty match is there; hit01 the same for the empty text; atn and hitn the same inside the text, hit1 at its end.

Bits

@sets:List<&2, Bit> -> @at0:U32 -> @hit0:Bool -> @hit01:Bool -> @atn:U32 -> @hit1:Bool -> Bits

type Asc source · line 828 · raw

Data

The ASCII bytes that may start a match, one bit per byte, 32 to a word.

Asc

@m0:U32 -> @m1:U32 -> @m2:U32 -> @m3:U32 -> Asc

type Regex source · line 859 · 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; bits: the bit-parallel form, for programs of at most 32 instructions without word boundaries; asc: start as a table of ASCII bytes, for skipping through Bytes.

Regex

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

type Th source · line 912 · raw

Data

A thread: its pc and its capture slots.

Th

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

type Cl source · line 917 · 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 972 · 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 1026 · 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 1080 · raw

Data

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

type Bs source · line 1114 · raw

Data

One char through the bit NFA: next the sets live after it, fin and end as in Bit.

Bs

@next:U32 -> @fin:Bool -> @end:Bool -> Bs

type Dc source · line 1201 · raw

Data

A code point decoded from UTF-8 and its width in bytes, or DEnd at the end of the buffer. An invalid byte is U+FFFD of width 1, as in RE2.

Dc
```
@c:U32 -> @w:U32 -> Dc
```
DEnd
```
Dc
```

type Rb source · line 1340 · raw

Type

The Pike VM over Bytes: the buffer, the offset i of the next char, that char, and the threads waiting on it.

Rb

@a:Array<U32> -> @i:U32 -> @d:Dc -> @st:Vm -> Rb

type Rt source · line 1414 · raw

Type

The bit NFA over Bytes: the buffer, the offset i of the next char, that char, and the NFA state.

Rt

@a:Array<U32> -> @i:U32 -> @d:Dc -> @st:Bs -> Rt

Definitions

def lit source · line 35 · raw

@+c:U32 -> Node

def is_digit source · line 38 · raw

@+c:U32 -> Bool

def is_word source · line 41 · raw

@+c:U32 -> Bool

def is_alnum source · line 44 · raw

@+c:U32 -> Bool

def perl.d source · line 48 · raw

List<&2, Item>

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

def perl.D source · line 51 · raw

List<&2, Item>

def perl.w source · line 54 · raw

List<&2, Item>

def perl.W source · line 57 · raw

List<&2, Item>

def perl.s source · line 60 · raw

List<&2, Item>

def perl.S source · line 63 · raw

List<&2, Item>

def cats source · line 66 · raw

List<&2, String>

def prop.if source · line 80 · raw

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

def prop.ok source · line 87 · raw

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

def prop.name source · line 90 · raw

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

def prop source · line 100 · raw

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

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

def esc.other source · line 110 · 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 118 · raw

@s:String -> Esc

The text after a backslash.

def class.range source · line 167 · raw

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

def class.hi source · line 174 · raw

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

def class.lo source · line 186 · 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 197 · raw

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

def class.step source · line 209 · raw

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

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

def class.run source · line 225 · raw

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

fuel: every step eats at least one char.

def class source · line 238 · raw

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

def num.add source · line 253 · raw

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

def num.go source · line 256 · raw

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

def num source · line 271 · raw

@s:String -> Num

def lex.rep source · line 279 · 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 286 · raw

@m:Num -> U32

def lex.brace.max source · line 291 · 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 303 · raw

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

def lex.class source · line 320 · raw

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

def lex.esc source · line 329 · raw

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

def lex.step source · line 340 · raw

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

def lex source · line 379 · 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 403 · raw

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

def seq.go source · line 414 · raw

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

def seq source · line 421 · raw

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

def alt.go source · line 424 · raw

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

def group source · line 431 · raw

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

def rep.copies source · line 438 · raw

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

def rep.opt source · line 445 · raw

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

def rep.inf source · line 453 · 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 460 · raw

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

def rep source · line 467 · raw

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

def rep.ok source · line 471 · 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 478 · 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 489 · raw

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

def parse.close source · line 496 · raw

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

def parse.tok source · line 503 · 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 516 · raw

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

def parse source · line 523 · raw

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

def size source · line 541 · raw

@n:Node -> U32

def emit source · line 561 · 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 590 · 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 606 · 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 634 · 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 638 · raw

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

def trie.from source · line 642 · raw

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

def first.inst source · line 655 · 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 668 · 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 676 · 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 eps.ctx source · line 695 · raw

@k:U32 -> @+at0:Bool -> @+at1:Bool -> Bool

def eps.assert source · line 704 · raw

@ok:Bool -> @+pc:U32 -> @stack:List<&2, U32> -> @seen:List<&2, U32> -> @mask:U32 -> @hit:Bool -> Ew

def eps.inst source · line 711 · raw

@i:Maybe<&2, Inst> -> @+pc:U32 -> @+at0:Bool -> @+at1:Bool -> @stack:List<&2, U32> -> @seen:List<&2, U32> -> @+mask:U32 -> @hit:Bool -> Ew

def eps.seen source · line 728 · raw

@hit:Bool -> @+prog:List<&2, Inst> -> @+pc:U32 -> @+at0:Bool -> @+at1:Bool -> @w:Ew -> Ew

def eps.go source · line 737 · raw

@fuel:Nat -> @+prog:List<&2, Inst> -> @+at0:Bool -> @+at1:Bool -> @w:Ew -> Ew

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

def eps source · line 748 · raw

@+fuel:Nat -> @+prog:List<&2, Inst> -> @+pc:U32 -> @+at0:Bool -> @+at1:Bool -> Ew

def Ew.mask source · line 751 · raw

@w:Ew -> U32

def Ew.hit source · line 755 · raw

@w:Ew -> Bool

def bits.set source · line 769 · raw

@+fuel:Nat -> @+prog:List<&2, Inst> -> @+pc:U32 -> @neg:Bool -> @items:List<&2, Item> -> Bit

def bits.sets source · line 773 · raw

@xs:List<&2, Inst> -> @+fuel:Nat -> @+prog:List<&2, Inst> -> @+pc:U32 -> List<&2, Bit>

def bits.plain source · line 783 · raw

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

Word boundaries depend on the chars on both sides, which one mask per set cannot track.

def bits.if source · line 792 · raw

@ok:Bool -> @+fuel:Nat -> @+prog:List<&2, Inst> -> Maybe<&2, Bits>

def bits source · line 801 · raw

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

def item.has source · line 804 · raw

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

def items.has source · line 811 · raw

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

def starts source · line 818 · raw

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

def asc.bit source · line 831 · raw

@hit:Bool -> @+c:U32 -> @a:Asc -> Asc

def asc.go source · line 841 · raw

@n:Nat -> @+c:U32 -> @+sets:List<&2, Inst> -> @a:Asc -> Asc

c: the byte for step n, counting down from 127 to 0.

def asc source · line 848 · raw

@start:Maybe<&2, List<&2, Inst>> -> Maybe<&2, Asc>

def build source · line 862 · raw

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

def compile.fin source · line 868 · raw

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

def compile.parse source · line 879 · raw

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

def compile source · line 887 · raw

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

The pattern, or None for a syntax error.

def word source · line 893 · raw

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

def assert.ok source · line 900 · raw

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

def close.assert source · line 920 · 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 927 · 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 946 · 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 953 · 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 958 · 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 975 · 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 982 · 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 990 · 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 997 · 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 1006 · 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 1014 · raw

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

def scan source · line 1018 · raw

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

def seed source · line 1030 · 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 seed.skip source · line 1038 · 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 1047 · 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 1054 · 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 1058 · 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 1062 · raw

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

def run source · line 1067 · 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 1083 · raw

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

def find.spans source · line 1092 · raw

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

def exec source · line 1100 · 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 1106 · 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.vm source · line 1110 · raw

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

The Pike VM form of is_match: stops at the first match of any priority and records no captures.

def bits.take source · line 1117 · raw

@hit:Bool -> @+follow:U32 -> @+fin:Bool -> @+end:Bool -> @acc:Bs -> Bs

def bits.char source · line 1125 · raw

@live:Bool -> @+c:U32 -> @neg:Bool -> @items:List<&2, Item> -> @+follow:U32 -> @+fin:Bool -> @+end:Bool -> @acc:Bs -> Bs

def bits.step source · line 1133 · raw

@xs:List<&2, Bit> -> @+cur:U32 -> @+c:U32 -> @acc:Bs -> Bs

ponytail: one test per set in the program, not a table lookup; use per-byte tables if sets grow many.

def bits.idle source · line 1141 · raw

@start:Maybe<&2, List<&2, Inst>> -> @+cur:U32 -> @+atn:U32 -> @+c:U32 -> Bool

Only the sets live at a fresh start wait on c, and c starts none of them: nothing moves.

def bits.go source · line 1149 · raw

@idle:Bool -> @+sets:List<&2, Bit> -> @+atn:U32 -> @+hit1:Bool -> @+cur:U32 -> @+c:U32 -> Bs

hit1: a match starts and ends at the end of the text, so end starts from it.

def bits.run source · line 1159 · raw

@s:String -> @+sets:List<&2, Bit> -> @+start:Maybe<&2, List<&2, Inst>> -> @+atn:U32 -> @+hit1:Bool -> @r:Bs -> Bool

r: the sets live at s's head, whether a match was found, and whether one ends at the end of the text, if the text ends here. Inside the text an assertion can only fail, so fin implies end, and a match at fin is final.

def bits.is_match source · line 1171 · raw

@b:Bits -> @start:Maybe<&2, List<&2, Inst>> -> @s:String -> Bool

def is_match.bits source · line 1176 · raw

@re:Regex -> @s:String -> Maybe<&2, Bool>

The bit NFA form of is_match, or None when the program is too large or has a word boundary.

def is_match.pick source · line 1184 · raw

@m:Maybe<&2, Bool> -> @re:Regex -> @+s:String -> Bool

def is_match source · line 1192 · raw

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

Whether s has a match; the bit NFA runs when the program allows it, else the Pike VM.

def Dc.char source · line 1205 · raw

@d:Dc -> Maybe<&2, Char>

def pk.if source · line 1212 · raw

@ok:Bool -> @a:Array<U32> -> @+i:U32 -> Pair(Array<U32>, U32)

def pk source · line 1220 · raw

@a:Array<U32> -> @+len:U32 -> @+i:U32 -> Pair(Array<U32>, U32)

Byte i, or 0 past len, which is no continuation byte.

def cont source · line 1223 · raw

@+b:U32 -> Bool

def dec.pick source · line 1226 · raw

@ok2:Bool -> @ok3:Bool -> @ok4:Bool -> @+c2:U32 -> @+c3:U32 -> @+c4:U32 -> Dc

def dec.n source · line 1242 · raw

@+b0:U32 -> @+b1:U32 -> @+b2:U32 -> @+b3:U32 -> Dc

Overlong forms, surrogates, and code points past U+10FFFF are invalid.

def dec.b3 source · line 1254 · raw

@+b0:U32 -> @+b1:U32 -> @+b2:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Dc)

def dec.b2 source · line 1258 · raw

@+len:U32 -> @+i:U32 -> @+b0:U32 -> @+b1:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Dc)

def dec.b1 source · line 1262 · raw

@+len:U32 -> @+i:U32 -> @+b0:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Dc)

def dec.lead source · line 1266 · raw

@ascii:Bool -> @+len:U32 -> @+i:U32 -> @+b0:U32 -> @a:Array<U32> -> Pair(Array<U32>, Dc)

def dec.at source · line 1273 · raw

@+len:U32 -> @+i:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Dc)

def dec.if source · line 1277 · raw

@ok:Bool -> @a:Array<U32> -> @+len:U32 -> @+i:U32 -> Pair(Array<U32>, Dc)

def dec source · line 1285 · raw

@a:Array<U32> -> @+len:U32 -> @+i:U32 -> Pair(Array<U32>, Dc)

The char at byte i, or DEnd at len.

def asc.word source · line 1288 · raw

@k:U32 -> @a:Asc -> U32

def asc.has source · line 1304 · raw

@+b:U32 -> @a:Asc -> Bool

Any non-ASCII byte may start a match: it may lead a char in start.

def probe.of source · line 1307 · raw

@+m:Asc -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, Bool)

def probe.if source · line 1312 · raw

@ok:Bool -> @a:Array<U32> -> @+k:U32 -> @+m:Asc -> Pair(Array<U32>, Bool)

Past len counts as a hit, so a skip stops there.

def probe source · line 1319 · raw

@a:Array<U32> -> @+len:U32 -> @+k:U32 -> @+m:Asc -> Pair(Array<U32>, Bool)

def skip source · line 1323 · raw

@fuel:Nat -> @r:Pair(Array<U32>, Bool) -> @+len:U32 -> @+k:U32 -> @+m:Asc -> Pair(Array<U32>, U32)

The first offset at or after k whose byte may start a match, or len; r holds the probe of k.

def skip.from source · line 1336 · raw

@a:Array<U32> -> @+len:U32 -> @+k:U32 -> @+m:Asc -> Pair(Array<U32>, U32)

def rb.step source · line 1343 · raw

@r:Pair(Array<U32>, Dc) -> @+j:U32 -> @st:Vm -> @+c:U32 -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> Rb

def rb.seed source · line 1348 · raw

@r:Pair(Array<U32>, Dc) -> @+k:U32 -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> Rb

A fresh seed at k. start is Some here, so no assertion is reachable before a char and prev does not count.

def rb.skip source · line 1352 · raw

@r:Pair(Array<U32>, U32) -> @+len:U32 -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> Rb

def rb.idle source · line 1359 · raw

@asc:Maybe<&2, Asc> -> @a:Array<U32> -> @+len:U32 -> @+j:U32 -> @+c:U32 -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> Rb

No thread is live and no match exists. With asc, the seed at the char before j was skipped because that char cannot start a match: jump to the next byte that may. Without asc, the seed died on an assertion, so step on as usual; prev matters then.

def runb source · line 1367 · raw

@fuel:Nat -> @r:Rb -> @+len:U32 -> @+prog:Trie<Inst> -> @+cfuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+asc:Maybe<&2, Asc> -> @+any:Bool -> Pair(Array<U32>, Maybe<&2, List<&2, Maybe<&2, U32>>>)

fuel: each step eats at least one byte, and the last one sees DEnd.

def exec.bytes.fin source · line 1388 · raw

@+len:U32 -> @r:Pair(Array<U32>, Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def exec.bytes source · line 1392 · raw

@re:Regex -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @+any:Bool -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def find.bytes.fin source · line 1398 · raw

@r:Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, Span>>>)

def find.bytes source · line 1403 · raw

@re:Regex -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, Span>>>)

find over UTF-8 bytes: the buffer back, and spans as byte offsets.

def is_match.bytes.fin source · line 1406 · raw

@r:Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Bool)

def is_match.bytes.vm source · line 1410 · raw

@re:Regex -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Bool)

def rt.at source · line 1417 · raw

@r:Pair(Array<U32>, Dc) -> @+j:U32 -> @st:Bs -> Rt

def rt.skip source · line 1421 · raw

@r:Pair(Array<U32>, U32) -> @+len:U32 -> @+atn:U32 -> @+hit1:Bool -> Rt

def rt.next source · line 1426 · raw

@idle:Bool -> @asc:Maybe<&2, Asc> -> @a:Array<U32> -> @+len:U32 -> @+j:U32 -> @+sets:List<&2, Bit> -> @+atn:U32 -> @+hit1:Bool -> @+cur:U32 -> @+c:U32 -> Rt

idle: only the sets live at a fresh start wait on c, and c starts none of them.

def bitsb source · line 1437 · raw

@fuel:Nat -> @r:Rt -> @+len:U32 -> @+sets:List<&2, Bit> -> @+start:Maybe<&2, List<&2, Inst>> -> @+asc:Maybe<&2, Asc> -> @+atn:U32 -> @+hit1:Bool -> Pair(Array<U32>, Bool)

def bits.bytes.fin source · line 1455 · raw

@+len:U32 -> @r:Pair(Array<U32>, Bool) -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, Bool>)

def bits.bytes source · line 1459 · raw

@b:Bits -> @start:Maybe<&2, List<&2, Inst>> -> @asc:Maybe<&2, Asc> -> @+len:U32 -> @buf:Array<U32> -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, Bool>)

def bits.bytes.if source · line 1463 · raw

@m:Maybe<&2, Bits> -> @start:Maybe<&2, List<&2, Inst>> -> @asc:Maybe<&2, Asc> -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, Bool>)

def is_match.bytes.bits source · line 1472 · raw

@re:Regex -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, Bool>)

The bit NFA form of is_match over Bytes, or None when the program does not allow it.

def is_match.bytes.pick source · line 1476 · raw

@r:Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, Bool>) -> @re:Regex -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Bool)

def is_match.bytes source · line 1485 · raw

@+re:Regex -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Bool)

is_match over UTF-8 bytes: the buffer back, and whether it has a match.