Theorem: Regex.VM.mem_stack_mem_exploreεClosure (RegexCorrectness/VM/Auxiliary.lean)

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
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
hmem : StackEntry.explore i ∈ stack
⊢ i ∈ next'
Tactic:
unfold exploreεClosure at h
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
hmem : StackEntry.explore i ∈ stack
h :
  (if target ∈ next then εClosure nfa pos next currentSave matched saveSlots stack
    else
      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'

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
hmem : StackEntry.explore i ∈ stack
h :
  (if target ∈ next then εClosure nfa pos next currentSave matched saveSlots stack
    else
      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'
Tactic:
split at h
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
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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∈ next
h : εClosure nfa pos next currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ 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
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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'

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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∈ next
h : εClosure nfa pos next currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ 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
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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_εClosure h hmem
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
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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'

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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'
Tactic:
next =>
  simp at h
  split at h
  next => exact mem_stack_mem_exploreεClosure h hmem
  next => exact mem_stack_mem_exploreεClosure h ((Array.mem_push ..).mpr (.inl hmem))
  next =>
    split at h
    next => exact mem_stack_mem_exploreεClosure h ((Array.mem_push ..).mpr (.inl hmem))
    next => exact mem_stack_mem_exploreεClosure h hmem
  next => exact mem_stack_mem_εClosure h hmem
  next => exact mem_stack_mem_εClosure h hmem
  next => exact mem_stack_mem_εClosure h hmem
  next => exact mem_stack_mem_εClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∈ next
h : εClosure nfa pos next currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_εClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'
Tactic:
simp at h
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
hmem : StackEntry.explore i ∈ stack
h✝ : 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')
⊢ i ∈ next'

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
hmem : StackEntry.explore i ∈ stack
h✝ : 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')
⊢ i ∈ next'
Tactic:
split at h
State after:
case h_1
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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target'✝ : ℕ
heq✝ : nfa[↑target] = Node.epsilon target'✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'

case h_2
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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target₁✝ target₂✝ : ℕ
heq✝ : nfa[↑target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ i ∈ next'

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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'

State before:
case h_1
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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target'✝ : ℕ
heq✝ : nfa[↑target] = Node.epsilon target'✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'

case h_2
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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target₁✝ target₂✝ : ℕ
heq✝ : nfa[↑target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ i ∈ next'

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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_exploreεClosure h hmem
State after:
case h_2
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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target₁✝ target₂✝ : ℕ
heq✝ : nfa[↑target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ i ∈ next'

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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'

State before:
case h_2
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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target₁✝ target₂✝ : ℕ
heq✝ : nfa[↑target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ i ∈ next'

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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_exploreεClosure h ((Array.mem_push ..).mpr (.inl hmem))
State after:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'

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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next =>
  split at h
  next => exact mem_stack_mem_exploreεClosure h ((Array.mem_push ..).mpr (.inl hmem))
  next => exact mem_stack_mem_exploreεClosure h hmem
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'

State before:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_εClosure h hmem
State after:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'

State before:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_εClosure h hmem
State after:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'

State before:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ 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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_εClosure h hmem
State after:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'

State before:
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
i : Fin nfa.nodes.size
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_εClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target'✝ : ℕ
heq✝ : nfa[↑target] = Node.epsilon target'✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_exploreεClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
target₁✝ target₂✝ : ℕ
heq✝ : nfa[↑target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_exploreεClosure h ((Array.mem_push ..).mpr (.inl hmem))
State after:
no goals

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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'
Tactic:
split at h
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
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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
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')
⊢ i ∈ 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
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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'

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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
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')
⊢ i ∈ 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
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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_exploreεClosure h ((Array.mem_push ..).mpr (.inl hmem))
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
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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'

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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
next => exact mem_stack_mem_exploreεClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
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')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_exploreεClosure h ((Array.mem_push ..).mpr (.inl hmem))
State after:
no goals

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
hmem : StackEntry.explore i ∈ stack
h✝¹ : target ∉ next
offset✝ target'✝ : ℕ
heq✝ : nfa[↑target] = Node.save offset✝ target'✝
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_exploreεClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_εClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_εClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ 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')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_εClosure h hmem
State after:
no goals

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
hmem : StackEntry.explore i ∈ stack
h✝ : target ∉ next
heq✝ : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ i ∈ next'
Tactic:
exact mem_stack_mem_εClosure h hmem
State after:
no goals