Files
marqdo/verification/replay-policy/ReplayPolicy/Cursor.lean
cflmyandCursor 8f1010f967 Ship oracle journal values, bytecode/frontend hardening, and replay-policy Lean.
Host exposes oracle journals as language values with refuse/copy gates; bytecode and foreign session paths get modularized; applications and verification replay-policy sources land with Lake builds ignored.

Co-authored-by: Cursor <cursoragent@cursor.com>
2026-11-06 15:04:27 +08:00

133 lines
4.8 KiB
Lean4
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
import Lean
namespace Marqdo.ReplayCursor
inductive Reason where
| missing | request | reply | surplus | phase
deriving DecidableEq, Repr
inductive Phase where
| ready | pending | stopped (reason : Reason)
deriving DecidableEq, Repr
structure Cursor (Q R : Type) where
remaining : List (Q × R)
matched : Nat
phase : Phase
deriving Repr
def halt (c : Cursor Q R) (why : Reason) : Cursor Q R :=
match c.phase with
| .stopped _ => c
| _ => {c with phase := .stopped why}
variable {Q R S V : Type} [DecidableEq Q] [DecidableEq R]
def prepare (c : Cursor Q R) (request : Q) : Cursor Q R × Bool :=
match c.phase with
| .stopped _ => (c,false)
| .pending => (halt c .phase,false)
| .ready => match c.remaining with
| [] => (halt c .missing,false)
| (wanted,_)::_ => if request = wanted then ({c with phase := .pending},true)
else (halt c .request,false)
def receive (c : Cursor Q R) (actual : R) : Cursor Q R × Bool :=
match c.phase with
| .stopped _ => (c,false)
| .ready => (halt c .phase,false)
| .pending => match c.remaining with
| [] => (halt c .phase,false)
| (_,wanted)::rest =>
let consumed := {c with remaining := rest}
if actual = wanted then ({consumed with matched := c.matched+1, phase := .ready},true)
else (halt consumed .reply,false)
def finish (c : Cursor Q R) : Option Reason :=
match c.phase with
| .stopped why => some why
| .pending => some .phase
| .ready => if c.remaining.isEmpty then none else some .surplus
def WellFormed (c : Cursor Q R) : Prop := c.phase = .pending → c.remaining ≠ []
omit [DecidableEq R] in
theorem prepare_wellFormed (c : Cursor Q R) (q : Q) : WellFormed (prepare c q).1 := by
cases hp : c.phase with
| stopped why => simp [prepare,hp,WellFormed]
| pending => simp [prepare,hp,halt,WellFormed]
| ready =>
cases hs : c.remaining with
| nil => simp [prepare,hp,hs,halt,WellFormed]
| cons event rest =>
rcases event with ⟨wanted,reply⟩
by_cases h : q = wanted <;> simp [prepare,hp,hs,h,halt,WellFormed]
omit [DecidableEq Q] in
theorem receive_wellFormed (c : Cursor Q R) (r : R) : WellFormed (receive c r).1 := by
cases hp : c.phase with
| stopped why => simp [receive,hp,WellFormed]
| ready => simp [receive,hp,halt,WellFormed]
| pending =>
cases hs : c.remaining with
| nil => simp [receive,hp,hs,halt,WellFormed]
| cons event rest =>
rcases event with ⟨q,wanted⟩
by_cases h : r = wanted <;> simp [receive,hp,hs,h,halt,WellFormed]
omit [DecidableEq R] in
theorem prepare_stopped (events : List (Q × R)) (n : Nat) (why : Reason) (q : Q) :
prepare ⟨events,n,.stopped why⟩ q = (⟨events,n,.stopped why⟩,false) := rfl
omit [DecidableEq Q] in
theorem receive_stopped (events : List (Q × R)) (n : Nat) (why : Reason) (r : R) :
receive ⟨events,n,.stopped why⟩ r = (⟨events,n,.stopped why⟩,false) := rfl
omit [DecidableEq R] in
/-- A permit identifies exactly the head request; no assumption on replies. -/
theorem permit_has_expected_request (c : Cursor Q R) (q : Q)
(granted : (prepare c q).2 = true) :
∃ r rest, c.phase = .ready ∧ c.remaining = (q,r)::rest := by
cases hp : c.phase with
| stopped why => simp [prepare,hp] at granted
| pending => simp [prepare,hp] at granted
| ready =>
cases hs : c.remaining with
| nil => simp [prepare,hp,hs] at granted
| cons event rest =>
rcases event with ⟨wanted,reply⟩
by_cases h : q = wanted
· subst wanted; exact ⟨reply,rest,rfl,rfl⟩
· simp [prepare,hp,hs,h] at granted
omit [DecidableEq Q] [DecidableEq R] in
theorem finish_ready (events : List (Q × R)) (n : Nat) :
finish (Cursor.mk events n .ready) = none ↔ events = [] := by
cases events <;> simp [finish]
omit [DecidableEq Q] in
theorem matching_reply_consumes_one (q : Q) (r : R) (rest : List (Q × R)) (n : Nat) :
receive (Cursor.mk ((q,r)::rest) n .pending) r =
(Cursor.mk rest (n+1) .ready,true) := by
simp [receive]
omit [DecidableEq Q] in
theorem mismatching_reply_retains_match_count (q : Q) (wanted actual : R)
(rest : List (Q × R)) (n : Nat) (different : actual ≠ wanted) :
receive (Cursor.mk ((q,wanted)::rest) n .pending) actual =
(Cursor.mk rest n (.stopped .reply),false) := by
simp [receive,different,halt]
omit [DecidableEq R] in
theorem prepare_preserves_history (c : Cursor Q R) (q : Q) :
(prepare c q).1.remaining = c.remaining ∧ (prepare c q).1.matched = c.matched := by
cases hp : c.phase with
| stopped why => simp [prepare,hp]
| pending => simp [prepare,hp,halt]
| ready =>
cases hs : c.remaining with
| nil => simp [prepare,hp,hs,halt]
| cons event rest =>
rcases event with ⟨wanted,r⟩
by_cases h : q = wanted <;> simp [prepare,hp,hs,h,halt]
end Marqdo.ReplayCursor