regex.bend checks

raw source on the hub · import 0x1300b2d5b9aa6d75cbf3892ade71bfa5/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 667 · 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 733 · 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 774 · 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 843 · 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 848 · 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 910 · 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 958 · raw

Data

Regex

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

type Th source · line 1011 · raw

Data

A thread: its pc and its capture slots.

Th

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

type Cl source · line 1016 · 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 1071 · 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 1125 · 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 1179 · raw

Data

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

type Bs source · line 1213 · 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 1300 · 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 1439 · 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 1502 · 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 1507 · 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 1512 · raw

Data

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

type Ix source · line 1515 · raw

Data

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

type Ik source · line 1519 · raw

Data

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

Ik

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

type Lr source · line 1523 · 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 1764 · 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:Trie<List<&2, Ix>> -> @n:U32 -> @id:U32 -> @i:U32 -> @d:Dc -> @st:Vm -> @same:Bool -> Rq

type Spin source · line 1795 · 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 1798 · raw

Type

SpinStep

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

type Ar source · line 1840 · 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 1944 · 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 1965 · raw

Type

Qa

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

type Rv source · line 2116 · raw

Type

Rv

@a:Array<U32> -> @best:Maybe<&2, U32> -> @ascii:Bool -> Rv

type RevBits source · line 2119 · raw

Type

RevBits

@running:Bool -> @a:Array<U32> -> @mask:U32 -> @best:Maybe<&2, U32> -> @ascii:Bool -> RevBits

type RevPhase source · line 2159 · raw

Type

Seek

@hit:Maybe<&2, U32> -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @best:Maybe<&2, U32> -> RevPhase

Check

@run:Rv -> @len:U32 -> @at:U32 -> @best:Maybe<&2, U32> -> RevPhase

type RevFound source · line 2163 · raw

Type

RevFound

@b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @best:Maybe<&2, U32> -> @safe:Bool -> RevFound

type Rt source · line 2280 · 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 required.right source · line 542 · raw

@b:Maybe<&2, U32> -> @a:Maybe<&2, U32> -> Maybe<&2, U32>

A byte that every match must contain. Optional branches and character classes have none.

def required source · line 549 · raw

@n:Node -> Maybe<&2, U32>

def required.join source · line 570 · raw

@right:Maybe<&2, Node> -> @left:Maybe<&2, Node> -> @a:Node -> Maybe<&2, Node>

def required.prefix source · line 578 · raw

@n:Node -> Maybe<&2, Node>

The first iteration contains the selected literal; every occurrence is inspected.

def reverse.ok source · line 591 · raw

@n:Node -> Bool

def reverse.node source · line 608 · raw

@n:Node -> Node

def size source · line 623 · raw

@n:Node -> U32

def emit source · line 643 · 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 672 · 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 688 · 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 716 · 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 720 · raw

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

def trie.from source · line 724 · raw

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

def first.inst source · line 737 · 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 750 · 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 758 · 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 777 · raw

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

def eps.assert source · line 786 · raw

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

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

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

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

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

def Ew.mask source · line 833 · raw

@w:Ew -> U32

def Ew.hit source · line 837 · raw

@w:Ew -> Bool

def bits.set source · line 851 · raw

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

def bits.sets source · line 855 · raw

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

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

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

def bits source · line 883 · raw

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

def item.has source · line 886 · raw

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

def items.has source · line 893 · raw

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

def starts source · line 900 · raw

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

def asc.bit source · line 913 · raw

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

def asc.go source · line 923 · 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 930 · raw

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

def rev.build source · line 942 · raw

@m:Maybe<&2, Node> -> Maybe<&2, Bits>

def rev.if source · line 951 · raw

@ok:Bool -> @node:Node -> Maybe<&2, Bits>

def build source · line 961 · raw

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

def compile.fin source · line 967 · raw

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

def compile.parse source · line 978 · raw

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

def compile source · line 986 · raw

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

The pattern, or None for a syntax error.

def word source · line 992 · raw

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

def assert.ok source · line 999 · raw

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

def close.assert source · line 1019 · 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 1026 · 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 1045 · 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 1052 · 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 1057 · 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 1074 · 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 1081 · 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 1089 · 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 1096 · 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 1105 · 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 1113 · raw

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

def scan source · line 1117 · raw

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

