regex.bend checks

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

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

2 imports

import Base
import 0x6c784a08486e2e02415e89c5249e9e8a/unicode.bend as U

Types

type Item source · line 12 · raw

Data

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

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

type Node source · line 17 · raw

Data

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

NEmpty
```
Node
```

NSet

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

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

type Tok source · line 27 · raw

Data

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

TRep

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

type Esc source · line 73 · raw

Data

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

EItems

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

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

type Cs source · line 161 · raw

Data

CsGo

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

CsDone

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

CsFail
```
Cs
```

type Lx source · line 243 · raw

Data

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

type Num source · line 249 · raw

Data

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

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

type Frame source · line 395 · raw

Data

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

Frame

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

type Ps source · line 399 · raw

Data

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

Ps

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

PsFail
```
Ps
```

type Inst source · line 532 · raw

Data

ISet

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

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

type Regex source · line 583 · raw

Data

prog: the program; fuel: enough steps for one closure; slots: two per group, group 0 included.

Regex

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

type Th source · line 648 · raw

Data

A thread: its pc and its capture slots.

Th

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

type Cl source · line 653 · 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:List<&2, U32> -> @out:List<&2, Th> -> Cl

type Sc source · line 708 · 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 754 · 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 787 · raw

Data

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

Definitions

def lit source · line 34 · raw

@+c:U32 -> Node

def is_digit source · line 37 · raw

@+c:U32 -> Bool

def is_word source · line 40 · raw

@+c:U32 -> Bool

def is_alnum source · line 43 · raw

@+c:U32 -> Bool

def perl.d source · line 47 · raw

List<&2, Item>

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

def perl.D source · line 50 · raw

List<&2, Item>

def perl.w source · line 53 · raw

List<&2, Item>

def perl.W source · line 56 · raw

List<&2, Item>

def perl.s source · line 59 · raw

List<&2, Item>

def perl.S source · line 62 · raw

List<&2, Item>

def cats source · line 65 · raw

List<&2, String>

def prop.if source · line 79 · raw

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

def prop.ok source · line 86 · raw

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

def prop.name source · line 89 · raw

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

def prop source · line 99 · raw

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

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

def esc.other source · line 109 · raw

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

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

def esc source · line 117 · raw

@s:String -> Esc

The text after a backslash.

def class.range source · line 166 · raw

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

def class.hi source · line 173 · raw

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

def class.lo source · line 185 · raw

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

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

def class.esc source · line 196 · raw

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

def class.step source · line 208 · raw

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

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

def class.run source · line 224 · raw

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

fuel: every step eats at least one char.

def class source · line 237 · raw

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

def num.add source · line 252 · raw

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

def num.go source · line 255 · raw

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

def num source · line 270 · raw

@s:String -> Num

def lex.rep source · line 278 · raw

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

A trailing "?" makes a repetition lazy.

def Num.n source · line 285 · raw

@m:Num -> U32

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

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

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

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

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

def lex.class source · line 319 · raw

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

def lex.esc source · line 328 · raw

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

def lex.step source · line 339 · raw

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

def lex source · line 378 · raw

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

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

def cat source · line 402 · raw

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

def seq.go source · line 413 · raw

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

def seq source · line 420 · raw

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

def alt.go source · line 423 · raw

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

def group source · line 430 · raw

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

def rep.copies source · line 437 · raw

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

def rep.opt source · line 444 · raw

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

def rep.inf source · line 452 · raw

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

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

def rep.fin source · line 459 · raw

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

def rep source · line 466 · raw

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

def rep.ok source · line 470 · raw

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

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

def parse.rep source · line 477 · raw

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

def parse.open source · line 488 · raw

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

def parse.close source · line 495 · raw

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

def parse.tok source · line 502 · raw

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

def parse.step source · line 515 · raw

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

def parse source · line 522 · raw

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

def size source · line 540 · raw

@n:Node -> U32

def emit source · line 560 · raw

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

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

def build source · line 586 · raw

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

def compile.fin source · line 590 · raw

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

def compile.parse source · line 601 · raw

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

def compile source · line 609 · raw

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

The pattern, or None for a syntax error.

def item.has source · line 615 · raw

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

def items.has source · line 622 · raw

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

def word source · line 629 · raw

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

def assert.ok source · line 636 · raw

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

def close.assert source · line 656 · raw

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

def close.inst source · line 663 · raw

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

def close.seen source · line 682 · raw

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

ponytail: list lookup and list membership make each step O(m) per thread, so a match costs O(n * m^2) for n chars and m instructions; use arrays if m grows large.

def close.step source · line 689 · raw

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

def close source · line 694 · raw

@fuel:Nat -> @+prog:List<&2, 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 711 · 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 718 · 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.inst source · line 725 · raw

@i:Maybe<&2, Inst> -> @c:Maybe<&2, Char> -> @+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 734 · raw

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

def scan.step source · line 742 · raw

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

def scan source · line 746 · raw

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

def seed source · line 758 · 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 run.close source · line 765 · raw

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

def run.step source · line 769 · raw

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

def run.end source · line 773 · raw

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

def run source · line 778 · raw

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

pos: the position of s's head.

def spans source · line 790 · raw

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

def find.spans source · line 799 · raw

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

def find source · line 807 · raw

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

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

def is_match source · line 812 · raw

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