Theorem: Regex.VM.lower_inv_exploreεClosure
Proof state before:
case h_3
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
h :
  (if h : offset✝ < currentSave.size then
      exploreεClosure nfa pos (next.insert target) (currentSave.set ⟨offset✝, ⋯⟩ (some pos)) matched saveSlots
        ⟨target'✝, ⋯⟩ (stack.push (StackEntry.restore currentSave))
    else exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack) =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]

case h_4
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
heq✝ : 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')
⊢ LowerInvεClosure nfa next' #[]

case h_5
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
c✝ : Char
next✝ : ℕ
heq✝ : nfa[↑target] = Node.char c✝ next✝
h :
  εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]

case h_6
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
cs✝ : Data.Classes
next✝ : ℕ
heq✝ : nfa[↑target] = Node.sparse cs✝ next✝
h :
  εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]

case h_7
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
next _ target' hn =>
  have isLt := nfa.inBounds' target hn
  split at h
  next =>
    have inv' : LowerInvExploreεClosure nfa (next.insert target) ⟨target', isLt⟩ (stack.push (.restore currentSave)) := by
      intro i j hi hj
      cases SparseSet.eq_or_mem_of_mem_insert hi with
      | inl htarget =>
        subst htarget
        simp [εStep, Node.εStep, hn] at hj
        exact .inr (.inl (Fin.eq_of_val_eq hj))
      | inr hnext =>
        match inv i j hnext hj with
        | .inl hnext => exact .inl (SparseSet.mem_insert_of_mem hnext)
        | .inr (.inl htarget) => exact .inl (htarget ▸ SparseSet.mem_insert)
        | .inr (.inr hstack) => exact .inr (.inr ((Array.mem_push ..).mpr (.inl hstack)))
    exact lower_inv_exploreεClosure h inv'
  next =>
    have inv' : LowerInvExploreεClosure nfa (next.insert target) ⟨target', isLt⟩ stack := by
      intro i j hi hj
      cases SparseSet.eq_or_mem_of_mem_insert hi with
      | inl htarget =>
        subst htarget
        simp [εStep, Node.εStep, hn] at hj
        exact .inr (.inl (Fin.eq_of_val_eq hj))
      | inr hnext =>
        match inv i j hnext hj with
        | .inl hnext => exact .inl (SparseSet.mem_insert_of_mem hnext)
        | .inr (.inl htarget) => exact .inl (htarget ▸ SparseSet.mem_insert)
        | .inr (.inr hstack) => exact .inr (.inr hstack)
    exact lower_inv_exploreεClosure h inv'
Proof state after:
case h_4
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
heq✝ : 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')
⊢ LowerInvεClosure nfa next' #[]

case h_5
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
c✝ : Char
next✝ : ℕ
heq✝ : nfa[↑target] = Node.char c✝ next✝
h :
  εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]

case h_6
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
cs✝ : Data.Classes
next✝ : ℕ
heq✝ : nfa[↑target] = Node.sparse cs✝ next✝
h :
  εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]

case h_7
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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]