def seed source · line 1129 · 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 1137 · 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 1146 · 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 1153 · 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 1157 · 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 1161 · raw

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

def run source · line 1166 · 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 1182 · raw

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

def find.spans source · line 1191 · raw

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

def exec source · line 1199 · 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 1205 · 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 1209 · 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 1216 · raw

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

def bits.char source · line 1224 · 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 1232 · 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 1240 · 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 1248 · 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 1258 · 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 1270 · raw

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

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

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

def is_match source · line 1291 · 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 1304 · raw

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

def pk.if source · line 1311 · raw

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

def pk source · line 1319 · 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 1322 · raw

@+b:U32 -> Bool

def dec.pick source · line 1325 · raw

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

def dec.n source · line 1341 · 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 1353 · raw

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

def dec.b2 source · line 1357 · raw

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

def dec.b1 source · line 1361 · raw

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

def dec.lead source · line 1365 · raw

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

def dec.at source · line 1372 · raw

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

def dec.if source · line 1376 · raw

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

def dec source · line 1384 · 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 1387 · raw

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

def asc.has source · line 1403 · 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 1406 · raw

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

def probe.if source · line 1411 · 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 1418 · raw

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

def skip source · line 1422 · 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 1435 · raw

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

def rb.step source · line 1442 · 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 1447 · 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 1451 · 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 1458 · 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 1466 · 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 1498 · raw

U32

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

def vm.pcs source · line 1526 · raw

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

def vm.key source · line 1533 · raw

@st:Vm -> Sk

def pcs.eq source · line 1537 · raw

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

def sk.eq source · line 1546 · raw

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

def pcs.hash source · line 1551 · raw

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

def sk.hash source · line 1558 · raw

@k:Sk -> U32

def ix.find source · line 1562 · raw

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

def intern.bucket source · line 1569 · raw

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

def intern.add source · line 1576 · raw

@m:Maybe<&2, List<&2, Ix>> -> @+k:Sk -> @+n:U32 -> List<&2, Ix>

def intern.if source · line 1583 · raw

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

def intern.full source · line 1590 · raw

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

def intern source · line 1600 · raw

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

A full cache is not searched; the plain Pike VM handles the remaining text.

def sym.caps source · line 1603 · raw

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

def sym.ths source · line 1606 · raw

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

def sym.src source · line 1614 · raw

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

The index in the last slot.

def sym.saves source · line 1624 · 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 1635 · raw

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

def sym.fresh source · line 1642 · raw

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

def op.same source · line 1649 · raw

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

def ops.same source · line 1656 · raw

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

def tr.of source · line 1665 · raw

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

def sym.lr source · line 1672 · raw

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

def sym.hit source · line 1677 · raw

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

def sym.close source · line 1690 · 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 1695 · 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 1702 · raw

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

def caps.at source · line 1706 · raw

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

def caps.of.if source · line 1713 · 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 1720 · raw

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

def saves.put source · line 1723 · raw

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

def replay source · line 1730 · 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 1737 · 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 1745 · 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 1753 · 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 1767 · raw

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

def rq.of source · line 1771 · raw

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

def rq.store source · line 1775 · 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 1781 · raw

@lr:Lr -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:Trie<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 1786 · raw

@room:Bool -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:Trie<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 1801 · raw

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

def spin.tr source · line 1808 · raw

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

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

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

def spin.state source · line 1819 · raw

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

def spin source · line 1823 · raw

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

def ar.fill source · line 1843 · raw

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

def ar.reset.size source · line 1850 · 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 1858 · raw

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

def ar.reset source · line 1863 · raw

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

def ar.new source · line 1867 · raw

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

def ar.list.go source · line 1870 · 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 1879 · 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 1883 · raw

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

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

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

def ar.src source · line 1891 · 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 1898 · 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 1902 · 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 1911 · 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 1915 · 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 1922 · 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 1926 · raw

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

def ar.cached source · line 1936 · 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 1950 · 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 1961 · raw

@ar:Ar -> Qst

def qa.seed source · line 1968 · raw

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

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

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

def qa.from source · line 1979 · raw

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

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

@r:Pair(Ar, Vm) -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:Trie<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 1987 · raw

@r:Pair(Ar, Vm) -> @s:Pair(Array<U32>, Dc) -> @+j:U32 -> @tab:Array<Tr> -> @+keys:Trie<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 1992 · raw

