Theorem: Regex.VM.lower_inv_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
inv : LowerInvExploreεClosure nfa next target stack
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')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
next =>
  simp at h
  split at h
  next target' hn =>
    have isLt := nfa.inBounds' target hn
    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'
  next target₁ target₂ hn =>
    have isLt := nfa.inBounds' target hn
    have inv' : LowerInvExploreεClosure nfa (next.insert target) ⟨target₁, isLt.1⟩ (stack.push (.explore ⟨target₂, isLt.2⟩)) := 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
        cases hj with
        | inl hj => exact .inr (.inl (Fin.eq_of_val_eq hj))
        | inr hj => exact .inr (.inr ((Array.mem_push ..).mpr (.inr (by simp [hj.symm]))))
      | 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 _ 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'
  next hn =>
    have inv' : LowerInvεClosure nfa (next.insert target) 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
      | 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 hstack
    exact lower_inv_εClosure h inv'
  next _ _ hn =>
    have inv' : LowerInvεClosure nfa (next.insert target) 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
      | 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 hstack
    exact lower_inv_εClosure h inv'
  next _ _ hn =>
    have inv' : LowerInvεClosure nfa (next.insert target) 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
      | 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 hstack
    exact lower_inv_εClosure h inv'
  next hn =>
    have inv' : LowerInvεClosure nfa (next.insert target) 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
      | 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 hstack
    exact lower_inv_εClosure h inv'
Proof state after:
no goals