Theorem: Regex.VM.exploreε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
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
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
target'✝ : ℕ
heq✝ : nfa[target] = Node.epsilon target'✝
h : exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack = (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
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
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
target₁✝ target₂✝ : ℕ
heq✝ : nfa[target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_3
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
offset✝ target'✝ : ℕ
heq✝ : nfa[target] = Node.save offset✝ target'✝
h :
  (if h : offset✝ < currentSave.size then
      exploreεClosure nfa pos inserted (currentSave.set ⟨offset✝, ⋯⟩ (some pos)) matched saveSlots ⟨target'✝, ⋯⟩
        (stack.push (StackEntry.restore currentSave))
    else exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack) =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_4
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.done
h :
  εClosure nfa pos inserted currentSave (HOrElse.hOrElse matched fun x => some currentSave)
      (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_5
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
c✝ : Char
next✝ : ℕ
heq✝ : nfa[target] = Node.char c✝ next✝
h :
  εClosure nfa pos inserted currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_6
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
cs✝ : Data.Classes
next✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ next✝
h :
  εClosure nfa pos inserted currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_7
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.fail
h : εClosure nfa pos inserted currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
next => exact SparseSet.subset_trans sub (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
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
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
target₁✝ target₂✝ : ℕ
heq✝ : nfa[target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_3
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
offset✝ target'✝ : ℕ
heq✝ : nfa[target] = Node.save offset✝ target'✝
h :
  (if h : offset✝ < currentSave.size then
      exploreεClosure nfa pos inserted (currentSave.set ⟨offset✝, ⋯⟩ (some pos)) matched saveSlots ⟨target'✝, ⋯⟩
        (stack.push (StackEntry.restore currentSave))
    else exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack) =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_4
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.done
h :
  εClosure nfa pos inserted currentSave (HOrElse.hOrElse matched fun x => some currentSave)
      (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_5
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
c✝ : Char
next✝ : ℕ
heq✝ : nfa[target] = Node.char c✝ next✝
h :
  εClosure nfa pos inserted currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_6
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
cs✝ : Data.Classes
next✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ next✝
h :
  εClosure nfa pos inserted currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_7
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.fail
h : εClosure nfa pos inserted currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'