internlm/Lean-Github huggingface dataset:
Theorem: Regex.VM.upper_bound_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
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
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
h :
  (let next' := next.insert target;
    match hn : nfa[target] with
    | Node.epsilon target' =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.split target₁ target₂ =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target₁, ⋯⟩
        (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
    | Node.save offset target' =>
      let_fun isLt := ⋯;
      if h : offset < currentSave.size then
        let nextSave := currentSave.set ⟨offset, h⟩ (some pos);
        let stack' := stack.push (StackEntry.restore currentSave);
        exploreεClosure nfa pos next' nextSave matched saveSlots ⟨target', isLt⟩ stack'
      else exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.done =>
      let matched' := HOrElse.hOrElse matched fun x => some currentSave;
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched' saveSlots' stack
    | Node.char c next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.sparse cs next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.fail => εClosure nfa pos next' currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
this : UpperBoundεClosure nfa i (next.insert target) next'
j : Fin nfa.nodes.size
hj : j ∈ next'
hnext✝ : j ∈ next.insert target
hnext : j ∈ next
⊢ j ∈ next ∨ ↑j ∈ nfa.εClosure ↑i
Tactic:
exact .inl hnext
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
h :
  (let next' := next.insert target;
    match hn : nfa[target] with
    | Node.epsilon target' =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.split target₁ target₂ =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target₁, ⋯⟩
        (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
    | Node.save offset target' =>
      let_fun isLt := ⋯;
      if h : offset < currentSave.size then
        let nextSave := currentSave.set ⟨offset, h⟩ (some pos);
        let stack' := stack.push (StackEntry.restore currentSave);
        exploreεClosure nfa pos next' nextSave matched saveSlots ⟨target', isLt⟩ stack'
      else exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.done =>
      let matched' := HOrElse.hOrElse matched fun x => some currentSave;
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched' saveSlots' stack
    | Node.char c next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.sparse cs next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.fail => εClosure nfa pos next' currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
this : UpperBoundεClosure nfa i (next.insert target) next'
j : Fin nfa.nodes.size
hj : j ∈ next'
hcls : ↑j ∈ nfa.εClosure ↑i
⊢ j ∈ next ∨ ↑j ∈ nfa.εClosure ↑i
Tactic:
exact .inr hcls
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
target' : ℕ
hn : nfa[↑target] = Node.epsilon target'
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
⊢ UpperBoundεClosure nfa i (next.insert target) 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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
target' : ℕ
hn : nfa[↑target] = Node.epsilon target'
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
isLt : (Node.epsilon target').inBounds nfa.nodes.size
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
target' : ℕ
hn : nfa[↑target] = Node.epsilon target'
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
isLt : (Node.epsilon target').inBounds nfa.nodes.size
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
have inv' : UpperInvExploreεClosure nfa i ⟨target', isLt⟩ stack :=
  ⟨εClosure_snoc inv.1 (by simp [εStep, Node.εStep, hn]), inv.2⟩
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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
target' : ℕ
hn : nfa[↑target] = Node.epsilon target'
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
isLt : (Node.epsilon target').inBounds nfa.nodes.size
inv' : UpperInvExploreεClosure nfa i ⟨target', isLt⟩ stack
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
target' : ℕ
hn : nfa[↑target] = Node.epsilon target'
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
isLt : (Node.epsilon target').inBounds nfa.nodes.size
inv' : UpperInvExploreεClosure nfa i ⟨target', isLt⟩ stack
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
exact upper_bound_exploreεClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i target stack
h✝ : target ∉ next
target' : ℕ
hn : nfa[↑target] = Node.epsilon target'
h :
  exploreεClosure nfa pos (next.insert target) currentSave matched saveSlots ⟨target', ⋯⟩ stack =
    (matched', next', saveSlots')
isLt : (Node.epsilon target').inBounds nfa.nodes.size
⊢ ↑⟨target', isLt⟩ ∈ nfa.εStep ↑target
Tactic:
simp [εStep, Node.εStep, hn]
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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')
⊢ UpperBoundεClosure nfa i (next.insert target) 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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
have inv' : UpperInvExploreεClosure nfa i ⟨target₁, isLt.1⟩ (stack.push (.explore ⟨target₂, isLt.2⟩)) := by
  refine ⟨εClosure_snoc inv.1 (by simp [εStep, Node.εStep, hn]), ?_⟩
  intro j hj
  cases (Array.mem_push ..).mp hj with
  | inl hj => exact inv.2 j hj
  | inr hj =>
    simp at hj
    exact εClosure_snoc inv.1 (by simp [εStep, Node.εStep, hn, 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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
inv' : UpperInvExploreεClosure nfa i ⟨target₁, ⋯⟩ (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
inv' : UpperInvExploreεClosure nfa i ⟨target₁, ⋯⟩ (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
⊢ UpperBoundεClosure nfa i (next.insert target) next'
Tactic:
exact upper_bound_exploreεClosure h inv'
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
⊢ UpperInvExploreεClosure nfa i ⟨target₁, ⋯⟩ (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
Tactic:
refine ⟨εClosure_snoc inv.1 (by simp [εStep, Node.εStep, 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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
⊢ ∀ (j : Fin nfa.nodes.size), StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩) → ↑j ∈ nfa.εClosure ↑i
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
⊢ ∀ (j : Fin nfa.nodes.size), StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩) → ↑j ∈ nfa.εClosure ↑i
Tactic:
intro j 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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
j : Fin nfa.nodes.size
hj : StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
⊢ ↑j ∈ nfa.εClosure ↑i
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
j : Fin nfa.nodes.size
hj : StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
⊢ ↑j ∈ nfa.εClosure ↑i
Tactic:
cases (Array.mem_push ..).mp hj with
| inl hj => exact inv.2 j hj
| inr hj =>
  simp at hj
  exact εClosure_snoc inv.1 (by simp [εStep, Node.εStep, hn, hj])
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_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
i : Fin nfa.nodes.size
inv : UpperInvExploreεClosure nfa i 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
⊢ ↑⟨target₁, ⋯⟩ ∈ nfa.εStep ↑target
Tactic:
simp [εStep, Node.εStep, hn]
Proof state after:
no goals
Theorem: Regex.VM.upper_bound_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
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
inv : UpperInvExploreεClosure nfa i 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
j : Fin nfa.nodes.size
hj✝ : StackEntry.explore j ∈ stack.push (StackEntry.explore ⟨target₂, ⋯⟩)
hj : StackEntry.explore j ∈ stack
⊢ ↑j ∈ nfa.εClosure ↑i
Tactic:
exact inv.2 j hj
Proof state after:
no goals