regex.bend checks

raw source on the hub · import 0x8e3e63eb9684869e3e7a2073837d2e82/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; plain: no word boundary.

Regex

@prog:Trie<Inst> -> @fuel:Nat -> @slots:Nat -> @start:Maybe<&2, List<&2, Inst>> -> @bits:Maybe<&2, Bits> -> @asc:Maybe<&2, Asc> -> @plain:Bool -> 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 Op source · line 1403 · raw

Data

A new thread: pc, the thread at src it came from (or the seed), and the slots it saved.

Op

@src:U32 -> @pc:U32 -> @saves:List<&2, U32> -> Op

type Tr source · line 1408 · raw

Data

next: the state after the char; hit: 1 + the index of the thread that matched, or 0; fresh: no match yet and every new thread comes from the seed, so the next state is a fresh start.

TrNo
```
Tr
```
TrSame
```
Tr
```

Tr

@next:U32 -> @hit:U32 -> @outs:List<&2, Op> -> @fresh:Bool -> Tr

type Sk source · line 1413 · raw

Data

Sk
```
@pcs:List<&2, U32> -> @done:Bool -> Sk
```

type Ix source · line 1416 · raw

Data

Ix
```
@key:Sk -> @id:U32 -> Ix
```

type Ik source · line 1420 · raw

Data

The interned states, how many there are, and the id of one.

Ik

@keys:List<&2, Ix> -> @n:U32 -> @id:U32 -> Ik

type Lr source · line 1424 · raw

Data

A learned transition, with the next state's key in place of its id.

Lr

@hit:U32 -> @outs:List<&2, Op> -> @key:Sk -> @fresh:Bool -> Lr

type Rq source · line 1641 · raw

Type

The DFA over Bytes: the buffer, the transitions by state and ASCII char, the interned states, the current state, the offset i of the next char, that char, and the threads waiting on it.

Rq

@a:Array<U32> -> @tab:Array<Tr> -> @keys:List<&2, Ix> -> @n:U32 -> @id:U32 -> @i:U32 -> @d:Dc -> @st:Vm -> @same:Bool -> Rq

type Spin source · line 1672 · raw

Type

A same transition leaves the VM and state id intact. Stop before the last byte: its following end-of-text context needs the plain Pike step.

Spin

@a:Array<U32> -> @tab:Array<Tr> -> @i:U32 -> Spin

type SpinStep source · line 1675 · raw

Type

SpinStep

@a:Array<U32> -> @tab:Array<Tr> -> @i:U32 -> @tr:Tr -> SpinStep

type Ar source · line 1717 · raw

Type

Cached DFA steps reuse two thread buffers; the Pike VM handles learning and text boundaries.

Ar

@old:Array<Th> -> @spare:Array<Th> -> @count:U32 -> @cap:U32 -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Ar

type Qst source · line 1821 · raw

Type

QDone
```
@best:List<&2, Maybe<&2, U32>> -> Qst
```
QIdle
```
@ar:Ar -> Qst
```
QLive
```
@ar:Ar -> Qst
```
QPlain
```
@st:Vm -> Qst
```

type Qa source · line 1842 · raw

Type

Qa

@a:Array<U32> -> @tab:Array<Tr> -> @keys:List<&2, Ix> -> @n:U32 -> @id:U32 -> @i:U32 -> @d:Dc -> @ar:Qst -> @same:Bool -> Qa

type Rt source · line 1998 · 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 seed.id source · line 1399 · raw

U32

The seed thread's index, and the id of a state the full cache could not add.

def vm.pcs source · line 1427 · raw

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

def vm.key source · line 1434 · raw

@st:Vm -> Sk

def pcs.eq source · line 1438 · raw

@xs:List<&2, U32> -> @ys:List<&2, U32> -> Bool

def sk.eq source · line 1447 · raw

@a:Sk -> @b:Sk -> Bool

def ix.find source · line 1453 · raw

@xs:List<&2, Ix> -> @+k:Sk -> U32

ponytail: a linear scan over at most cap states, run only when a transition is learned; hash the keys if cap grows.

def intern.if source · line 1460 · raw

@miss:Bool -> @+found:U32 -> @keys:List<&2, Ix> -> @+n:U32 -> @+k:Sk -> Ik

def intern.full source · line 1467 · raw

@room:Bool -> @+keys:List<&2, Ix> -> @+n:U32 -> @+k:Sk -> Ik

def intern source · line 1477 · raw

@+keys:List<&2, Ix> -> @+n:U32 -> @+cap:U32 -> @+k:Sk -> Ik

The id of state k, added when new; seed.id() when the cache is full. A full cache is not searched: with many states the search would cost more than the step it saves.

def sym.caps source · line 1480 · raw

@+slots:Nat -> @+i:U32 -> List<&2, Maybe<&2, U32>>

