Theorem: Regex.VM.exploreεClosure_mem_done_iff
Proof state before:
case mp
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 : (∃ i ∈ next, nfa[i] = Node.done) ↔ matched.isSome = true
hmem : target ∉ next
h :
  (match hn : nfa[↑target] with
    | Node.epsilon target' =>
      exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack
    | Node.split target₁ target₂ =>
      exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁, ⋯⟩
        (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
    | Node.save offset target' =>
      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
    | Node.done =>
      εClosure nfa pos (next.insert target) currentSave (HOrElse.hOrElse matched fun x => some currentSave)
        (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.char c next_1 =>
      εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.sparse cs next_1 =>
      εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.fail => εClosure nfa pos (next.insert target) currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
hn : nfa[target] ≠ Node.done
⊢ (∃ i ∈ next.insert target, nfa[i] = Node.done) → matched.isSome = true

case mpr
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 : (∃ i ∈ next, nfa[i] = Node.done) ↔ matched.isSome = true
hmem : target ∉ next
h :
  (match hn : nfa[↑target] with
    | Node.epsilon target' =>
      exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack
    | Node.split target₁ target₂ =>
      exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁, ⋯⟩
        (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
    | Node.save offset target' =>
      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
    | Node.done =>
      εClosure nfa pos (next.insert target) currentSave (HOrElse.hOrElse matched fun x => some currentSave)
        (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.char c next_1 =>
      εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.sparse cs next_1 =>
      εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.fail => εClosure nfa pos (next.insert target) currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
hn : nfa[target] ≠ Node.done
⊢ matched.isSome = true → ∃ i ∈ next.insert target, nfa[i] = Node.done
Tactic:
. intro h
  have ⟨i, hmem', hn'⟩ := h
  cases SparseSet.eq_or_mem_of_mem_insert hmem' with
  | inl heq =>
    simp [heq] at hn'
    simp [hn'] at hn
  | inr hmem' => exact inv.mp ⟨i, hmem', hn'⟩
Proof state after:
case mpr
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 : (∃ i ∈ next, nfa[i] = Node.done) ↔ matched.isSome = true
hmem : target ∉ next
h :
  (match hn : nfa[↑target] with
    | Node.epsilon target' =>
      exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack
    | Node.split target₁ target₂ =>
      exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁, ⋯⟩
        (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
    | Node.save offset target' =>
      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
    | Node.done =>
      εClosure nfa pos (next.insert target) currentSave (HOrElse.hOrElse matched fun x => some currentSave)
        (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.char c next_1 =>
      εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.sparse cs next_1 =>
      εClosure nfa pos (next.insert target) currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack
    | Node.fail => εClosure nfa pos (next.insert target) currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
hn : nfa[target] ≠ Node.done
⊢ matched.isSome = true → ∃ i ∈ next.insert target, nfa[i] = Node.done