@s:Pair(Array<U32>, Dc) -> @+j:U32 -> @tab:Array<Tr> -> @+keys:Trie<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 1995 · raw

@r:Pair(Array<Tr>, Tr) -> @a:Array<U32> -> @+keys:Trie<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 2005 · raw

@ok:Bool -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:Trie<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 2013 · raw

@s:Pair(Array<U32>, Dc) -> @+j:U32 -> @tab:Array<Tr> -> @+keys:Trie<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 2017 · raw

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

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

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

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

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

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

@same:Bool -> @a:Array<U32> -> @tab:Array<Tr> -> @+keys:Trie<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 2039 · raw

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

def qa.end.vm source · line 2043 · 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 2047 · 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 2051 · 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 2063 · 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 2085 · 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.if source · line 2090 · raw

@use:Bool -> @+len:U32 -> @+from: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 large programs use the plain VM; long large programs can use 2048 states.

def exec.bytes.go source · line 2100 · raw

@plain:Bool -> @+len:U32 -> @+from: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>>>)

def exec.bytes.run source · line 2103 · raw

@b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def rev.best source · line 2108 · raw

@hit:Bool -> @+i:U32 -> @prev:Maybe<&2, U32> -> Maybe<&2, U32>

def rev.bits.after source · line 2122 · raw

@step:Bs -> @a:Array<U32> -> @best:Maybe<&2, U32> -> @+i:U32 -> RevBits

def rev.bits.char source · line 2126 · raw

@valid:Bool -> @a:Array<U32> -> @+mask:U32 -> @best:Maybe<&2, U32> -> @+c:U32 -> @+i:U32 -> @+sets:List<&2, Bit> -> RevBits

def rev.bits.read source · line 2133 · raw

@r:Pair(Array<U32>, U32) -> @+mask:U32 -> @best:Maybe<&2, U32> -> @+i:U32 -> @+sets:List<&2, Bit> -> RevBits

def rev.bits.walk source · line 2137 · raw

@fuel:Nat -> @r:RevBits -> @+i:U32 -> @+sets:List<&2, Bit> -> RevBits

def rev.bits.result source · line 2149 · raw

@done:Bool -> @r:RevBits -> Rv

def rev.bits.run source · line 2153 · raw

@a:Array<U32> -> @+end:U32 -> @bits:Bits -> Rv

def rev.min source · line 2166 · raw

@m:Maybe<&2, U32> -> @prev:Maybe<&2, U32> -> Maybe<&2, U32>

def rev.seek source · line 2177 · raw

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

def rev.abort source · line 2181 · raw

@r:RevPhase -> RevFound

def rev.candidates source · line 2188 · raw

@fuel:Nat -> @r:RevPhase -> @+needle:String -> @+bits:Bits -> RevFound

def exec.bytes.at source · line 2208 · raw

@b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @+k:U32 -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def rev.confirm.best source · line 2212 · raw

@best:Maybe<&2, U32> -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def rev.confirm source · line 2220 · raw

@r:RevFound -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def exec.bytes.candidate source · line 2228 · raw

@r:Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, U32>) -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def exec.bytes.reverse source · line 2236 · raw

@r:Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, U32>) -> @bits:Bits -> @+needle:String -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def exec.bytes.select source · line 2240 · raw

@rev:Maybe<&2, Bits> -> @r:Pair(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, U32>) -> @+needle:String -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def exec.bytes.must.hit source · line 2248 · raw

@b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @rev:Maybe<&2, Bits> -> @+c:U32 -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def exec.bytes.must source · line 2252 · raw

@m:Maybe<&2, U32> -> @rev:Maybe<&2, Bits> -> @b:0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes -> @+plain:Bool -> @+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(0x49814d83de8f70993a43e1002be29ecd/bytes.Bytes, Maybe<&2, List<&2, Maybe<&2, U32>>>)

def exec.bytes source · line 2259 · 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 2264 · 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 2269 · 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 2272 · 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 2276 · raw

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

def rt.at source · line 2283 · raw

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

def rt.skip source · line 2287 · raw

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

def rt.next source · line 2292 · 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 2303 · 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 2321 · raw

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

def bits.bytes source · line 2325 · 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 2329 · 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 2338 · 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 2342 · raw

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

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