def sym.ths source · line 1483 · raw

@xs:List<&2, Th> -> @+slots:Nat -> @+i:U32 -> List<&2, Th>

def sym.src source · line 1491 · raw

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

The index in the last slot.

def sym.saves source · line 1501 · raw

@xs:List<&2, Maybe<&2, U32>> -> @+k:U32 -> List<&2, U32>

The slots before the last that hold a position.

def sym.outs source · line 1512 · raw

@xs:List<&2, Th> -> List<&2, Op>

def sym.fresh source · line 1519 · raw

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

def op.same source · line 1526 · raw

@saves:List<&2, U32> -> @+src:U32 -> @+pc:U32 -> @+i:U32 -> @+old:U32 -> Bool

def ops.same source · line 1533 · raw

@xs:List<&2, Op> -> @ths:List<&2, Th> -> @+i:U32 -> Bool

def tr.of source · line 1542 · raw

@same:Bool -> @+next:U32 -> @+hit:U32 -> @+outs:List<&2, Op> -> @+fresh:Bool -> Tr

def sym.lr source · line 1549 · raw

@+hit:U32 -> @+done:Bool -> @v:Vm -> Lr

def sym.hit source · line 1554 · raw

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

def sym.close source · line 1567 · raw

@sc:Sc -> @+done:Bool -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+slots:Nat -> @+c:U32 -> Lr

The closure after the char, inside the text: prev and next are any chars, and start is None so the seed always runs; replay.vm skips a fresh start the way seed.skip does.

def sym.best source · line 1572 · raw

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

Once a match is found no seed starts, so a done state scans with some best.

def learn source · line 1579 · raw

@st:Vm -> @+c:U32 -> @+prog:Trie<Inst> -> @+fuel:Nat -> @+slots:Nat -> @+any:Bool -> Lr

def caps.at source · line 1583 · raw

@m:Maybe<&2, Th> -> @+init:List<&2, Maybe<&2, U32>> -> List<&2, Maybe<&2, U32>>

def caps.of.if source · line 1590 · raw

@seed:Bool -> @+src:U32 -> @+ths:List<&2, Th> -> @+init:List<&2, Maybe<&2, U32>> -> List<&2, Maybe<&2, U32>>

def caps.of source · line 1597 · raw

@+src:U32 -> @+ths:List<&2, Th> -> @+init:List<&2, Maybe<&2, U32>> -> List<&2, Maybe<&2, U32>>

def saves.put source · line 1600 · raw

@xs:List<&2, U32> -> @caps:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> List<&2, Maybe<&2, U32>>

def replay source · line 1607 · raw

@xs:List<&2, Op> -> @+ths:List<&2, Th> -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> List<&2, Th>

def replay.best source · line 1614 · raw

@none:Bool -> @+hit:U32 -> @+ths:List<&2, Th> -> @+init:List<&2, Maybe<&2, U32>> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Maybe<&2, List<&2, Maybe<&2, U32>>>

def replay.fresh source · line 1622 · raw

@skip:Bool -> @outs:List<&2, Op> -> @+ths:List<&2, Th> -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> Vm

fresh: no match yet and every thread starts at the seed; skip it when next cannot start a match.

def replay.vm source · line 1630 · raw

@fresh:Bool -> @+hit:U32 -> @outs:List<&2, Op> -> @st:Vm -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> @+start:Maybe<&2, List<&2, Inst>> -> @+next:Maybe<&2, Char> -> Vm

A learned transition on the real threads; next is the char after the new position.

def rq.ik source · line 1644 · raw

@ik:Ik -> @a:Array<U32> -> @tab:Array<Tr> -> @+j:U32 -> @+d:Dc -> @st:Vm -> Rq

def rq.of source · line 1648 · raw

@r:Rb -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+cap:U32 -> Rq

def rq.store source · line 1652 · raw

@ik:Ik -> @a:Array<U32> -> @tab:Array<Tr> -> @+idx:U32 -> @+old:U32 -> @+hit:U32 -> @+outs:List<&2, Op> -> @+fresh:Bool -> @+j:U32 -> @+d:Dc -> @st:Vm -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> Rq

def rq.learn source · line 1658 · raw

@lr:Lr -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+idx:U32 -> @+old:U32 -> @+j:U32 -> @+d:Dc -> @st:Vm -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+cap:U32 -> Rq

def rq.real source · line 1663 · raw

@room:Bool -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+j:U32 -> @+d:Dc -> @+st:Vm -> @+cap:U32 -> Rq

With a full cache, skip building the key too.

def spin.byte source · line 1678 · raw

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

def spin.tr source · line 1685 · raw

@ascii:Bool -> @tab:Array<Tr> -> @+id:U32 -> @+c:U32 -> Pair(Array<Tr>, Tr)

