internlm/Lean-Github huggingface dataset:
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
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
target₁ target₂ : ℕ
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
hj : ↑j ∈ nfa.εStep ↑i
inv : LowerInvExploreεClosure nfa next i stack
h✝ : i ∉ next
hn : nfa[↑i] = Node.split target₁ target₂
h :
  exploreεClosure nfa pos (next.insert i) currentSave matched saveSlots ⟨target₁, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂, ⋯⟩)) =
    (matched', next', saveSlots')
hi : i ∈ next.insert i
⊢ j ∈ next.insert i ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
simp [εStep, Node.εStep, hn] at hj
Proof 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
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
target₁ target₂ : ℕ
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
inv : LowerInvExploreεClosure nfa next i stack
h✝ : i ∉ next
hn : nfa[↑i] = Node.split target₁ target₂
h :
  exploreεClosure nfa pos (next.insert i) currentSave matched saveSlots ⟨target₁, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂, ⋯⟩)) =
    (matched', next', saveSlots')
hi : i ∈ next.insert i
hj : ↑j = target₁ ∨ ↑j = target₂
⊢ j ∈ next.insert i ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
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
target₁ target₂ : ℕ
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
inv : LowerInvExploreεClosure nfa next i stack
h✝ : i ∉ next
hn : nfa[↑i] = Node.split target₁ target₂
h :
  exploreεClosure nfa pos (next.insert i) currentSave matched saveSlots ⟨target₁, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂, ⋯⟩)) =
    (matched', next', saveSlots')
hi : i ∈ next.insert i
hj : ↑j = target₁ ∨ ↑j = target₂
⊢ j ∈ next.insert i ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
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]))))
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof state before:
case inl.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
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
target₁ target₂ : ℕ
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
inv : LowerInvExploreεClosure nfa next i stack
h✝ : i ∉ next
hn : nfa[↑i] = Node.split target₁ target₂
h :
  exploreεClosure nfa pos (next.insert i) currentSave matched saveSlots ⟨target₁, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂, ⋯⟩)) =
    (matched', next', saveSlots')
hi : i ∈ next.insert i
hj : ↑j = target₁
⊢ j ∈ next.insert i ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
exact .inr (.inl (Fin.eq_of_val_eq hj))
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof state before:
case inl.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
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
target₁ target₂ : ℕ
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
inv : LowerInvExploreεClosure nfa next i stack
h✝ : i ∉ next
hn : nfa[↑i] = Node.split target₁ target₂
h :
  exploreεClosure nfa pos (next.insert i) currentSave matched saveSlots ⟨target₁, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂, ⋯⟩)) =
    (matched', next', saveSlots')
hi : i ∈ next.insert i
hj : ↑j = target₂
⊢ j ∈ next.insert i ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
exact .inr (.inr ((Array.mem_push ..).mpr (.inr (by simp [hj.symm]))))
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
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
target₁ target₂ : ℕ
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
inv : LowerInvExploreεClosure nfa next i stack
h✝ : i ∉ next
hn : nfa[↑i] = Node.split target₁ target₂
h :
  exploreεClosure nfa pos (next.insert i) currentSave matched saveSlots ⟨target₁, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂, ⋯⟩)) =
    (matched', next', saveSlots')
hi : i ∈ next.insert i
hj : ↑j = target₂
⊢ StackEntry.explore j = StackEntry.explore ⟨target₂, ⋯⟩
Tactic:
simp [hj.symm]
Proof state after:
no goals
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
target₁ target₂ : ℕ
hn : 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')
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
hnext : i ∈ next
⊢ j ∈ next.insert target ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
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)))
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
target₁ target₂ : ℕ
hn : 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')
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
hnext✝ : i ∈ next
hnext : j ∈ next
⊢ j ∈ next.insert target ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
exact .inl (SparseSet.mem_insert_of_mem hnext)
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
target₁ target₂ : ℕ
hn : 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')
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
hnext : i ∈ next
htarget : j = target
⊢ j ∈ next.insert target ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
exact .inl (htarget ▸ SparseSet.mem_insert)
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
target₁ target₂ : ℕ
hn : 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')
isLt : (Node.split target₁ target₂).inBounds nfa.nodes.size
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
hnext : i ∈ next
hstack : StackEntry.explore j ∈ stack
⊢ j ∈ next.insert target ∨ j = ⟨target₁, ⋯⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
Tactic:
exact .inr (.inr ((Array.mem_push ..).mpr (.inl hstack)))
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
h :
  (if h : offset✝ < currentSave.size then
      exploreεClosure nfa pos (next.insert target) (currentSave.set ⟨offset✝, ⋯⟩ (some pos)) matched saveSlots
        ⟨target', ⋯⟩ (stack.push (StackEntry.restore currentSave))
    else exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack) =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
have isLt := nfa.inBounds' target hn
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
offset✝ target' : ℕ
hn : 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')
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
⊢ LowerInvεClosure nfa next' #[]
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
offset✝ target' : ℕ
hn : 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')
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
⊢ LowerInvεClosure nfa next' #[]
Tactic:
split at h
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
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')
⊢ LowerInvεClosure nfa 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
inv : LowerInvExploreεClosure nfa next target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
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
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
h✝ : ¬offset✝ < currentSave.size
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
next =>
  have inv' : LowerInvExploreεClosure nfa (next.insert target) ⟨target', isLt⟩ stack := by
    intro i j hi hj
    cases SparseSet.eq_or_mem_of_mem_insert hi with
    | inl htarget =>
      subst htarget
      simp [εStep, Node.εStep, hn] at hj
      exact .inr (.inl (Fin.eq_of_val_eq hj))
    | inr hnext =>
      match inv i j hnext hj with
      | .inl hnext => exact .inl (SparseSet.mem_insert_of_mem hnext)
      | .inr (.inl htarget) => exact .inl (htarget ▸ SparseSet.mem_insert)
      | .inr (.inr hstack) => exact .inr (.inr hstack)
  exact lower_inv_exploreεClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
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')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
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)))
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
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')
inv' : LowerInvExploreεClosure nfa (next.insert target) ⟨target', isLt⟩ (stack.push (StackEntry.restore currentSave))
⊢ LowerInvεClosure nfa next' #[]
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
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')
inv' : LowerInvExploreεClosure nfa (next.insert target) ⟨target', isLt⟩ (stack.push (StackEntry.restore currentSave))
⊢ LowerInvεClosure nfa next' #[]
Tactic:
exact lower_inv_exploreεClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_exploreεClosure
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
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')
⊢ LowerInvExploreεClosure nfa (next.insert target) ⟨target', isLt⟩ (stack.push (StackEntry.restore currentSave))
Tactic:
intro i j hi hj
Proof 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
inv : LowerInvExploreεClosure nfa next target stack
h✝¹ : target ∉ next
offset✝ target' : ℕ
hn : nfa[↑target] = Node.save offset✝ target'
isLt : (Node.save offset✝ target').inBounds nfa.nodes.size
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 j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
⊢ j ∈ next.insert target ∨ j = ⟨target', isLt⟩ ∨ StackEntry.explore j ∈ stack.push (StackEntry.restore currentSave)