internlm/Lean-Github huggingface dataset:
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
case inl
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) (currentSave.set ⟨offset✝, ⋯⟩ (some pos)) matched saveSlots ⟨target', ⋯⟩
      (stack.push (StackEntry.restore currentSave)) =
    (matched', next', saveSlots')
j : Fin nfa.nodes.size
hj✝ : StackEntry.explore j ∈ stack.push (StackEntry.restore currentSave)
hj : StackEntry.explore j ∈ stack
⊢ ↑j ∈ nfa.εClosure ↑i
Tactic:
exact inv.2 j hj
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) (currentSave.set ⟨offset✝, ⋯⟩ (some pos)) matched saveSlots ⟨target', ⋯⟩
      (stack.push (StackEntry.restore currentSave)) =
    (matched', next', saveSlots')
j : Fin nfa.nodes.size
hj✝ : StackEntry.explore j ∈ stack.push (StackEntry.restore currentSave)
hj : StackEntry.explore j = StackEntry.restore currentSave
⊢ ↑j ∈ nfa.εClosure ↑i
Tactic:
contradiction
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
have inv' : UpperInvExploreεClosure nfa i ⟨target', isLt⟩ stack :=
  ⟨εClosure_snoc inv.1 (by simp [εStep, Node.εStep, hn]), inv.2⟩
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
inv' : UpperInvExploreεClosure nfa i ⟨target', isLt⟩ stack
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
inv' : UpperInvExploreεClosure nfa i ⟨target', isLt⟩ stack
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
exact upper_bound_exploreεClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ ↑⟨target', isLt⟩ ∈ nfa.εStep ↑target
Tactic:
simp [εStep, Node.εStep, hn]
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
hn : nfa[↑target] = Node.done
h :
  εClosure nfa pos (next.insert target) currentSave (HOrElse.hOrElse matched fun x => some currentSave)
      (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
exact upper_bound_εClosure h inv.2
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
c✝ : Char
next✝ : ℕ
hn : nfa[↑target] = Node.char c✝ next✝
h :
  εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
exact upper_bound_εClosure h inv.2
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
cs✝ : Data.Classes
next✝ : ℕ
hn : nfa[↑target] = Node.sparse cs✝ next✝
h :
  εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
exact upper_bound_εClosure h inv.2
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_exploreεClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
exact upper_bound_εClosure h inv.2
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
h : εClosure nfa pos next currentSave matched saveSlots stack = (matched', next', saveSlots')
inv : UpperInvεClosure nfa i stack
⊢ UpperBoundεClosure nfa i next next'
Tactic:
unfold εClosure at h
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h :
  (if hemp : stack.isEmpty = true then (matched, next, saveSlots)
    else
      let entry := stack.back' hemp;
      let stack' := stack.pop;
      let_fun this := ⋯;
      match entry with
      | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
      | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h :
  (if hemp : stack.isEmpty = true then (matched, next, saveSlots)
    else
      let entry := stack.back' hemp;
      let stack' := stack.pop;
      let_fun this := ⋯;
      match entry with
      | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
      | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Tactic:
split at h
Proof state after:
case inl
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'

case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    let stack' := stack.pop;
    let_fun this := ⋯;
    match entry with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
case inl
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'

case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    let stack' := stack.pop;
    let_fun this := ⋯;
    match entry with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Tactic:
next =>
  simp at h
  simp [h]
  intro j hj
  exact .inl hj
Proof state after:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    let stack' := stack.pop;
    let_fun this := ⋯;
    match entry with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    let stack' := stack.pop;
    let_fun this := ⋯;
    match entry with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Tactic:
next hemp =>
  simp at h
  have : stack.pop.size < stack.size := Array.lt_size_of_pop_of_not_empty _ (by assumption)
  split at h
  next target heq =>
    have inv' : UpperInvExploreεClosure nfa i target stack.pop :=
      ⟨inv target (heq ▸ Array.mem_back' hemp), fun j hj => inv j (Array.mem_of_mem_pop _ _ hj)⟩
    exact upper_bound_exploreεClosure h inv'
  next =>
    have inv' : UpperInvεClosure nfa i stack.pop := fun j hj => inv j (Array.mem_of_mem_pop _ _ hj)
    exact upper_bound_εClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Tactic:
simp at h
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ UpperBoundεClosure nfa i next next'
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ UpperBoundεClosure nfa i next next'
Tactic:
simp [h]
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ UpperBoundεClosure nfa i next' next'
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ UpperBoundεClosure nfa i next' next'
Tactic:
intro j hj
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
j : Fin nfa.nodes.size
hj : j ∈ next'
⊢ j ∈ next' ∨ ↑j ∈ nfa.εClosure ↑i
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
j : Fin nfa.nodes.size
hj : j ∈ next'
⊢ j ∈ next' ∨ ↑j ∈ nfa.εClosure ↑i
Tactic:
exact .inl hj
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_εClosure
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
hemp : ¬stack.isEmpty = true
h :
  (let entry := stack.back' hemp;
    let stack' := stack.pop;
    let_fun this := ⋯;
    match entry with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'
Tactic:
simp at h
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
i : Fin nfa.nodes.size
inv : UpperInvεClosure nfa i stack
hemp : ¬stack.isEmpty = true
h :
  (match stack.back' hemp with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack.pop) =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i next next'