internlm/Lean-Github huggingface dataset:
Theorem: Regex.VM.εClosure_subset
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
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
⊢ next ⊆ 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
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
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    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')
⊢ next ⊆ next'
Tactic:
next =>
  have : next = next' := by
    simp at h
    simp only [h]
  exact this ▸ SparseSet.subset_self
Proof 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
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
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    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')
⊢ next ⊆ next'
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    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')
⊢ next ⊆ next'
Tactic:
next =>
  simp at h
  have : stack.pop.size < stack.size := Array.lt_size_of_pop_of_not_empty _ (by assumption)
  split at h
  next => exact exploreεClosure_subset h
  next => exact εClosure_subset h
Proof state after:
no goals
Theorem: Regex.VM.εClosure_subset
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
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
have : next = next' := by
  simp at h
  simp only [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
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
this : next = next'
⊢ next ⊆ next'
Theorem: Regex.VM.εClosure_subset
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
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
this : next = next'
⊢ next ⊆ next'
Tactic:
exact this ▸ SparseSet.subset_self
Proof state after:
no goals
Theorem: Regex.VM.εClosure_subset
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
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
⊢ next = 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
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ next = next'
Theorem: Regex.VM.εClosure_subset
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
h✝ : stack.isEmpty = true
h : matched = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ next = next'
Tactic:
simp only [h]
Proof state after:
no goals
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    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')
⊢ next ⊆ 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
h✝ : ¬stack.isEmpty = true
h :
  (match stack.back' h✝ 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')
⊢ next ⊆ next'
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
h :
  (match stack.back' h✝ 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')
⊢ next ⊆ 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
h✝ : ¬stack.isEmpty = true
h :
  (match stack.back' h✝ 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
⊢ next ⊆ next'
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
h :
  (match stack.back' h✝ 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
⊢ next ⊆ 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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target✝ : Fin nfa.nodes.size
heq✝ : stack.back' h✝ = StackEntry.explore target✝
h : exploreεClosure nfa pos next currentSave matched saveSlots target✝ stack.pop = (matched', next', saveSlots')
⊢ next ⊆ 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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' h✝ = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ next ⊆ next'
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target✝ : Fin nfa.nodes.size
heq✝ : stack.back' h✝ = StackEntry.explore target✝
h : exploreεClosure nfa pos next currentSave matched saveSlots target✝ stack.pop = (matched', next', saveSlots')
⊢ next ⊆ 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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' h✝ = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
next => exact exploreεClosure_subset h
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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' h✝ = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ next ⊆ next'
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' h✝ = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
next => exact εClosure_subset h
Proof state after:
no goals
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
h :
  (match stack.back' h✝ 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.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
target✝ : Fin nfa.nodes.size
heq✝ : stack.back' h✝ = StackEntry.explore target✝
h : exploreεClosure nfa pos next currentSave matched saveSlots target✝ stack.pop = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact exploreεClosure_subset h
Proof state after:
no goals
Theorem: Regex.VM.εClosure_subset
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
h✝ : ¬stack.isEmpty = true
this : stack.pop.size < stack.size
entry✝ : StackEntry nfa.nodes.size
save✝ : Array (Option String.Pos)
heq✝ : stack.back' h✝ = StackEntry.restore save✝
h : εClosure nfa pos next save✝ matched saveSlots stack.pop = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact εClosure_subset h
Proof state after:
no goals
Theorem: Regex.VM.target_mem_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
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
⊢ target ∈ next'
Tactic:
unfold exploreεClosure 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
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
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')
⊢ target ∈ next'
Theorem: Regex.VM.target_mem_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
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')
⊢ target ∈ next'
Tactic:
next =>
  generalize hins : next.insert target = inserted at h
  have hmem : target ∈ inserted := hins ▸ SparseSet.mem_insert
  split at h <;> simp at h
  next => exact exploreεClosure_subset h target hmem
  next => exact exploreεClosure_subset h target hmem
  next => split at h <;> exact exploreεClosure_subset h target hmem
  next => exact εClosure_subset h target hmem
  next => exact εClosure_subset h target hmem
  next => exact εClosure_subset h target hmem
  next => exact εClosure_subset h target hmem
Proof state after:
no goals
Theorem: Regex.VM.target_mem_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
hmem : target ∈ next
h : εClosure nfa pos next currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ target ∈ next'
Tactic:
exact εClosure_subset h target hmem
Proof state after:
no goals