Theorem: Regex.VM.stepChar_spec.mem_next_iff (RegexCorrectness/VM/Auxiliary.lean)

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : stepChar nfa c pos next saveSlots target = (matched', next', saveSlots')
inv : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
unfold stepChar at h
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 :
  (match hn : nfa[target] with
    | Node.char c' target' =>
      if c = c' then
        let_fun isLt := ⋯;
        let currentSave := saveSlots.get ↑target ⋯;
        exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
      else (none, next, saveSlots)
    | Node.sparse cs target' =>
      if c ∈ cs then
        let_fun isLt := ⋯;
        let currentSave := saveSlots.get ↑target ⋯;
        exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
      else (none, next, saveSlots)
    | x => (none, next, saveSlots)) =
    (matched', next', saveSlots')
inv : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 :
  (match hn : nfa[target] with
    | Node.char c' target' =>
      if c = c' then
        let_fun isLt := ⋯;
        let currentSave := saveSlots.get ↑target ⋯;
        exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
      else (none, next, saveSlots)
    | Node.sparse cs target' =>
      if c ∈ cs then
        let_fun isLt := ⋯;
        let currentSave := saveSlots.get ↑target ⋯;
        exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
      else (none, next, saveSlots)
    | x => (none, next, saveSlots)) =
    (matched', next', saveSlots')
inv : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
split at h
State after:
case h_1
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c'✝ : Char
target'✝ : ℕ
heq✝ : nfa[target] = Node.char c'✝ target'✝
h :
  (if c = c'✝ then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target'✝, isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case h_2
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs✝ : Data.Classes
target'✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ target'✝
h :
  (if c ∈ cs✝ then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target'✝, isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case h_3
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
x✝¹ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
x✝ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case h_1
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c'✝ : Char
target'✝ : ℕ
heq✝ : nfa[target] = Node.char c'✝ target'✝
h :
  (if c = c'✝ then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target'✝, isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case h_2
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs✝ : Data.Classes
target'✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ target'✝
h :
  (if c ∈ cs✝ then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target'✝, isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case h_3
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
x✝¹ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
x✝ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
next c' target' hn =>
  simp at hn
  split at h
  next hc =>
    simp at h
    have mem_next_iff := exploreεClosure_spec.mem_next_iff h inv
    intro j
    apply Iff.intro
    . intro hj
      cases (mem_next_iff j).mp hj with
      | inl hj => exact .inl hj
      | inr hj =>
        refine .inr ⟨target', ?_, hj⟩
        simp [charStep, Node.charStep, hn, hc]
    . intro hj
      cases hj with
      | inl hj => exact (mem_next_iff j).mpr (.inl hj)
      | inr hj =>
        simp [charStep, Node.charStep, hn, hc] at hj
        exact (mem_next_iff j).mpr (.inr hj)
  next hc =>
    have : ∀ i, ¬i ∈ nfa.charStep target c := by
      intro i
      simp [charStep, Node.charStep, hn, hc]
    simp at h
    simp [h, this]
State after:
case h_2
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs✝ : Data.Classes
target'✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ target'✝
h :
  (if c ∈ cs✝ then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target'✝, isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case h_3
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
x✝¹ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
x✝ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case h_2
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs✝ : Data.Classes
target'✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ target'✝
h :
  (if c ∈ cs✝ then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target'✝, isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case h_3
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
x✝¹ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
x✝ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
next cs target' hn =>
  simp at hn
  split at h
  next hc =>
    simp at h
    have mem_next_iff := exploreεClosure_spec.mem_next_iff h inv
    intro j
    apply Iff.intro
    . intro hj
      cases (mem_next_iff j).mp hj with
      | inl hj => exact .inl hj
      | inr hj =>
        refine .inr ⟨target', ?_, hj⟩
        simp [charStep, Node.charStep, hn, hc]
    . intro hj
      cases hj with
      | inl hj => exact (mem_next_iff j).mpr (.inl hj)
      | inr hj =>
        simp [charStep, Node.charStep, hn, hc] at hj
        exact (mem_next_iff j).mpr (.inr hj)
  next hc =>
    have : ∀ i, ¬i ∈ nfa.charStep target c := by
      intro i
      simp [charStep, Node.charStep, hn, hc]
    simp at h
    simp [h, this]
State after:
case h_3
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
x✝¹ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
x✝ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case h_3
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
x✝¹ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
x✝ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
next hn₁ hn₂ =>
  have : ∀ i, ¬i ∈ nfa.charStep target c := by
    intro i
    simp at hn₁ hn₂
    simp [charStep, Node.charStep]
  simp at h
  simp [h, this]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[target] = Node.char c' target'
h :
  (if c = c' then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp at hn
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h :
  (if c = c' then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h :
  (if c = c' then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
split at h
State after:
case inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h✝ : c = c'
h :
  (let_fun isLt := ⋯;
    let currentSave := saveSlots.get ↑target ⋯;
    exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h✝ : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h✝ : c = c'
h :
  (let_fun isLt := ⋯;
    let currentSave := saveSlots.get ↑target ⋯;
    exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h✝ : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
next hc =>
  simp at h
  have mem_next_iff := exploreεClosure_spec.mem_next_iff h inv
  intro j
  apply Iff.intro
  . intro hj
    cases (mem_next_iff j).mp hj with
    | inl hj => exact .inl hj
    | inr hj =>
      refine .inr ⟨target', ?_, hj⟩
      simp [charStep, Node.charStep, hn, hc]
  . intro hj
    cases hj with
    | inl hj => exact (mem_next_iff j).mpr (.inl hj)
    | inr hj =>
      simp [charStep, Node.charStep, hn, hc] at hj
      exact (mem_next_iff j).mpr (.inr hj)
State after:
case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h✝ : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
h✝ : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
next hc =>
  have : ∀ i, ¬i ∈ nfa.charStep target c := by
    intro i
    simp [charStep, Node.charStep, hn, hc]
  simp at h
  simp [h, this]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  (let_fun isLt := ⋯;
    let currentSave := saveSlots.get ↑target ⋯;
    exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp at h
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
have mem_next_iff := exploreεClosure_spec.mem_next_iff h inv
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
intro j
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
apply Iff.intro
State after:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' → j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'

State before:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' → j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'
Tactic:
. intro hj
  cases (mem_next_iff j).mp hj with
  | inl hj => exact .inl hj
  | inr hj =>
    refine .inr ⟨target', ?_, hj⟩
    simp [charStep, Node.charStep, hn, hc]
State after:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'

State before:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'
Tactic:
. intro hj
  cases hj with
  | inl hj => exact (mem_next_iff j).mpr (.inl hj)
  | inr hj =>
    simp [charStep, Node.charStep, hn, hc] at hj
    exact (mem_next_iff j).mpr (.inr hj)
State after:
no goals

State before:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' → j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
intro hj
State after:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next'
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next'
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
cases (mem_next_iff j).mp hj with
| inl hj => exact .inl hj
| inr hj =>
  refine .inr ⟨target', ?_, hj⟩
  simp [charStep, Node.charStep, hn, hc]
State after:
no goals

State before:
case mp.inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : j ∈ next
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
exact .inl hj
State after:
no goals

State before:
case mp.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : ↑j ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
refine .inr ⟨target', ?_, hj⟩
State after:
case mp.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : ↑j ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ target' ∈ nfa.charStep (↑target) c

State before:
case mp.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : ↑j ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ target' ∈ nfa.charStep (↑target) c
Tactic:
simp [charStep, Node.charStep, hn, hc]
State after:
no goals

State before:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'
Tactic:
intro hj
State after:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
⊢ j ∈ next'

State before:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
⊢ j ∈ next'
Tactic:
cases hj with
| inl hj => exact (mem_next_iff j).mpr (.inl hj)
| inr hj =>
  simp [charStep, Node.charStep, hn, hc] at hj
  exact (mem_next_iff j).mpr (.inr hj)
State after:
no goals

State before:
case mpr.inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next
⊢ j ∈ next'
Tactic:
exact (mem_next_iff j).mpr (.inl hj)
State after:
no goals

State before:
case mpr.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
⊢ j ∈ next'
Tactic:
simp [charStep, Node.charStep, hn, hc] at hj
State after:
case mpr.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : ↑j ∈ nfa.εClosure target'
⊢ j ∈ next'

State before:
case mpr.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : c = c'
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : ↑j ∈ nfa.εClosure target'
⊢ j ∈ next'
Tactic:
exact (mem_next_iff j).mpr (.inr hj)
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
have : ∀ i, ¬i ∈ nfa.charStep target c := by
  intro i
  simp [charStep, Node.charStep, hn, hc]
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp at h
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
h : none = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
h : none = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp [h, this]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
Tactic:
intro i
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
⊢ i ∉ nfa.charStep (↑target) c

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
c' : Char
target' : ℕ
hn : nfa[↑target] = Node.char c' target'
hc : ¬c = c'
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
⊢ i ∉ nfa.charStep (↑target) c
Tactic:
simp [charStep, Node.charStep, hn, hc]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[target] = Node.sparse cs target'
h :
  (if c ∈ cs then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp at hn
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h :
  (if c ∈ cs then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h :
  (if c ∈ cs then
      let_fun isLt := ⋯;
      let currentSave := saveSlots.get ↑target ⋯;
      exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]
    else (none, next, saveSlots)) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
split at h
State after:
case inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h✝ : c ∈ cs
h :
  (let_fun isLt := ⋯;
    let currentSave := saveSlots.get ↑target ⋯;
    exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h✝ : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h✝ : c ∈ cs
h :
  (let_fun isLt := ⋯;
    let currentSave := saveSlots.get ↑target ⋯;
    exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h✝ : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
next hc =>
  simp at h
  have mem_next_iff := exploreεClosure_spec.mem_next_iff h inv
  intro j
  apply Iff.intro
  . intro hj
    cases (mem_next_iff j).mp hj with
    | inl hj => exact .inl hj
    | inr hj =>
      refine .inr ⟨target', ?_, hj⟩
      simp [charStep, Node.charStep, hn, hc]
  . intro hj
    cases hj with
    | inl hj => exact (mem_next_iff j).mpr (.inl hj)
    | inr hj =>
      simp [charStep, Node.charStep, hn, hc] at hj
      exact (mem_next_iff j).mpr (.inr hj)
State after:
case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h✝ : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
h✝ : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
next hc =>
  have : ∀ i, ¬i ∈ nfa.charStep target c := by
    intro i
    simp [charStep, Node.charStep, hn, hc]
  simp at h
  simp [h, this]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  (let_fun isLt := ⋯;
    let currentSave := saveSlots.get ↑target ⋯;
    exploreεClosure nfa pos next currentSave none saveSlots ⟨target', isLt⟩ #[]) =
    (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp at h
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
have mem_next_iff := exploreεClosure_spec.mem_next_iff h inv
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
intro j
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
apply Iff.intro
State after:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' → j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'

State before:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' → j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'
Tactic:
. intro hj
  cases (mem_next_iff j).mp hj with
  | inl hj => exact .inl hj
  | inr hj =>
    refine .inr ⟨target', ?_, hj⟩
    simp [charStep, Node.charStep, hn, hc]
State after:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'

State before:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'
Tactic:
. intro hj
  cases hj with
  | inl hj => exact (mem_next_iff j).mpr (.inl hj)
  | inr hj =>
    simp [charStep, Node.charStep, hn, hc] at hj
    exact (mem_next_iff j).mpr (.inr hj)
State after:
no goals

State before:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ j ∈ next' → j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
intro hj
State after:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next'
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
case mp
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next'
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
cases (mem_next_iff j).mp hj with
| inl hj => exact .inl hj
| inr hj =>
  refine .inr ⟨target', ?_, hj⟩
  simp [charStep, Node.charStep, hn, hc]
State after:
no goals

State before:
case mp.inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : j ∈ next
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
exact .inl hj
State after:
no goals

State before:
case mp.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : ↑j ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
refine .inr ⟨target', ?_, hj⟩
State after:
case mp.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : ↑j ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ target' ∈ nfa.charStep (↑target) c

State before:
case mp.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj✝ : j ∈ next'
hj : ↑j ∈ nfa.εClosure ↑⟨target', ⋯⟩
⊢ target' ∈ nfa.charStep (↑target) c
Tactic:
simp [charStep, Node.charStep, hn, hc]
State after:
no goals

State before:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
⊢ (j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i) → j ∈ next'
Tactic:
intro hj
State after:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
⊢ j ∈ next'

State before:
case mpr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
⊢ j ∈ next'
Tactic:
cases hj with
| inl hj => exact (mem_next_iff j).mpr (.inl hj)
| inr hj =>
  simp [charStep, Node.charStep, hn, hc] at hj
  exact (mem_next_iff j).mpr (.inr hj)
State after:
no goals

State before:
case mpr.inl
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : j ∈ next
⊢ j ∈ next'
Tactic:
exact (mem_next_iff j).mpr (.inl hj)
State after:
no goals

State before:
case mpr.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
⊢ j ∈ next'
Tactic:
simp [charStep, Node.charStep, hn, hc] at hj
State after:
case mpr.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : ↑j ∈ nfa.εClosure target'
⊢ j ∈ next'

State before:
case mpr.inr
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∈ cs
h :
  exploreεClosure nfa pos next (saveSlots.get ↑target ⋯) none saveSlots ⟨target', ⋯⟩ #[] = (matched', next', saveSlots')
mem_next_iff : ∀ (i : Fin nfa.nodes.size), i ∈ next' ↔ i ∈ next ∨ ↑i ∈ nfa.εClosure ↑⟨target', ⋯⟩
j : Fin nfa.nodes.size
hj : ↑j ∈ nfa.εClosure target'
⊢ j ∈ next'
Tactic:
exact (mem_next_iff j).mpr (.inr hj)
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
have : ∀ i, ¬i ∈ nfa.charStep target c := by
  intro i
  simp [charStep, Node.charStep, hn, hc]
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp at h
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
h : none = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
h : none = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp [h, this]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
Tactic:
intro i
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
⊢ i ∉ nfa.charStep (↑target) c

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
cs : Data.Classes
target' : ℕ
hn : nfa[↑target] = Node.sparse cs target'
hc : c ∉ cs
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
⊢ i ∉ nfa.charStep (↑target) c
Tactic:
simp [charStep, Node.charStep, hn, hc]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
have : ∀ i, ¬i ∈ nfa.charStep target c := by
  intro i
  simp at hn₁ hn₂
  simp [charStep, Node.charStep]
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp at h
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
h : none = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
this : ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
h : none = matched' ∧ next = next' ∧ saveSlots = saveSlots'
⊢ ∀ (j : Fin nfa.nodes.size), j ∈ next' ↔ j ∈ next ∨ ∃ i ∈ nfa.charStep (↑target) c, ↑j ∈ nfa.εClosure i
Tactic:
simp [h, this]
State after:
no goals

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
⊢ ∀ (i : ℕ), i ∉ nfa.charStep (↑target) c
Tactic:
intro i
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
⊢ i ∉ nfa.charStep (↑target) c

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
hn₁ : ∀ (c' : Char) (target' : ℕ), nfa[target] = Node.char c' target' → False
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), nfa[target] = Node.sparse cs target' → False
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
⊢ i ∉ nfa.charStep (↑target) c
Tactic:
simp at hn₁ hn₂
State after:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
hn₁ : ∀ (c' : Char) (target' : ℕ), ¬nfa[↑target] = Node.char c' target'
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), ¬nfa[↑target] = Node.sparse cs target'
⊢ i ∉ nfa.charStep (↑target) c

State before:
nfa : NFA
c : Char
pos : String.Pos
next : SparseSet nfa.nodes.size
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin 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 : ∀ (i j : Fin nfa.nodes.size), i ∈ next → ↑j ∈ nfa.εStep ↑i → j ∈ next
h : (none, next, saveSlots) = (matched', next', saveSlots')
i : ℕ
hn₁ : ∀ (c' : Char) (target' : ℕ), ¬nfa[↑target] = Node.char c' target'
hn₂ : ∀ (cs : Data.Classes) (target' : ℕ), ¬nfa[↑target] = Node.sparse cs target'
⊢ i ∉ nfa.charStep (↑target) c
Tactic:
simp [charStep, Node.charStep]
State after:
no goals