BoundedBacktracker

An NFA backed bounded backtracker for executing regex searches with capturing groups (BoundedBacktracker.slots).

This regex engine only implements leftmost-first match semantics and only supports leftmost searches. By design, this backtracking regex engine is bounded. This bound is implemented by not visiting any combination of NFA state ID and position in a haystack more than once.

All searches execute in linear time with respect to the size of the regular expression and search text.

def BoundedBacktracker.Array.Ref.mkRef {α β : Type} [Inhabited β] (arr : Array α) : ST.Ref β (Array α)

make reference of array

Equations

• BoundedBacktracker.Array.Ref.mkRef arr = match ST.Prim.mkRef arr default with | EStateM.Result.ok r a => r

def BoundedBacktracker.Array.Ref.getRefValue {α β : Type} [Inhabited β] (ref : ST.Ref β (Array α)) : Array α

get array of reference

Equations

• BoundedBacktracker.Array.Ref.getRefValue ref = match ST.Prim.Ref.get ref default with | EStateM.Result.ok r a => r

def BoundedBacktracker.Array.Ref.modifyRefValue {α β : Type} [Inhabited β] [DecidableEq β] (ref : ST.Ref β (Array α)) (index : Nat) (value : α) : ST.Ref β (Array α)

modify array, try to perform the update destructively

Equations

• One or more equations did not get rendered due to their size.

instance BoundedBacktracker.Array.Ref.instInhabitedRefArray_regex {α β : Type} [Inhabited β] : Inhabited (ST.Ref β (Array α))

Equations

