regex.bend checks

raw source on the hub · import 0x1a53d6ec10a4300c106d83bbfb08e2ba/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 Ew source · line 691 · 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 760 · 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 765 · 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 Regex source · line 806 · 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.

Regex

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

type Th source · line 872 · raw

Data

A thread: its pc and its capture slots.

Th

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

type Cl source · line 877 · 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 932 · 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 986 · 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 1049 · raw

Data

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

type Bs source · line 1083 · 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

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 eps.ctx source · line 694 · raw

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

def eps.assert source · line 703 · raw

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

def eps.inst source · line 710 · 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 727 · raw

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

def eps.go source · line 736 · 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 747 · raw

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

def Ew.mask source · line 750 · raw

@w:Ew -> U32

def Ew.hit source · line 754 · raw

@w:Ew -> Bool

def bits.set source · line 768 · raw

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

def bits.sets source · line 772 · raw

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

def bits.plain source · line 782 · 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 791 · raw

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

def bits source · line 800 · raw

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

def build source · line 809 · raw

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

def compile.fin source · line 814 · raw

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

def compile.parse source · line 825 · raw

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

def compile source · line 833 · raw

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

The pattern, or None for a syntax error.

def item.has source · line 839 · raw

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

def items.has source · line 846 · raw

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

def word source · line 853 · raw

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

def assert.ok source · line 860 · raw

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

def close.assert source · line 880 · 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 887 · 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 906 · 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 913 · 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 918 · 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 935 · 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 942 · 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 950 · 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 957 · 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 966 · 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 974 · raw

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

def scan source · line 978 · raw

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

def seed source · line 990 · 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 997 · raw

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

def seed.skip source · line 1007 · 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 1016 · 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 1023 · 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 1027 · 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 1031 · raw

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

def run source · line 1036 · 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 1052 · raw

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

def find.spans source · line 1061 · raw

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

def exec source · line 1069 · 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 1075 · 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 1079 · 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 1086 · raw

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

def bits.char source · line 1094 · 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 1102 · 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 1110 · 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 1118 · 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 1128 · 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 1140 · raw

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

def is_match.bits source · line 1145 · 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 1153 · raw

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

def is_match source · line 1161 · raw

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

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