Theorem: Regex.VM.lower_inv_exploreεClosure (RegexCorrectness/VM/Auxiliary.lean)

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa next' #[]
Tactic:
have inv' : LowerInvεClosure nfa (next.insert target) 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
  | 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 hstack
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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
inv' : LowerInvεClosure nfa (next.insert target) stack
⊢ LowerInvεClosure nfa next' #[]

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
inv' : LowerInvεClosure nfa (next.insert target) stack
⊢ LowerInvεClosure nfa next' #[]
Tactic:
exact lower_inv_εClosure h inv'
State after:
no goals

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ LowerInvεClosure nfa (next.insert target) stack
Tactic:
intro i j hi hj
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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
⊢ j ∈ next.insert target ∨ StackEntry.explore j ∈ stack

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
⊢ j ∈ next.insert target ∨ StackEntry.explore j ∈ stack
Tactic:
cases SparseSet.eq_or_mem_of_mem_insert hi with
| inl htarget =>
  subst htarget
  simp [εStep, Node.εStep, hn] at 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 hstack
State after:
no goals

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
inv : LowerInvExploreεClosure nfa next target stack
h✝ : target ∉ next
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
htarget : i = target
⊢ j ∈ next.insert target ∨ StackEntry.explore j ∈ stack
Tactic:
subst htarget
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
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.fail
h : εClosure nfa pos (next.insert i) currentSave matched saveSlots stack = (matched', next', saveSlots')
hi : i ∈ next.insert i
⊢ j ∈ next.insert i ∨ StackEntry.explore j ∈ stack

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
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.fail
h : εClosure nfa pos (next.insert i) currentSave matched saveSlots stack = (matched', next', saveSlots')
hi : i ∈ next.insert i
⊢ j ∈ next.insert i ∨ StackEntry.explore j ∈ stack
Tactic:
simp [εStep, Node.εStep, hn] at hj
State after:
no goals

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
i j : Fin nfa.nodes.size
hi : i ∈ next.insert target
hj : ↑j ∈ nfa.εStep ↑i
hnext : i ∈ next
⊢ j ∈ next.insert target ∨ StackEntry.explore j ∈ stack
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 hstack
State after:
no goals

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
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 ∨ StackEntry.explore j ∈ stack
Tactic:
exact .inl (SparseSet.mem_insert_of_mem hnext)
State after:
no goals

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
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 ∨ StackEntry.explore j ∈ stack
Tactic:
exact .inl (htarget ▸ SparseSet.mem_insert)
State after:
no goals

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
hn : nfa[↑target] = Node.fail
h : εClosure nfa pos (next.insert target) currentSave matched saveSlots stack = (matched', next', saveSlots')
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 ∨ StackEntry.explore j ∈ stack
Tactic:
exact .inr hstack
State after:
no goals