def spin.state.tr source · line 1692 · raw

@r:Pair(Array<Tr>, Tr) -> @a:Array<U32> -> @+i:U32 -> SpinStep

def spin.state source · line 1696 · raw

@r:Pair(Array<U32>, U32) -> @tab:Array<Tr> -> @+i:U32 -> @+id:U32 -> @+cap:U32 -> SpinStep

def spin source · line 1700 · raw

@fuel:Nat -> @s:SpinStep -> @+len:U32 -> @+id:U32 -> @+cap:U32 -> Spin

def ar.fill source · line 1720 · raw

@xs:List<&2, Th> -> @a:Array<Th> -> @+i:U32 -> Array<Th>

def ar.reset.size source · line 1727 · raw

@fits:Bool -> @ths:List<&2, Th> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> @old:Array<Th> -> @spare:Array<Th> -> @+count:U32 -> @+cap:U32 -> @+init:List<&2, Maybe<&2, U32>> -> Ar

def ar.reset.put source · line 1735 · raw

@vm:Vm -> @old:Array<Th> -> @spare:Array<Th> -> @+cap:U32 -> @+init:List<&2, Maybe<&2, U32>> -> Ar

def ar.reset source · line 1740 · raw

@vm:Vm -> @ar:Ar -> @+init:List<&2, Maybe<&2, U32>> -> Ar

def ar.new source · line 1744 · raw

@vm:Vm -> @+init:List<&2, Maybe<&2, U32>> -> Ar

def ar.list.go source · line 1747 · raw

@fuel:Nat -> @r:Pair(Array<Th>, Th) -> @+i:U32 -> @acc:List<&2, Th> -> Pair(Array<Th>, List<&2, Th>)

def ar.vm.put source · line 1756 · raw

@r:Pair(Array<Th>, List<&2, Th>) -> @spare:Array<Th> -> @+count:U32 -> @+cap:U32 -> @+best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Pair(Ar, Vm)

def ar.vm source · line 1760 · raw

@ar:Ar -> Pair(Ar, Vm)

def ar.src.get source · line 1764 · raw

@r:Pair(Array<Th>, Th) -> Pair(Array<Th>, List<&2, Maybe<&2, U32>>)

def ar.src source · line 1768 · raw

@seed:Bool -> @old:Array<Th> -> @+src:U32 -> @+init:List<&2, Maybe<&2, U32>> -> Pair(Array<Th>, List<&2, Maybe<&2, U32>>)

def ar.put source · line 1775 · raw

@r:Pair(Array<Th>, List<&2, Maybe<&2, U32>>) -> @spare:Array<Th> -> @+pc:U32 -> @saves:List<&2, U32> -> @+pos:U32 -> @+i:U32 -> Pair(Array<Th>, Array<Th>)

def ar.replay source · line 1779 · raw

@xs:List<&2, Op> -> @r:Pair(Array<Th>, Array<Th>) -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> @+i:U32 -> @+cap:U32 -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Ar

def ar.best.get source · line 1788 · raw

