Theorem: Regex.VM.exploreεClosure_mem_done_iff
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
inv : (∃ i ∈ next, nfa[i] = Node.done) ↔ matched.isSome = true
h✝ : target ∉ next
h :
  (let next' := next.insert target;
    match hn : nfa[target] with
    | Node.epsilon target' =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.split target₁ target₂ =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target₁, ⋯⟩
        (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
    | Node.save offset target' =>
      let_fun isLt := ⋯;
      if h : offset < currentSave.size then
        let nextSave := currentSave.set ⟨offset, h⟩ (some pos);
        let stack' := stack.push (StackEntry.restore currentSave);
        exploreεClosure nfa pos next' nextSave matched saveSlots ⟨target', isLt⟩ stack'
      else exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.done =>
      let matched' := HOrElse.hOrElse matched fun x => some currentSave;
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched' saveSlots' stack
    | Node.char c next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.sparse cs next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.fail => εClosure nfa pos next' currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
⊢ (∃ i ∈ next', nfa[i] = Node.done) ↔ matched'.isSome = true
Tactic:
next hmem =>
  simp at h
  have inv' (hn : nfa[target] ≠ .done) : (∃ i, i ∈ next.insert target ∧ nfa[i] = .done) ↔ matched.isSome := by
    apply Iff.intro
    . 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'⟩
    . intro h
      have ⟨i, hmem', hn'⟩ := inv.mpr h
      exact ⟨i, SparseSet.mem_insert_of_mem hmem', hn'⟩
  split at h
  next hn => exact exploreεClosure_mem_done_iff h (inv' (by simp [hn]))
  next hn => exact exploreεClosure_mem_done_iff h (inv' (by simp [hn]))
  next hn =>
    split at h
    next => exact exploreεClosure_mem_done_iff h (inv' (by simp [hn]))
    next => exact exploreεClosure_mem_done_iff h (inv' (by simp [hn]))
  next hn =>
    have lhs : ∃ i, i ∈ next.insert target ∧ nfa[i] = .done := ⟨target, SparseSet.mem_insert, hn⟩
    have rhs : (matched <|> currentSave).isSome := by
      cases matched <;> simp
    have inv'' : (∃ i, i ∈ next.insert target ∧ nfa[i] = .done) ↔ (matched <|> currentSave).isSome := by
      simp only [lhs, rhs]
    exact εClosure_mem_done_iff h inv''
  next hn => exact εClosure_mem_done_iff h (inv' (by simp [hn]))
  next hn => exact εClosure_mem_done_iff h (inv' (by simp [hn]))
  next hn => exact εClosure_mem_done_iff h (inv' (by simp [hn]))
Proof state after:
no goals