internlm/Lean-Github huggingface dataset:
Theorem: Regex.Data.SparseSet.eq_or_mem_of_mem_insert
Proof state before:
n : Nat
s : SparseSet n
i j : Fin n
heq : ¬i = j
hmem : ¬j ∈ s
ne : ↑j ≠ ↑i
heq' : ¬s.count = ↑s.sparse[↑i]
h : ↑s.sparse[↑i] < s.count + 1 ∧ s.dense[↑s.sparse[↑i]] = i
⊢ ↑s.sparse[↑i] < s.count
Tactic:
have : s.sparse[i.val] ≤ s.count := Nat.le_of_lt_succ h.left
Proof state after:
n : Nat
s : SparseSet n
i j : Fin n
heq : ¬i = j
hmem : ¬j ∈ s
ne : ↑j ≠ ↑i
heq' : ¬s.count = ↑s.sparse[↑i]
h : ↑s.sparse[↑i] < s.count + 1 ∧ s.dense[↑s.sparse[↑i]] = i
this : ↑s.sparse[↑i] ≤ s.count
⊢ ↑s.sparse[↑i] < s.count
Theorem: Regex.Data.SparseSet.eq_or_mem_of_mem_insert
Proof state before:
n : Nat
s : SparseSet n
i j : Fin n
heq : ¬i = j
hmem : ¬j ∈ s
ne : ↑j ≠ ↑i
heq' : ¬s.count = ↑s.sparse[↑i]
h : ↑s.sparse[↑i] < s.count + 1 ∧ s.dense[↑s.sparse[↑i]] = i
this : ↑s.sparse[↑i] ≤ s.count
⊢ ↑s.sparse[↑i] < s.count
Tactic:
exact Nat.lt_of_le_of_ne this (Ne.symm heq')
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.subset_self
Proof state before:
n : Nat
s : SparseSet n
⊢ s ⊆ s
Tactic:
simp [HasSubset.Subset, Subset]
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.subset_insert
Proof state before:
n : Nat
i : Fin n
s : SparseSet n
⊢ s ⊆ s.insert i
Tactic:
intro j hj
Proof state after:
n : Nat
i : Fin n
s : SparseSet n
j : Fin n
hj : j ∈ s
⊢ j ∈ s.insert i
Theorem: Regex.Data.SparseSet.subset_insert
Proof state before:
n : Nat
i : Fin n
s : SparseSet n
j : Fin n
hj : j ∈ s
⊢ j ∈ s.insert i
Tactic:
exact mem_insert_of_mem hj
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.subset_trans
Proof state before:
n : Nat
s₁ s₂ s₃ : SparseSet n
h₁ : s₁ ⊆ s₂
h₂ : s₂ ⊆ s₃
⊢ s₁ ⊆ s₃
Tactic:
intro i hi
Proof state after:
n : Nat
s₁ s₂ s₃ : SparseSet n
h₁ : s₁ ⊆ s₂
h₂ : s₂ ⊆ s₃
i : Fin n
hi : i ∈ s₁
⊢ i ∈ s₃
Theorem: Regex.Data.SparseSet.subset_trans
Proof state before:
n : Nat
s₁ s₂ s₃ : SparseSet n
h₁ : s₁ ⊆ s₂
h₂ : s₂ ⊆ s₃
i : Fin n
hi : i ∈ s₁
⊢ i ∈ s₃
Tactic:
exact h₂ _ (h₁ _ hi)
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.mem_get
Proof state before:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
⊢ s[i] ∈ s
Tactic:
have isLt : i < n := Nat.lt_of_lt_of_le h s.le_count
Proof state after:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
⊢ s[i] ∈ s
Theorem: Regex.Data.SparseSet.mem_get
Proof state before:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
⊢ s[i] ∈ s
Tactic:
have : s[i] = s.dense[i] := rfl
Proof state after:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this : s[i] = s.dense[i]
⊢ s[i] ∈ s
Theorem: Regex.Data.SparseSet.mem_get
Proof state before:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this : s[i] = s.dense[i]
⊢ s[i] ∈ s
Tactic:
simp [mem, this]
Proof state after:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this : s[i] = s.dense[i]
⊢ ↑s.sparse[↑s.dense[i]] < s.count ∧ s.dense[↑s.sparse[↑s.dense[i]]] = s.dense[i]
Theorem: Regex.Data.SparseSet.mem_get
Proof state before:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this : s[i] = s.dense[i]
⊢ ↑s.sparse[↑s.dense[i]] < s.count ∧ s.dense[↑s.sparse[↑s.dense[i]]] = s.dense[i]
Tactic:
have := s.sparse_dense ⟨i, isLt⟩ h
Proof state after:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this✝ : s[i] = s.dense[i]
this : s.sparse[↑s.dense[↑⟨i, isLt⟩]] = ⟨i, isLt⟩
⊢ ↑s.sparse[↑s.dense[i]] < s.count ∧ s.dense[↑s.sparse[↑s.dense[i]]] = s.dense[i]
Theorem: Regex.Data.SparseSet.mem_get
Proof state before:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this✝ : s[i] = s.dense[i]
this : s.sparse[↑s.dense[↑⟨i, isLt⟩]] = ⟨i, isLt⟩
⊢ ↑s.sparse[↑s.dense[i]] < s.count ∧ s.dense[↑s.sparse[↑s.dense[i]]] = s.dense[i]
Tactic:
simp at this
Proof state after:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this✝ : s[i] = s.dense[i]
this : s.sparse[↑s.dense[i]] = ⟨i, isLt⟩
⊢ ↑s.sparse[↑s.dense[i]] < s.count ∧ s.dense[↑s.sparse[↑s.dense[i]]] = s.dense[i]
Theorem: Regex.Data.SparseSet.mem_get
Proof state before:
n : Nat
s : SparseSet n
i : Nat
h : i < s.count
isLt : i < n
this✝ : s[i] = s.dense[i]
this : s.sparse[↑s.dense[i]] = ⟨i, isLt⟩
⊢ ↑s.sparse[↑s.dense[i]] < s.count ∧ s.dense[↑s.sparse[↑s.dense[i]]] = s.dense[i]
Tactic:
simp [this, h]
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : exploreεClosure nfa pos next currentSave matched saveSlots target stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
unfold exploreεClosure at h
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h :
  (if target ∈ next then εClosure nfa pos next currentSave matched saveSlots stack
    else
      let next' := next.insert target;
      match hn : nfa[target] with
      | Node.epsilon target' =>
        let_fun isLt := ⋯;
        exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
      | Node.split target₁ target₂ =>
        let_fun isLt := ⋯;
        exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target₁, ⋯⟩
          (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
      | Node.save offset target' =>
        let_fun isLt := ⋯;
        if h : offset < currentSave.size then
          let nextSave := currentSave.set ⟨offset, h⟩ (some pos);
          let stack' := stack.push (StackEntry.restore currentSave);
          exploreεClosure nfa pos next' nextSave matched saveSlots ⟨target', isLt⟩ stack'
        else exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
      | Node.done =>
        let matched' := HOrElse.hOrElse matched fun x => some currentSave;
        let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
        εClosure nfa pos next' currentSave matched' saveSlots' stack
      | Node.char c next =>
        let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
        εClosure nfa pos next' currentSave matched saveSlots' stack
      | Node.sparse cs next =>
        let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
        εClosure nfa pos next' currentSave matched saveSlots' stack
      | Node.fail => εClosure nfa pos next' currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
h :
  (let next' := next.insert target;
    match hn : nfa[target] with
    | Node.epsilon target' =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.split target₁ target₂ =>
      let_fun isLt := ⋯;
      exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target₁, ⋯⟩
        (stack.push (StackEntry.explore ⟨target₂, ⋯⟩))
    | Node.save offset target' =>
      let_fun isLt := ⋯;
      if h : offset < currentSave.size then
        let nextSave := currentSave.set ⟨offset, h⟩ (some pos);
        let stack' := stack.push (StackEntry.restore currentSave);
        exploreεClosure nfa pos next' nextSave matched saveSlots ⟨target', isLt⟩ stack'
      else exploreεClosure nfa pos next' currentSave matched saveSlots ⟨target', isLt⟩ stack
    | Node.done =>
      let matched' := HOrElse.hOrElse matched fun x => some currentSave;
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched' saveSlots' stack
    | Node.char c next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.sparse cs next =>
      let saveSlots' := saveSlots.set ↑target ⋯ currentSave;
      εClosure nfa pos next' currentSave matched saveSlots' stack
    | Node.fail => εClosure nfa pos next' currentSave matched saveSlots stack) =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
next =>
  generalize hins : next.insert target = inserted at h
  have sub : next ⊆ inserted := hins ▸ SparseSet.subset_insert
  split at h <;> simp at h
  next => exact SparseSet.subset_trans sub (exploreεClosure_subset h)
  next => exact SparseSet.subset_trans sub (exploreεClosure_subset h)
  next => split at h <;> exact SparseSet.subset_trans sub (exploreεClosure_subset h)
  next => exact SparseSet.subset_trans sub (εClosure_subset h)
  next => exact SparseSet.subset_trans sub (εClosure_subset h)
  next => exact SparseSet.subset_trans sub (εClosure_subset h)
  next => exact SparseSet.subset_trans sub (εClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∈ next
h : εClosure nfa pos next currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact εClosure_subset h
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
case h_6
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
cs✝ : Data.Classes
next✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ next✝
h :
  εClosure nfa pos inserted currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'

case h_7
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.fail
h : εClosure nfa pos inserted currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
next => exact SparseSet.subset_trans sub (εClosure_subset h)
Proof state after:
case h_7
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.fail
h : εClosure nfa pos inserted currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
case h_7
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.fail
h : εClosure nfa pos inserted currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
next => exact SparseSet.subset_trans sub (εClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
target'✝ : ℕ
heq✝ : nfa[target] = Node.epsilon target'✝
h : exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact SparseSet.subset_trans sub (exploreεClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
target₁✝ target₂✝ : ℕ
heq✝ : nfa[target] = Node.split target₁✝ target₂✝
h :
  exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target₁✝, ⋯⟩
      (stack.push (StackEntry.explore ⟨target₂✝, ⋯⟩)) =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact SparseSet.subset_trans sub (exploreεClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
offset✝ target'✝ : ℕ
heq✝ : nfa[target] = Node.save offset✝ target'✝
h :
  (if h : offset✝ < currentSave.size then
      exploreεClosure nfa pos inserted (currentSave.set ⟨offset✝, ⋯⟩ (some pos)) matched saveSlots ⟨target'✝, ⋯⟩
        (stack.push (StackEntry.restore currentSave))
    else exploreεClosure nfa pos inserted currentSave matched saveSlots ⟨target'✝, ⋯⟩ stack) =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
split at h <;> exact SparseSet.subset_trans sub (exploreεClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.done
h :
  εClosure nfa pos inserted currentSave (HOrElse.hOrElse matched fun x => some currentSave)
      (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact SparseSet.subset_trans sub (εClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
c✝ : Char
next✝ : ℕ
heq✝ : nfa[target] = Node.char c✝ next✝
h :
  εClosure nfa pos inserted currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact SparseSet.subset_trans sub (εClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
cs✝ : Data.Classes
next✝ : ℕ
heq✝ : nfa[target] = Node.sparse cs✝ next✝
h :
  εClosure nfa pos inserted currentSave matched (saveSlots.set ↑target ⋯ currentSave) stack =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact SparseSet.subset_trans sub (εClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.exploreεClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
target : Fin nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : target ∉ next
inserted : SparseSet nfa.nodes.size
hins : next.insert target = inserted
sub : next ⊆ inserted
heq✝ : nfa[target] = Node.fail
h : εClosure nfa pos inserted currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
exact SparseSet.subset_trans sub (εClosure_subset h)
Proof state after:
no goals
Theorem: Regex.VM.εClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h : εClosure nfa pos next currentSave matched saveSlots stack = (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
unfold εClosure at h
Proof state after:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h :
  (if hemp : stack.isEmpty = true then (matched, next, saveSlots)
    else
      let entry := stack.back' hemp;
      let stack' := stack.pop;
      let_fun this := ⋯;
      match entry with
      | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
      | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Theorem: Regex.VM.εClosure_subset
Proof state before:
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h :
  (if hemp : stack.isEmpty = true then (matched, next, saveSlots)
    else
      let entry := stack.back' hemp;
      let stack' := stack.pop;
      let_fun this := ⋯;
      match entry with
      | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
      | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ next ⊆ next'
Tactic:
split at h
Proof 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
h✝ : stack.isEmpty = true
h : (matched, next, saveSlots) = (matched', next', saveSlots')
⊢ next ⊆ next'

case inr
nfa : NFA
pos : String.Pos
next : SparseSet nfa.nodes.size
currentSave : Array (Option String.Pos)
matched : Option (Array (Option String.Pos))
saveSlots : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
stack : Array (StackEntry nfa.nodes.size)
matched' : Option (Array (Option String.Pos))
next' : SparseSet nfa.nodes.size
saveSlots' : Data.Vec (Array (Option String.Pos)) nfa.nodes.size
h✝ : ¬stack.isEmpty = true
h :
  (let entry := stack.back' h✝;
    let stack' := stack.pop;
    let_fun this := ⋯;
    match entry with
    | StackEntry.explore target => exploreεClosure nfa pos next currentSave matched saveSlots target stack'
    | StackEntry.restore save => εClosure nfa pos next save matched saveSlots stack') =
    (matched', next', saveSlots')
⊢ next ⊆ next'