Spill and processed-prefix invariant at the reverse-search queue test
OpenDirKECC1549.Main.reverse_search_dequeue_invariantLet G have n vertices and m edges with root r, and set B=n+2m+3 and S=16B+64. Suppose the original memory M contains GraphLayout G and stores r at parameter cell 5B+2, with 32B+256 at most the word modulus. At any reachable running state s with program counter 70, the spill pointer, saved original register words, and unchanged-memory region satisfy
There are a vertex-valued parent map P, a discovery list L, and a set E_s of scanned edges that form a ReverseScanTrace from its abstract initial state. The parent array in s encodes P. Writing h and t for the natural values of registers 9 and 10, respectively, the queue counters and scanned-edge coverage satisfy
Thus coverage is asserted only for the processed prefix. The next queue test may either start another dequeue or take the restoration branch. The theorem assumes neither queue exhaustion, a future halt, nor a running-time bound. Reachability is from the specified original input, not from an arbitrary state at counter 70.
import Definitions.Def_DirKECC1549_Main_Machine import Definitions.Def_DirKECC1549_Main_ReverseSearchCode import Definitions.Def_DirKECC1549_Main_ReverseScanTrace set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_dequeue_invariant
(n m : ℕ) (G : Fin m → Fin n × Fin n) (r : Fin n)
(w : Width) (mem : Memory w) (steps : ℕ)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hgraph : GraphLayout G mem)
(hroot : (mem (paramCell n m 2)).toNat = r)
(hpc : (runFrom reverseSearchAlgorithm.code w mem steps).pc = 70)
(hrunning : (runFrom reverseSearchAlgorithm.code w mem steps).halted = false) :
let S := 16 * blk n m + 64
let s := runFrom reverseSearchAlgorithm.code w mem steps
(s.mem 2).toNat = S ∧ s.mem (S + 16) = mem 0 ∧
(∀ a : ℕ, 1 ≤ a → a ≤ 16 → s.mem (S + a - 1) = mem a) ∧
(∀ a : ℕ, 16 < a → a < 6 * blk n m → s.mem a = mem a) ∧
∃ (par : Fin n → Fin n) (order : List (Fin n)) (scanned : Finset (Fin m)),
ReverseScanTrace G r par order scanned ∧
(s.mem 9).toNat ≤ order.length ∧ (s.mem 10).toNat = order.length ∧
(∀ e : Fin m, (G e).2 ∈ order.take (s.mem 9).toNat → e ∈ scanned) ∧
∀ v : Fin n, (s.mem (arrayCell n m v)).toNat = par v := by sorry
end DirKECC1549.Main