internlm/Lean-Github huggingface dataset:
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
h :
  (let entry := stack.back' hemp;
    let stack' := stack.pop;
    let_fun this := ⋯;
    match entry with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
simp at h
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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
h :
  (match stack.back' hemp with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack.pop) =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
h :
  (match stack.back' hemp with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack.pop) =
    (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
have : stack.pop.size < stack.size := Array.lt_size_of_pop_of_not_empty _ (by assumption)
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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
h :
  (match stack.back' hemp with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack.pop) =
    (matched', next', saveSlots')
this : stack.pop.size < stack.size
⊢ LowerInvεClosure nfa next' #[]
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
h :
  (match stack.back' hemp with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack.pop) =
    (matched', next', saveSlots')
this : stack.pop.size < stack.size
⊢ LowerInvεClosure nfa next' #[]
Tactic:
split at h
Proof 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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target✝ : Fin nfa.nodes.size
heq✝ : stack.back' hemp = StackEntry.explore target✝
h : exploreεClosure nfa pos next currentSave matched saveSlots target✝ stack.pop = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa 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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' hemp = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Theorem: Regex.VM.lower_inv_εClosure
Proof 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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target✝ : Fin nfa.nodes.size
heq✝ : stack.back' hemp = StackEntry.explore target✝
h : exploreεClosure nfa pos next currentSave matched saveSlots target✝ stack.pop = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa 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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' hemp = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
next _ target heq =>
  have inv' : LowerInvExploreεClosure nfa next target stack.pop := by
    intro i j hi hj
    cases inv i j hi hj with
    | inl hnext => exact .inl hnext
    | inr hstack =>
      cases Array.mem_pop_or_eq_of_mem _ _ hemp hstack with
      | inl hstack => exact .inr (.inr hstack)
      | inr heq' =>
        rw [heq] at heq'
        have : j = target := by
          simp at heq'
          exact heq'
        exact .inr (.inl this)
  exact lower_inv_exploreεClosure h inv'
Proof 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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' hemp = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Theorem: Regex.VM.lower_inv_εClosure
Proof 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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' hemp = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
next _ _ heq =>
  have inv' : LowerInvεClosure nfa next stack.pop := by
    intro i j hi hj
    cases inv i j hi hj with
    | inl hnext => exact .inl hnext
    | inr hstack =>
      cases Array.mem_pop_or_eq_of_mem _ _ hemp hstack with
      | inl hstack => exact .inr hstack
      | inr heq' =>
        rw [heq] at heq'
        contradiction
  exact lower_inv_εClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
h :
  (match stack.back' hemp with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack.pop) =
    (matched', next', saveSlots')
⊢ ¬stack.isEmpty = true
Tactic:
assumption
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
have inv' : LowerInvExploreεClosure nfa next target stack.pop := by
  intro i j hi hj
  cases inv i j hi hj with
  | inl hnext => exact .inl hnext
  | inr hstack =>
    cases Array.mem_pop_or_eq_of_mem _ _ hemp hstack with
    | inl hstack => exact .inr (.inr hstack)
    | inr heq' =>
      rw [heq] at heq'
      have : j = target := by
        simp at heq'
        exact heq'
      exact .inr (.inl this)
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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
inv' : LowerInvExploreεClosure nfa next target stack.pop
⊢ LowerInvεClosure nfa next' #[]
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
inv' : LowerInvExploreεClosure nfa next target stack.pop
⊢ LowerInvεClosure nfa next' #[]
Tactic:
exact lower_inv_exploreεClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
⊢ LowerInvExploreεClosure nfa next target stack.pop
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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Tactic:
cases inv i j hi hj with
| inl hnext => exact .inl hnext
| inr hstack =>
  cases Array.mem_pop_or_eq_of_mem _ _ hemp hstack with
  | inl hstack => exact .inr (.inr hstack)
  | inr heq' =>
    rw [heq] at heq'
    have : j = target := by
      simp at heq'
      exact heq'
    exact .inr (.inl this)
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_ε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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
hnext : j ∈ next
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Tactic:
exact .inl hnext
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_ε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
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 : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
hstack : StackEntry.explore j ∈ stack
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Tactic:
cases Array.mem_pop_or_eq_of_mem _ _ hemp hstack with
| inl hstack => exact .inr (.inr hstack)
| inr heq' =>
  rw [heq] at heq'
  have : j = target := by
    simp at heq'
    exact heq'
  exact .inr (.inl this)
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_εClosure
Proof state before:
case inr.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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
hstack✝ : StackEntry.explore j ∈ stack
hstack : StackEntry.explore j ∈ stack.pop
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Tactic:
exact .inr (.inr hstack)
Proof state after:
no goals
Theorem: Regex.VM.lower_inv_εClosure
Proof state before:
case inr.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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
hstack : StackEntry.explore j ∈ stack
heq' : StackEntry.explore j = stack.back' hemp
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Tactic:
rw [heq] at heq'
Proof state after:
case inr.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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
hstack : StackEntry.explore j ∈ stack
heq' : StackEntry.explore j = StackEntry.explore target
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Theorem: Regex.VM.lower_inv_εClosure
Proof state before:
case inr.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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
hstack : StackEntry.explore j ∈ stack
heq' : StackEntry.explore j = StackEntry.explore target
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop
Tactic:
have : j = target := by
  simp at heq'
  exact heq'
Proof state after:
case inr.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
inv : LowerInvεClosure nfa next stack
hemp : ¬stack.isEmpty = true
this✝ : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target : Fin nfa.nodes.size
heq : stack.back' hemp = StackEntry.explore target
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack.pop = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next
hj : ↑j ∈ nfa.εStep ↑i
hstack : StackEntry.explore j ∈ stack
heq' : StackEntry.explore j = StackEntry.explore target
this : j = target
⊢ j ∈ next ∨ j = target ∨ StackEntry.explore j ∈ stack.pop