• BoundedBacktracker.Array.Ref.instInhabitedRefArray_regex = { default := BoundedBacktracker.Array.Ref.mkRef #[] }

structure BoundedBacktracker.CharPos (s : String.Slice) : Type

Char position in a slice of some underlying string.

• pos : s.Pos

  current position

• curr? : Option Char

  char at current position

• prev? : Option Char

  char at previous position

@[reducible, inline]

abbrev BoundedBacktracker.CharPos.Pair (s : String.Slice) : Type

Equations

• BoundedBacktracker.CharPos.Pair s = { p : s.Pos × s.Pos // p.fst ≤ p.snd }

instance BoundedBacktracker.instInhabitedCharPosDefaultSlice : Inhabited (CharPos default)

Equations

• BoundedBacktracker.instInhabitedCharPosDefaultSlice = { default := { pos := default } }

instance BoundedBacktracker.instToStringCharPos {s : String.Slice} : ToString (CharPos s)

Equations

• One or more equations did not get rendered due to their size.

instance BoundedBacktracker.instToStringPos_regex {s : String.Slice} : ToString s.Pos

Equations

• BoundedBacktracker.instToStringPos_regex = { toString := fun (pos : s.Pos) => toString pos.offset }

def BoundedBacktracker.CharPos.create (s : String.Slice) («at» : s.Pos) : CharPos s

create a CharPos from s and position «at»

Equations

• One or more equations did not get rendered due to their size.

def BoundedBacktracker.CharPos.prev {s : String.Slice} (cp : CharPos s) : Option (CharPos s)

to prev position of cp

Equations

• cp.prev = if h : cp.pos ≠ s.startPos then some (BoundedBacktracker.CharPos.create s (cp.pos.prev h)) else none

def BoundedBacktracker.CharPos.prevn {s : String.Slice} (offset : Nat) (cp : CharPos s) : Option (CharPos s)

Equations

• BoundedBacktracker.CharPos.prevn offset cp = if offset ≤ cp.pos.offset.byteIdx then BoundedBacktracker.CharPos.prevn.loop offset (some cp) else none

@[irreducible]

def BoundedBacktracker.CharPos.prevn.loop {s : String.Slice} (offset : Nat) (cp : Option (CharPos s)) : Option (CharPos s)

Equations

• One or more equations did not get rendered due to their size.

def BoundedBacktracker.CharPos.next {s : String.Slice} (cp : CharPos s) : CharPos s

to next position of cp

Equations

• One or more equations did not get rendered due to their size.

def BoundedBacktracker.CharPos.atStart {s : String.Slice} (cp : CharPos s) : Bool

is CharPos at start position

Equations

• cp.atStart = decide (cp.pos = s.startPos)

def BoundedBacktracker.CharPos.atStop {s : String.Slice} (cp : CharPos s) : Bool

is CharPos at stop position

Equations

• cp.atStop = decide (cp.pos = s.endPos)

inductive BoundedBacktracker.Frame (n : Nat) (s : String.Slice) : Type

Represents a stack frame on the heap while doing backtracking.

• Step {n : Nat} {s : String.Slice} (sid : Fin n) («at» : CharPos s) : Frame n s

  Look for a match starting at sid and the given position in the haystack.

• RestoreCapture {n : Nat} {s : String.Slice} (role : NFA.Capture.Role) (slot : Nat) (pos : Option s.Pos) : Frame n s

  Reset the given slot to the given pos (which might be None).

instance BoundedBacktracker.instToStringFrame {n : Nat} {s : String.Slice} : ToString (Frame n s)

Equations

• One or more equations did not get rendered due to their size.

structure BoundedBacktracker.HalfMatch (s : String.Slice) : Type

A representation of "half" of a match reported by a DFA.

• pattern : NFA.PatternID

  The pattern ID.

• offset : s.Pos

  The offset of the match.

instance BoundedBacktracker.instInhabitedHalfMatch {s : String.Slice} : Inhabited (HalfMatch s)

Equations

• BoundedBacktracker.instInhabitedHalfMatch = { default := { pattern := 0, offset := default } }

instance BoundedBacktracker.instToStringHalfMatch {s : String.Slice} : ToString (HalfMatch s)

Equations

• One or more equations did not get rendered due to their size.

@[reducible, inline]

abbrev BoundedBacktracker.Stack (n : Nat) (s : String.Slice) : Type

The stack of frames

Equations

• BoundedBacktracker.Stack n s = List (BoundedBacktracker.Frame n s)

@[inline]

def BoundedBacktracker.Stack.push {n : Nat} {s : String.Slice} (stack : Stack n s) (v : Frame n s) : Stack n s

Push frame to stack

Equations

• stack.push v = v :: stack

@[inline]

def BoundedBacktracker.Stack.pop? {n : Nat} {s : String.Slice} (stack : Stack n s) : Option (Frame n s × Stack n s)

pop head frame from stack

Equations

• BoundedBacktracker.Stack.pop? [] = none
• BoundedBacktracker.Stack.pop? (head :: tail) = some (head, tail)

theorem BoundedBacktracker.Stack.pop?_some_lt {n : Nat} {s : String.Slice} {a : Frame n s} {s1 : Stack n s} (s✝ : Stack n s) (h : s✝.pop? = some (a, s1)) : List.length s1 < List.length s✝

@[inline]

def BoundedBacktracker.Stack.append {n : Nat} {s : String.Slice} (stack1 stack2 : Stack n s) : Stack n s

append stacks

Equations

• stack1.append [v1, v2] = v2 :: v1 :: stack1
• stack1.append stack2 = (List.reverse stack2).append stack1

@[inline]

def BoundedBacktracker.Stack.toStack {n : Nat} {s : String.Slice} (arr : Array (Frame n s)) : Stack n s

Equations

• BoundedBacktracker.Stack.toStack arr = arr.toList

instance BoundedBacktracker.instInhabitedStackDefaultNatSlice : Inhabited (Stack default default)

Equations

• BoundedBacktracker.instInhabitedStackDefaultNatSlice = { default := [] }

@[reducible, inline]

abbrev BoundedBacktracker.Visited : Type

The encoded set of (Fin n, HaystackOffset) pairs that have been visited by the backtracker within a single search. Optimization: encode as bits

Equations

• BoundedBacktracker.Visited = Array UInt8

@[reducible, inline]

abbrev BoundedBacktracker.SlotEntry (s : String.Slice) : Type

SlotEntry consists of slot, group and char pos in s

Equations

• BoundedBacktracker.SlotEntry s = (Nat × Nat × Option s.Pos)

def BoundedBacktracker.SearchState.Slots.Valid {s : String.Slice} (slots : Array (SlotEntry s)) : Prop

Equations

• One or more equations did not get rendered due to their size.

@[reducible, inline]

abbrev BoundedBacktracker.SlotsValid (s : String.Slice) : Type

Equations

• BoundedBacktracker.SlotsValid s = { slots : Array (BoundedBacktracker.SlotEntry s) // BoundedBacktracker.SearchState.Slots.Valid slots }

theorem BoundedBacktracker.valid_of_range_map (s : String.Slice) (slots : Array (SlotEntry s)) (f : Nat → SlotEntry s) (hf : f = fun (i : Nat) => (i, i.div 2, none)) (h : List.map f (List.range slots.size) = slots.toList) : SearchState.Slots.Valid slots

def BoundedBacktracker.Capture.toSlot (c : NFA.Capture) : Nat

Equations

• BoundedBacktracker.Capture.toSlot c = match c.role with | NFA.Capture.Role.Start => c.group * 2 | NFA.Capture.Role.End => c.group * 2 + 1

def BoundedBacktracker.toSlotEntry {s : String.Slice} (c : NFA.Capture) : SlotEntry s

Equations

• BoundedBacktracker.toSlotEntry c = (BoundedBacktracker.Capture.toSlot c, c.group, none)

theorem BoundedBacktracker.valid_map_of_valid (s : String.Slice) (captures : Array NFA.Capture) (h : NFA.Capture.Valid captures) (slots : Array (SlotEntry s)) (hs : slots = Array.map toSlotEntry captures) (slot : { slot : SlotEntry s // slot ∈ slots ∧ slot.fst = slot.snd.fst * 2 + 1 }) : ∃ (slot' : SlotEntry s), slot' ∈ slots ∧ slot.val.snd.fst = slot'.snd.fst ∧ slot'.fst = slot'.snd.fst * 2

theorem BoundedBacktracker.mem_range_map_of_mem {s : String.Slice} (captures : Array NFA.Capture) (slots : Array (SlotEntry s)) (f : Nat → SlotEntry s) (hf : f = fun (i : Nat) => (i, i.div 2, none)) (heq : Array.map f (Array.range slots.size) = slots) (hsize : slots.size = match (Array.map Capture.toSlot captures).max? with | some m => m + 1 | none => 0) (capture : NFA.Capture) : capture ∈ captures → toSlotEntry capture ∈ slots

structure BoundedBacktracker.SearchState (n : Nat) (input : String.Slice) : Type

State of the backtracking search

• stack : Stack n input

  Stack used on the heap for doing backtracking

• visited : ST.Ref Nat Visited

  The encoded set of (Fin n, HaystackOffset) pairs that have been visited by the backtracker within a single search.

• countVisited : Nat

  count of pairs that have been visited

• sid : Fin n

  current state

• at : CharPos input

  position in input string

• slots : Array (SlotEntry input)

  slots, positions of captures in input

• slotsValid : Slots.Valid self.slots

  slots are valid

• recentCaptures : Array (Option (input.Pos × input.Pos))

  recent captures of capture groups

• logEnabled : Bool

  is logging enabled

• msgs : Array String

  log msgs

• halfMatch : Option (HalfMatch input)

  HalfMatch

• backtracks : Nat

  count of backtracks

theorem BoundedBacktracker.SearchState.ext_iff {n : Nat} {input : String.Slice} {x y : SearchState n input} : x = y ↔ x.stack = y.stack ∧ x.visited = y.visited ∧ x.countVisited = y.countVisited ∧ x.sid = y.sid ∧ x.at = y.at ∧ x.slots = y.slots ∧ x.recentCaptures = y.recentCaptures ∧ x.logEnabled = y.logEnabled ∧ x.msgs = y.msgs ∧ x.halfMatch = y.halfMatch ∧ x.backtracks = y.backtracks

theorem BoundedBacktracker.SearchState.ext {n : Nat} {input : String.Slice} {x y : SearchState n input} (stack : x.stack = y.stack) (visited : x.visited = y.visited) (countVisited : x.countVisited = y.countVisited) (sid : x.sid = y.sid) («at» : x.at = y.at) (slots : x.slots = y.slots) (recentCaptures : x.recentCaptures = y.recentCaptures) (logEnabled : x.logEnabled = y.logEnabled) (msgs : x.msgs = y.msgs) (halfMatch : x.halfMatch = y.halfMatch) (backtracks : x.backtracks = y.backtracks) : x = y

def BoundedBacktracker.SearchState.fromNfa (nfa : NFA.Checked.NFA) (input : String.Slice) («at» : input.Pos) (logEnabled : Bool) (h : 0 < nfa.n) : SearchState nfa.n input

create the SearchState from an NFA

Equations

• One or more equations did not get rendered due to their size.

theorem BoundedBacktracker.SearchState.slots_of_modify_valid {s : String.Slice} (slots : Array (SlotEntry s)) (h : Slots.Valid slots) (slot : Nat) (f : Option s.Pos → Option s.Pos) : Slots.Valid (slots.modify slot (Prod.map id (Prod.map id f)))

theorem BoundedBacktracker.SearchState.slots_of_map_valid {s : String.Slice} (slots : Array (SlotEntry s)) (h : Slots.Valid slots) (f : SlotEntry s → SlotEntry s) (hf : ∀ (x : SlotEntry s), (f x).fst = x.fst ∧ (f x).snd.fst = x.snd.fst) : Slots.Valid (Array.map f slots)

instance BoundedBacktracker.instNonemptyVisited : Nonempty Visited

def BoundedBacktracker.Visited.index {n : Nat} {s : String.Slice} (sid : Fin n) (cp : CharPos s) : Nat

get encoded index of Fin n and CharPos in visited array

Equations

• BoundedBacktracker.Visited.index sid cp = ↑sid * (s.endPos.offset.byteIdx - s.startPos.offset.byteIdx + 1) + cp.pos.offset.byteIdx - s.startPos.offset.byteIdx

theorem BoundedBacktracker.Visited.eq_of_linear_eq {a1 b1 a2 b2 x : Nat} (hb1 : b1 < x) (hb2 : b2 < x) (h : a1 * x + b1 = a2 * x + b2) : a1 = a2 ∧ b1 = b2

theorem BoundedBacktracker.Visited.index_injective {n : Nat} {s : String.Slice} (sid1 sid2 : Fin n) (cp1 cp2 : CharPos s) (heq : index sid1 cp1 = index sid2 cp2) : ↑sid1 = ↑sid2 ∧ cp1.pos.offset.byteIdx = cp2.pos.offset.byteIdx

index is injective.

def BoundedBacktracker.Visited.checkVisited {n : Nat} {s : String.Slice} (state : SearchState n s) : Bool × SearchState n s

Check if current Fin n and CharPos in SearchState is already visited. If not visited mark pair as visited.

Equations

• One or more equations did not get rendered due to their size.

def BoundedBacktracker.Visited.checkVisited' {n : Nat} {s : String.Slice} (state : SearchState n s) : Bool × SearchState n s

Check if current Fin n and CharPos in SearchState is already visited. If not visited mark pair as visited.

Equations

• One or more equations did not get rendered due to their size.

theorem BoundedBacktracker.Visited.checkVisited'_false_lt {n : Nat} {input : String.Slice} {s1 : SearchState n input} (s : SearchState n input) (h : checkVisited' s = (false, s1)) : s.countVisited < s1.countVisited

theorem BoundedBacktracker.Visited.checkVisited'_true_eq {n : Nat} {input : String.Slice} {s1 : SearchState n input} (s : SearchState n input) (h : checkVisited' s = (true, s1)) : s.countVisited = s1.countVisited ∧ List.length s.stack = List.length s1.stack

theorem BoundedBacktracker.withMsg_eq {input : String.Slice} {nfa : NFA.Checked.NFA} {s s1 : SearchState nfa.n input} {msg : Unit → String} (h : BoundedBacktracker.withMsg✝ msg s = s1) : s.countVisited = s1.countVisited ∧ s.stack = s1.stack

theorem BoundedBacktracker.step_match_countVisited_eq {n : Nat} {s : String.Slice} {p : NFA.PatternID} (s1 s2 : SearchState n s) (h : BoundedBacktracker.step_match✝ p s1 = s2) : s1.countVisited = s2.countVisited

theorem BoundedBacktracker.toNextStep_countVisited_eq {s : String.Slice} (nfa : NFA.Checked.NFA) (state : NFA.Checked.State nfa.n) (s1 s2 : SearchState nfa.n s) (h : BoundedBacktracker.toNextStep✝ nfa state s1 = s2) : s1.countVisited = s2.countVisited

theorem BoundedBacktracker.toNextStep_eq {input : String.Slice} {nfa : NFA.Checked.NFA} {state : NFA.Checked.State nfa.n} {s s1 : SearchState nfa.n input} {msg : Unit → String} (h : BoundedBacktracker.toNextStep✝ nfa state (BoundedBacktracker.withMsg✝ msg s) = s1) : s.countVisited = s1.countVisited

theorem BoundedBacktracker.toNextStepChecked_true_lt {input : String.Slice} (nfa : NFA.Checked.NFA) (s s1 : SearchState nfa.n input) (h : BoundedBacktracker.toNextStepChecked✝ nfa s = (true, s1)) : s.countVisited < s1.countVisited

theorem BoundedBacktracker.toNextStepChecked_false_eq {input : String.Slice} (nfa : NFA.Checked.NFA) (s s1 : SearchState nfa.n input) (h : BoundedBacktracker.toNextStepChecked✝ nfa s = (false, s1)) : s.countVisited = s1.countVisited ∧ s.stack = s1.stack

def BoundedBacktracker.steps {s : String.Slice} (nfa : NFA.Checked.NFA) (state : SearchState nfa.n s) : SearchState nfa.n s

execute next steps in NFA.

Equations

• BoundedBacktracker.steps nfa state = match BoundedBacktracker.toNextStepChecked✝ nfa state with | (true, state) => BoundedBacktracker.steps.loop nfa state | (false, state) => state

@[irreducible]

def BoundedBacktracker.steps.loop {s : String.Slice} (nfa : NFA.Checked.NFA) (state : SearchState nfa.n s) : SearchState nfa.n s

Equations

• One or more equations did not get rendered due to their size.

@[irreducible]

theorem BoundedBacktracker.steps_loop_le {input : String.Slice} (nfa : NFA.Checked.NFA) (s s1 : SearchState nfa.n input) (h : steps.loop nfa s = s1) : s.countVisited ≤ s1.countVisited

theorem BoundedBacktracker.steps_lt_or_eq_lt {input : String.Slice} (nfa : NFA.Checked.NFA) (s s1 : SearchState nfa.n input) (h : steps nfa s = s1) : s.countVisited < s1.countVisited ∨ s.countVisited = s1.countVisited ∧ List.length s.stack = List.length s1.stack

theorem BoundedBacktracker.toNextFrameStep_true_lt_or_eq_lt {input : String.Slice} (nfa : NFA.Checked.NFA) (s s1 : SearchState nfa.n input) (h : BoundedBacktracker.toNextFrameStep✝ nfa s = (true, s1)) : s.countVisited < s1.countVisited ∨ s.countVisited = s1.countVisited ∧ List.length s.stack = List.length s1.stack

theorem BoundedBacktracker.toNextFrameRestoreCapture_true_lt_or_eq_lt {s : String.Slice} {n : Nat} {s1 : SearchState n s} (slot : Nat) (offset : Option s.Pos) (stack : Stack n s) (s✝ : SearchState n s) (h : BoundedBacktracker.toNextFrameRestoreCapture✝ slot offset stack s✝ = (true, s1)) : s✝.countVisited = s1.countVisited ∧ stack = s1.stack

theorem BoundedBacktracker.toNextFrame_true_lt {input : String.Slice} (nfa : NFA.Checked.NFA) (s s1 : SearchState nfa.n input) (h : BoundedBacktracker.toNextFrame✝ nfa s = (true, s1)) : s.countVisited < s1.countVisited ∨ s.countVisited = s1.countVisited ∧ List.length s1.stack < List.length s.stack

theorem BoundedBacktracker.searchState_lexLt {input : String.Slice} (nfa : NFA.Checked.NFA) (s s1 : SearchState nfa.n input) (h1 : s.countVisited < BoundedBacktracker.visitedSize✝ s) (h2 : BoundedBacktracker.visitedSize✝¹ s = BoundedBacktracker.visitedSize✝² s1) (h : BoundedBacktracker.toNextFrame✝ nfa s = (true, s1)) : BoundedBacktracker.unvisited✝ s1 < BoundedBacktracker.unvisited✝¹ s ∨ BoundedBacktracker.unvisited✝² s1 = BoundedBacktracker.unvisited✝³ s ∧ List.length s1.stack < List.length s.stack

def BoundedBacktracker.backtrack {s : String.Slice} (nfa : NFA.Checked.NFA) (state : SearchState nfa.n s) : SearchState nfa.n s

BoundedBacktrack search

Equations

• One or more equations did not get rendered due to their size.

@[irreducible]

def BoundedBacktracker.backtrack.loop {s : String.Slice} (nfa : NFA.Checked.NFA) (state : SearchState nfa.n s) : SearchState nfa.n s

Equations

• One or more equations did not get rendered due to their size.

def BoundedBacktracker.matches (s : String.Slice) («at» : s.Pos) (nfa : NFA.Checked.NFA) (logEnabled : Bool) : Array String × Array (Option { m : String.Slice // m.isSubslice s })

Search for the first match of this regex in the haystack given and return log msgs and the matches of each capture group.

Equations

• One or more equations did not get rendered due to their size.