@r:Pair(Array<Th>, List<&2, Maybe<&2, U32>>) -> Pair(Array<Th>, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def ar.best.none source · line 1792 · raw

@no_hit:Bool -> @old:Array<Th> -> @+hit:U32 -> @+init:List<&2, Maybe<&2, U32>> -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Pair(Array<Th>, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def ar.replay.best source · line 1799 · raw

@r:Pair(Array<Th>, Maybe<&2, List<&2, Maybe<&2, U32>>>) -> @spare:Array<Th> -> @outs:List<&2, Op> -> @+cap:U32 -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> Ar

def ar.cached.fresh source · line 1803 · raw

@skip:Bool -> @ar:Ar -> @outs:List<&2, Op> -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> Ar

def ar.cached source · line 1813 · raw

@fresh:Bool -> @+hit:U32 -> @outs:List<&2, Op> -> @ar:Ar -> @+init:List<&2, Maybe<&2, U32>> -> @+pos:U32 -> @+start:Maybe<&2, List<&2, Inst>> -> @+next:Maybe<&2, Char> -> Ar

A cached transition was learned in this run, so the buffers already fit its outputs.

def qa.status.if source · line 1827 · raw

@zero:Bool -> @old:Array<Th> -> @spare:Array<Th> -> @+count:U32 -> @+cap:U32 -> @best:Maybe<&2, List<&2, Maybe<&2, U32>>> -> Qst

def qa.status source · line 1838 · raw

@ar:Ar -> Qst

def qa.seed source · line 1845 · raw

@r:Rq -> @+init:List<&2, Maybe<&2, U32>> -> Qa

def qa.from.state source · line 1849 · raw

@cached:Bool -> @st:Vm -> @ar:Ar -> @+init:List<&2, Maybe<&2, U32>> -> Qst

def qa.from source · line 1856 · raw

@r:Rq -> @ar:Ar -> @+init:List<&2, Maybe<&2, U32>> -> @+cap:U32 -> Qa

def qa.learn.vm source · line 1860 · raw

@r:Pair(Ar, Vm) -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+idx:U32 -> @+j:U32 -> @+d:Dc -> @+c:U32 -> @+prog:Trie<Inst> -> @+cfuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+slots:Nat -> @+cap:U32 -> Qa

def qa.real.vm source · line 1864 · raw

@r:Pair(Ar, Vm) -> @s:Pair(Array<U32>, Dc) -> @+j:U32 -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+c:U32 -> @+prog:Trie<Inst> -> @+cfuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+cap:U32 -> Qa

def qa.real source · line 1869 · raw

@s:Pair(Array<U32>, Dc) -> @+j:U32 -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @ar:Ar -> @+c:U32 -> @+prog:Trie<Inst> -> @+cfuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+cap:U32 -> Qa

def qa.cached source · line 1872 · raw

@r:Pair(Array<Tr>, Tr) -> @a:Array<U32> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+idx:U32 -> @+j:U32 -> @+d:Dc -> @ar:Ar -> @+c:U32 -> @+prog:Trie<Inst> -> @+cfuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+slots:Nat -> @+cap:U32 -> Qa

def qa.pick source · line 1882 · raw

@ok:Bool -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+id:U32 -> @+j:U32 -> @+d:Dc -> @ar:Ar -> @+c:U32 -> @+prog:Trie<Inst> -> @+cfuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+slots:Nat -> @+cap:U32 -> Qa

def qa.step source · line 1890 · raw

@s:Pair(Array<U32>, Dc) -> @+j:U32 -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+id:U32 -> @ar:Ar -> @+c:U32 -> @+prog:Trie<Inst> -> @+cfuel:Nat -> @+init:List<&2, Maybe<&2, U32>> -> @+start:Maybe<&2, List<&2, Inst>> -> @+any:Bool -> @+slots:Nat -> @+cap:U32 -> Qa

def qa.spin.read source · line 1894 · raw

@s:Pair(Array<U32>, Dc) -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+id:U32 -> @+i:U32 -> @ar:Qst -> Qa

def qa.spin.dec source · line 1898 · raw

@moved:Bool -> @a:Array<U32> -> @tab:Array<Tr> -> @+len:U32 -> @+keys:List<&2, Ix> -> @+n:U32 -> @+id:U32 -> @+i:U32 -> @d:Dc -> @ar:Qst -> Qa

def qa.spin.at source · line 1905 · raw

@s:Spin -> @+old:U32 -> @+len:U32 -> @+keys:List<&2, Ix> -> @+n:U32 -> @+id:U32 -> @d:Dc -> @ar:Qst -> Qa

def qa.spin.if source · line 1909 · raw

@same:Bool -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:List<&2, Ix> -> @+n:U32 -> @+id:U32 -> @+i:U32 -> @d:Dc -> @ar:Qst -> @+fuel:Nat -> @+len:U32 -> @+cap:U32 -> Qa

def qa.spin source · line 1916 · raw

@r:Qa -> @+fuel:Nat -> @+len:U32 -> @+cap:U32 -> Qa

def qa.end.vm source · line 1920 · raw

@st:Vm -> @a:Array<U32> -> @+prog:Trie<Inst> -> @+any:Bool -> Pair(Array<U32>, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def qa.end source · line 1924 · raw

@r:Pair(Ar, Vm) -> @a:Array<U32> -> @+prog:Trie<Inst> -> @+any:Bool -> Pair(Array<U32>, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def qa.end.status source · line 1928 · raw

@st:Qst -> @a:Array<U32> -> @+prog:Trie<Inst> -> @+any:Bool -> Pair(Array<U32>, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def runqa source · line 1940 · raw

@+fuel:Nat -> @r:Qa -> @+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 -> @+slots:Nat -> @+cap:U32 -> Pair(Array<U32>, Maybe<&2, List<&2, Maybe<&2, U32>>>)

Each step consumes a byte; after the cache fills, continue in the plain Pike VM.

def exec.bytes.fin source · line 1962 · 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.go source · line 1967 · raw

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

Short texts get a small cache: 8 states, so learning costs little.

def exec.bytes source · line 1976 · 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 1982 · 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 1987 · 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 1990 · 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 1994 · raw

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

def rt.at source · line 2001 · raw

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

def rt.skip source · line 2005 · raw

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

def rt.next source · line 2010 · 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 2021 · 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 2039 · raw

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

def bits.bytes source · line 2043 · 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 2047 · 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 2056 · 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 2060 · raw

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

def is_match.bytes source · line 2069 · 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.