Files

646 lines
34 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.
/-
Released under Apache 2.0 license as described in the file LICENSE.
-/
import FormalConflictRange.CrossedGeneral
/-!
# The crossed nonpositive-begin complete overshoot closed form
A forward complete result at a negative begin offset whose `begin.key` lies strictly
above the reported head and whose end overshoots has a two-branch minimal sound
conflict range. Let `q = -begin.offset` be the begin slack and let `hmin` be the
number of reported keys strictly below `begin.key`. If `hmin ≤ q` the begin selector
clamps to the empty key, every key is forced, and the minimal range is `[⊥, ⊤)`.
Otherwise a compatible database resolves the begin selector exactly onto the reported
head (`hmin = q + 1`), the complete keys are the stored keys at or above the head, and
the minimal range is `[head, ⊤)`.
The clamp branch is minimal because inserting any key below the head forces a new
complete key; the nonclamp branch is sound because agreement on `[head, ⊤)` fixes the
begin resolution and the end sentinel.
-/
namespace FormalConflictRange
/-- The nonpositive begin slack, `-begin.offset` as a natural. -/
def beginSlack (r : RangeRead) : ℕ := (0 - r.begin.offset).toNat
/-- Reported keys strictly below `begin.key`. -/
def reportedBelowBegin (r : RangeRead) (res : Result) : ℕ :=
res.keys.countP (fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key))
/-- The crossed nonpositive-begin complete overshoot region (forward traversal). -/
abbrev negCrossOvershoot (r : RangeRead) (res : Result) : Prop :=
r.reverse = false ∧ r.begin.offset < 0 ∧ res.more = false ∧ res.keys ≠ [] ∧
2 ≤ r.end_.offset ∧
(∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key) ∧
((res.keys.headD ([] : Key) : Key) : WithTop Key) < r.begin.key
/-- The closed form for the crossed complete overshoot at a negative begin offset. -/
noncomputable def closedFormNegCrossOvershoot (r : RangeRead) (res : Result) : ConflictRange :=
if reportedBelowBegin r res ≤ beginSlack r then
⟨(([] : Key) : WithTop Key), (⊤ : WithTop Key)⟩
else topOfLast (res.keys.headD ([] : Key))
theorem beginSlack_cast (r : RangeRead) (h : r.begin.offset ≤ 0) :
(beginSlack r : ℤ) = -r.begin.offset := by
unfold beginSlack
rw [Int.toNat_of_nonneg (by omega)]
ring
theorem anchor_eq_count_sub_slack (db : DB) (r : RangeRead) (h : r.begin.offset ≤ 0) :
r.begin.anchor db =
(db.keys.countP (fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) : ℤ) -
(beginSlack r : ℤ) - 1 := by
unfold Selector.anchor
rw [beginSlack_cast r h]
ring
theorem result_sublist_db_of_compatible {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false) :
List.Sublist res.keys db.keys := by
have hpre := RangeRead.compatible_keys_prefix hcomp
have hck : RangeRead.completeKeys db r =
db.keys.filter (fun k : Key => decide (resolve db r.begin ≤ (k : WithTop Key) ∧
(k : WithTop Key) < resolve db r.end_)) := by
rw [RangeRead.completeKeys, ite_eq_right (by simp [hrev])]
rfl
rw [hck] at hpre
exact hpre.sublist.trans List.filter_sublist
theorem resolve_end_top_of_negCross_compat {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hne : res.keys ≠ [])
(hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key) :
resolve db r.end_ = (⊤ : WithTop Key) := by
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp hrev
have hmaxres : ∀ k ∈ res.keys, k ≤ res.keys.getLast hne :=
fun k hk => (hsort.pairwise.imp le_of_lt).rel_getLast hk
have hres_eq : res.keys = RangeRead.completeKeys db r := by
rcases hcomp.2 with ⟨hm, _, _⟩ | ⟨-, heq⟩
· simp [hmore] at hm
· exact heq
exact resolve_end_eq_top_of_hhi hcomp hend hhi (res.keys.getLast hne)
(List.getLast_mem hne) (fun k hk => hmaxres k (by rw [hres_eq]; exact hk))
/-- The compatibility data used by both branches: when `hmin > q`, a compatible
database resolves its begin selector exactly onto the reported head. -/
theorem resolve_begin_eq_head_of_negCross_compat {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hne : res.keys ≠ []) (hbegin : r.begin.offset < 0)
(hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(_hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hnonclamp : beginSlack r < reportedBelowBegin r res) :
resolve db r.begin = ((res.keys.head hne : Key) : WithTop Key) := by
set head : Key := res.keys.head hne with hhead
set cB := db.keys.countP (fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key))
with hcB
have hsub : List.Sublist res.keys db.keys := result_sublist_db_of_compatible hcomp hrev
have hmin_le : reportedBelowBegin r res ≤ cB := List.Sublist.countP_le hsub
have hcB_ge : beginSlack r + 1 ≤ cB :=
Nat.succ_le_of_lt (lt_of_lt_of_le hnonclamp hmin_le)
have hanchor_ge : 0 ≤ r.begin.anchor db := by
rw [anchor_eq_count_sub_slack db r (le_of_lt hbegin)]
have : (beginSlack r : ℤ) + 1 ≤ (cB : ℤ) := by exact_mod_cast hcB_ge
omega
have hres_eq : res.keys = RangeRead.completeKeys db r := by
rcases hcomp.2 with ⟨hm, _, _⟩ | ⟨-, heq⟩
· simp [hmore] at hm
· exact heq
have hhead_mem : head ∈ res.keys := List.head_mem hne
have hhead_ck : head ∈ RangeRead.completeKeys db r := by
rw [← hres_eq]; exact hhead_mem
have hle_head : resolve db r.begin ≤ ((head : Key) : WithTop Key) :=
(RangeRead.mem_completeKeys.mp hhead_ck).2.1
have hnot_top : resolve db r.begin ≠ (⊤ : WithTop Key) := by
intro htop
rw [htop] at hle_head
exact absurd hle_head (not_le.mpr (WithTop.coe_lt_top head))
have hltlen : (r.begin.anchor db).toNat < db.keys.length := by
by_contra h
exact hnot_top (resolve_eq_top hanchor_ge (le_of_not_gt h))
have hresolve_get : resolve db r.begin =
((db.keys[(r.begin.anchor db).toNat] : Key) : WithTop Key) :=
resolve_eq_getElem hanchor_ge hltlen
set k : Key := db.keys[(r.begin.anchor db).toNat] with hk
have hk_le_head : k ≤ head := WithTop.coe_le_coe.mp (by rw [← hresolve_get]; exact hle_head)
have hk_stored : k ∈ db.keys := List.getElem_mem hltlen
have hE := resolve_end_top_of_negCross_compat hcomp hrev hmore hne hend hhi
have hk_ck : k ∈ RangeRead.completeKeys db r :=
RangeRead.mem_completeKeys.mpr ⟨hk_stored, by rw [hresolve_get],
by rw [hE]; exact WithTop.coe_lt_top k⟩
have hk_ge_head : head ≤ k := by
have hmem : k ∈ res.keys := by rw [hres_eq]; exact hk_ck
exact (RangeRead.compatible_sortedLT hcomp hrev).pairwise.imp le_of_lt |>.rel_head hmem
have hk_eq : k = head := le_antisymm hk_le_head hk_ge_head
rw [← hk_eq]
exact hresolve_get
theorem negCross_compat_filter {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hne : res.keys ≠ []) (hbegin : r.begin.offset < 0)
(hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hnonclamp : beginSlack r < reportedBelowBegin r res) :
db.keys.filter (fun k : Key => decide (res.keys.head hne ≤ k)) = res.keys := by
set head : Key := res.keys.head hne with hhead
have hE := resolve_end_top_of_negCross_compat hcomp hrev hmore hne hend hhi
have hL := resolve_begin_eq_head_of_negCross_compat hcomp hrev hmore hne hbegin hend hhi
hcross hnonclamp
have hck := completeKeys_eq_topOfLast_keys (db := db) (r := r) (last := head) hrev hE hL
have hres_eq : res.keys = RangeRead.completeKeys db r := by
rcases hcomp.2 with ⟨hm, _, _⟩ | ⟨-, heq⟩
· simp [hmore] at hm
· exact heq
rw [hres_eq, hck]
theorem negCross_count_eq {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hne : res.keys ≠ []) (hbegin : r.begin.offset < 0)
(hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hnonclamp : beginSlack r < reportedBelowBegin r res) :
db.keys.countP (fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) =
db.keys.countP (fun k : Key =>
decide (((k : Key) : WithTop Key) < ((res.keys.head hne : Key) : WithTop Key))) +
reportedBelowBegin r res := by
set head : Key := res.keys.head hne with hhead
have hfil : db.keys.filter (fun k : Key => decide (head ≤ k)) = res.keys :=
negCross_compat_filter hcomp hrev hmore hne hbegin hend hhi hcross hnonclamp
cases hB : r.begin.key with
| top =>
have hcB : db.keys.countP (fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) =
db.keys.length := by rw [hB]; exact countP_lt_top
have hhmin : reportedBelowBegin r res = res.keys.length := by
unfold reportedBelowBegin; rw [hB]; exact countP_lt_top
have he : db.keys.countP (fun k : Key =>
decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) =
db.keys.countP (fun k : Key => decide (k < head)) := countP_lt_coe head
have hlen := List.length_eq_length_filter_add (l := db.keys)
(f := fun k : Key => decide (head ≤ k))
have hf1 : (db.keys.filter (fun k : Key => decide (head ≤ k))).length = res.keys.length := by
rw [hfil]
have hf2 : (db.keys.filter (fun k : Key => !decide (head ≤ k))).length =
db.keys.countP (fun k : Key => decide (k < head)) := by
rw [List.countP_eq_length_filter]
congr 1
apply List.filter_congr
intro k _
by_cases h : head ≤ k
· simp [h, not_lt.mpr h]
· simp [h, lt_of_not_ge h]
rw [hB] at hcB
rw [hcB, he, hhmin]
omega
| coe b =>
have hcross_key : head < b := by
rw [hB] at hcross
exact WithTop.coe_lt_coe.mp hcross
have hcB : db.keys.countP (fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) =
db.keys.countP (fun k : Key => decide (k < b)) := by rw [hB]; exact countP_lt_coe b
have he : db.keys.countP (fun k : Key =>
decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) =
db.keys.countP (fun k : Key => decide (k < head)) := countP_lt_coe head
have hhmin : reportedBelowBegin r res = res.keys.countP (fun k : Key => decide (k < b)) := by
unfold reportedBelowBegin; rw [hB]; exact countP_lt_coe b
have hsplit := countP_lt_eq_add_filter db.keys db.nodup (le_of_lt hcross_key)
have hfil2 : db.keys.filter (fun k : Key => decide (head ≤ k ∧ k < b)) =
res.keys.filter (fun k : Key => decide (k < b)) := by
rw [filter_and_eq_filter_filter (fun k : Key => head ≤ k) (fun k : Key => k < b), hfil]
have hlen : (db.keys.filter (fun k : Key => decide (head ≤ k ∧ k < b))).length =
res.keys.countP (fun k : Key => decide (k < b)) := by
rw [hfil2, List.countP_eq_length_filter]
rw [hB] at hcB
rw [hcB, he, hhmin]
omega
/-- A general count identity: if the stored keys at or above `head` are exactly `R`, then
the number of stored keys below `B` splits as those below `head` plus those of `R`
below `B`. -/
theorem count_eq_of_filter {l : List Key} {R : List Key} {head : Key} {B : WithTop Key}
(hnd : l.Nodup) (hheadB : ((head : Key) : WithTop Key) < B)
(hfil : l.filter (fun k : Key => decide (head ≤ k)) = R) :
l.countP (fun k : Key => decide (((k : Key) : WithTop Key) < B)) =
l.countP (fun k : Key => decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) +
R.countP (fun k : Key => decide (((k : Key) : WithTop Key) < B)) := by
cases B with
| top =>
have hcB : l.countP (fun k : Key => decide (((k : Key) : WithTop Key) < (⊤ : WithTop Key))) =
l.length := countP_lt_top
have hhmin : R.countP (fun k : Key => decide (((k : Key) : WithTop Key) < (⊤ : WithTop Key))) =
R.length := countP_lt_top
have he : l.countP (fun k : Key =>
decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) =
l.countP (fun k : Key => decide (k < head)) := countP_lt_coe head
have hlen := List.length_eq_length_filter_add (l := l)
(f := fun k : Key => decide (head ≤ k))
have hf1 : (l.filter (fun k : Key => decide (head ≤ k))).length = R.length := by
rw [hfil]
have hf2 : (l.filter (fun k : Key => !decide (head ≤ k))).length =
l.countP (fun k : Key => decide (k < head)) := by
rw [List.countP_eq_length_filter]
congr 1
apply List.filter_congr
intro k _
by_cases h : head ≤ k
· simp [h, not_lt.mpr h]
· simp [h, lt_of_not_ge h]
rw [hcB, he, hhmin]
omega
| coe b =>
have hcross_key : head < b := WithTop.coe_lt_coe.mp hheadB
have hcB : l.countP (fun k : Key => decide (((k : Key) : WithTop Key) < (↑b : WithTop Key))) =
l.countP (fun k : Key => decide (k < b)) := countP_lt_coe b
have he : l.countP (fun k : Key =>
decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) =
l.countP (fun k : Key => decide (k < head)) := countP_lt_coe head
have hhmin : R.countP (fun k : Key => decide (((k : Key) : WithTop Key) < (↑b : WithTop Key))) =
R.countP (fun k : Key => decide (k < b)) := countP_lt_coe b
have hsplit := countP_lt_eq_add_filter l hnd (le_of_lt hcross_key)
have hfil2 : l.filter (fun k : Key => decide (head ≤ k ∧ k < b)) =
R.filter (fun k : Key => decide (k < b)) := by
rw [filter_and_eq_filter_filter (fun k : Key => head ≤ k) (fun k : Key => k < b), hfil]
have hlen : (l.filter (fun k : Key => decide (head ≤ k ∧ k < b))).length =
R.countP (fun k : Key => decide (k < b)) := by
rw [hfil2, List.countP_eq_length_filter]
rw [hcB, he, hhmin]
omega
theorem negCross_hmin_eq {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hne : res.keys ≠ []) (hbegin : r.begin.offset < 0)
(hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hnonclamp : beginSlack r < reportedBelowBegin r res) :
reportedBelowBegin r res = beginSlack r + 1 := by
set head : Key := res.keys.head hne with hhead
have hcount := negCross_count_eq hcomp hrev hmore hne hbegin hend hhi hcross hnonclamp
set cH : ℕ := db.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) with hcH
set cB : ℕ := db.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) with hcB
have hsub : List.Sublist res.keys db.keys := result_sublist_db_of_compatible hcomp hrev
have hmin_le : reportedBelowBegin r res ≤ cB := List.Sublist.countP_le hsub
have hcB_ge : beginSlack r + 1 ≤ cB :=
Nat.succ_le_of_lt (lt_of_lt_of_le hnonclamp hmin_le)
have hanchor_ge : 0 ≤ r.begin.anchor db := by
rw [anchor_eq_count_sub_slack db r (le_of_lt hbegin)]
have : (beginSlack r : ℤ) + 1 ≤ (cB : ℤ) := by exact_mod_cast hcB_ge
omega
have hL := resolve_begin_eq_head_of_negCross_compat hcomp hrev hmore hne hbegin hend hhi
hcross hnonclamp
have hhead_mem : head ∈ res.keys := by rw [hhead]; exact List.head_mem hne
have hhead_db : head ∈ db.keys := RangeRead.compatible_keys_subset hcomp hhead_mem
have hnot_top : resolve db r.begin ≠ (⊤ : WithTop Key) := by
intro htop
rw [hL] at htop
exact absurd htop (WithTop.coe_ne_top (a := head))
have hltlen : (r.begin.anchor db).toNat < db.keys.length := by
by_contra h
exact hnot_top (resolve_eq_top (db := db) hanchor_ge (le_of_not_gt h))
have hget := resolve_eq_getElem (db := db) (s := r.begin) hanchor_ge hltlen
have hidx : db.keys[(r.begin.anchor db).toNat] = head := by
have hcoe : ((db.keys[(r.begin.anchor db).toNat] : Key) : WithTop Key) =
((head : Key) : WithTop Key) := by rw [← hget, hL]
exact WithTop.coe_injective hcoe
have hrank : db.keys.countP (fun k => decide (k < head)) = (r.begin.anchor db).toNat :=
countP_lt_eq_of_getElem db.sorted hltlen hidx
have hcH_eq : cH = (r.begin.anchor db).toNat := by
rw [hcH, countP_lt_coe head]
exact hrank
have hanchor_cast : r.begin.anchor db = (cB : ℤ) - (beginSlack r : ℤ) - 1 := by
rw [anchor_eq_count_sub_slack db r (le_of_lt hbegin), ← hcB]
have htoNat : (r.begin.anchor db).toNat = cB - (beginSlack r + 1) := by
have hz : r.begin.anchor db = ((cB : ℤ) - ((beginSlack r + 1 : ℕ) : ℤ)) := by
rw [hanchor_cast]; push_cast; ring
have hz2 : ((cB : ℤ) - ((beginSlack r + 1 : ℕ) : ℤ)) =
((cB - (beginSlack r + 1) : ℕ) : ℤ) := by
rw [← Nat.cast_sub hcB_ge]
rw [hz, hz2, Int.toNat_natCast]
have hcH_add : cH + (beginSlack r + 1) = cB := by
rw [hcH_eq, htoNat]
exact Nat.sub_add_cancel hcB_ge
omega
/-- In the clamp region every key below the reported head is necessary: inserting it
into the database made of the reported keys either clamps the begin selector to the
empty key or lands it on the inserted key, and either way the complete keys gain a
key, so the result is no longer compatible. -/
theorem necessary_below_head_of_negCross_clamp {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0) (hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hclamp : reportedBelowBegin r res ≤ beginSlack r)
{k : Key} (hk : ((k : Key) : WithTop Key) < ((res.keys.head hne : Key) : WithTop Key)) :
Necessary r res k := by
obtain ⟨db₀, hcomp₀⟩ := hread
intro cr hs
by_contra hkcr
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hk_not : k ∉ res.keys := by
intro hkmem
exact hkcr (necessary_of_mem_result ⟨db₀, hcomp₀⟩ hkmem cr hs)
let db₁ : DB := ⟨res.keys, hsort⟩
have hcB₁ : db₁.keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res := rfl
have hanchor₁ : r.begin.anchor db₁ < 0 := by
rw [anchor_eq_count_sub_slack db₁ r (le_of_lt hbegin), hcB₁]
have : (reportedBelowBegin r res : ℤ) ≤ (beginSlack r : ℤ) := by exact_mod_cast hclamp
omega
have hL₁ : resolve db₁ r.begin = (([] : Key) : WithTop Key) :=
resolve_eq_nil (db := db₁) (s := r.begin) hanchor₁
have hE₁ : resolve db₁ r.end_ = (⊤ : WithTop Key) :=
resolve_eq_top_of_all_lt (db := db₁) (fun x hx => hhi x hx) hend
have hfil₁ : db₁.keys.filter (fun x : Key => decide (([] : Key) ≤ x)) = res.keys := by
have hself : db₁.keys.filter (fun x : Key => decide (([] : Key) ≤ x)) = db₁.keys := by
rw [List.filter_eq_self]
intro x _; rw [decide_eq_true_eq]; exact nil_le_key x
rw [hself]
have hcomp₁ : RangeRead.Compatible db₁ r res := by
refine ⟨hcomp₀.1, Or.inr ⟨hmore, ?_⟩⟩
rw [RangeRead.completeKeys, ite_eq_right (by simp [hrev]), hL₁, hE₁]
simpa [RangeRead.inRange] using hfil₁.symm
let db₂ : DB := db₁.insert k hk_not
have hagree : AgreeOn cr db₁ db₂ :=
(ConflictRange.keys_insert_of_not_mem cr db₁ hk_not hkcr).symm
have hcomp₂ : RangeRead.Compatible db₂ r res := (hs db₁ db₂ hagree).mp hcomp₁
have hck₂ : RangeRead.completeKeys db₂ r = res.keys := by
rcases hcomp₂.2 with ⟨hm, _, _⟩ | ⟨-, heq⟩
· simp [hmore] at hm
· exact heq.symm
have hdb₂_keys : db₂.keys = k :: res.keys := by
unfold db₂
rw [DB.insert_keys, show db₁.keys = res.keys from rfl]
cases hres : res.keys with
| nil => exact absurd hres hne
| cons a t =>
have hhead_a : res.keys.head hne = a := by simp [hres]
have hka : k ≤ a := by
rw [hhead_a] at hk
exact le_of_lt (WithTop.coe_lt_coe.mp hk)
rw [List.orderedInsert_cons_of_le (r := (· ≤ ·)) (a := k) (b := a) t hka]
have hkltB : ((k : Key) : WithTop Key) < r.begin.key := lt_trans hk hcross
have hcB₂ : db₂.keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res + 1 := by
rw [hdb₂_keys, List.countP_cons]
rw [decide_eq_true_eq.mpr hkltB]
simp [reportedBelowBegin]
have hanchor₂ : r.begin.anchor db₂ ≤ 0 := by
rw [anchor_eq_count_sub_slack db₂ r (le_of_lt hbegin), hcB₂]
have : (reportedBelowBegin r res : ℤ) ≤ (beginSlack r : ℤ) := by exact_mod_cast hclamp
omega
have hL₂_le : resolve db₂ r.begin ≤ ((k : Key) : WithTop Key) := by
by_cases hneg : r.begin.anchor db₂ < 0
· rw [resolve_eq_nil (db := db₂) (s := r.begin) hneg]
exact WithTop.coe_le_coe.mpr (nil_le_key k)
· have hzero : r.begin.anchor db₂ = 0 := by omega
have hltlen₂ : (r.begin.anchor db₂).toNat < db₂.keys.length := by
rw [hzero, hdb₂_keys]
simp
rw [resolve_eq_getElem (db := db₂) (s := r.begin) (by omega) hltlen₂]
have hval₂ : db₂.keys[(r.begin.anchor db₂).toNat]'hltlen₂ = k := by
simp [hzero, hdb₂_keys]
exact WithTop.coe_le_coe.mpr (le_of_eq hval₂)
have hall₂ : ∀ x ∈ db₂.keys, ((x : Key) : WithTop Key) < r.end_.key := by
intro x hx
rw [hdb₂_keys] at hx
rcases List.mem_cons.mp hx with rfl | hx
· exact lt_of_lt_of_le hk (le_of_lt (hhi _ (List.head_mem hne)))
· exact hhi x hx
have hE₂ : resolve db₂ r.end_ = (⊤ : WithTop Key) :=
resolve_eq_top_of_all_lt hall₂ hend
have hk_ck₂ : k ∈ RangeRead.completeKeys db₂ r := by
rw [RangeRead.mem_completeKeys]
refine ⟨by rw [hdb₂_keys]; exact List.mem_cons_self .., hL₂_le, ?_⟩
rw [hE₂]; exact WithTop.coe_lt_top k
rw [hck₂] at hk_ck₂
exact hk_not hk_ck₂
/-- **The clamp branch of the negative-offset crossed complete overshoot.** When the
reported keys below `begin.key` fit in the begin slack, every key is necessary, so the
full range is minimal. -/
theorem minimal_fullRange_of_negCross_clamp {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0) (hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hclamp : reportedBelowBegin r res ≤ beginSlack r) :
Minimal r res ⟨(([] : Key) : WithTop Key), (⊤ : WithTop Key)⟩ := by
refine (minimal_iff_sound_and_necessary).mpr ⟨sound_fullRange r res, ?_⟩
intro k _
by_cases hkhead : ((k : Key) : WithTop Key) <
((res.keys.head hne : Key) : WithTop Key)
· exact necessary_below_head_of_negCross_clamp hread hrev hmore hne hbegin hend hhi
hcross hclamp hkhead
· have hhead_le : res.keys.head hne ≤ k := WithTop.coe_le_coe.mp (le_of_not_gt hkhead)
by_cases hklast : k ≤ res.keys.getLast hne
· exact necessary_of_between_result hread (List.head_mem hne) (List.getLast_mem hne)
hhead_le hklast
· exact necessary_of_end_offset_ge_two hread hrev hmore hne hend hhi
(le_of_lt (lt_of_not_ge hklast))
/-- **Soundness of the top range from the reported head in the nonclamp branch.**
Agreement on `[head, ⊤)` fixes the stored keys at or above the head, hence the begin
resolution (`hmin = q + 1` forces the selector onto the head) and the end sentinel, so
the complete keys are unchanged. -/
theorem sound_topOfLast_of_negCross_nonclamp {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hmore : res.more = false) (hne : res.keys ≠ [])
(hbegin : r.begin.offset < 0) (hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hnonclamp : beginSlack r < reportedBelowBegin r res) :
Sound r res (topOfLast (res.keys.head hne)) := by
intro db₁ db₂ hagree
have step : ∀ db db', AgreeOn (topOfLast (res.keys.head hne)) db db' →
RangeRead.Compatible db r res → RangeRead.Compatible db' r res := by
intro db db' hag' hcomp_db
set head : Key := res.keys.head hne with hhead
have hhead_mem : head ∈ res.keys := by rw [hhead]; exact List.head_mem hne
have hhmin : reportedBelowBegin r res = beginSlack r + 1 :=
negCross_hmin_eq hcomp_db hrev hmore hne hbegin hend hhi hcross hnonclamp
have hE := resolve_end_top_of_negCross_compat hcomp_db hrev hmore hne hend hhi
have hL := resolve_begin_eq_head_of_negCross_compat hcomp_db hrev hmore hne hbegin
hend hhi hcross hnonclamp
have hres_eq : res.keys = RangeRead.completeKeys db r := by
rcases hcomp_db.2 with ⟨hm, _, _⟩ | ⟨-, heq⟩
· simp [hmore] at hm
· exact heq
have hck : RangeRead.completeKeys db r =
db.keys.filter (fun k => decide (head ≤ k)) :=
completeKeys_eq_topOfLast_keys hrev hE hL
have hagree_keys : db.keys.filter (fun k => decide (head ≤ k)) =
db'.keys.filter (fun k => decide (head ≤ k)) := by
have h := hag'
rw [AgreeOn, topOfLast_keys, topOfLast_keys] at h
exact h
have hfil' : db'.keys.filter (fun k => decide (head ≤ k)) = res.keys := by
rw [← hagree_keys, ← hck, hres_eq]
have hall' : ∀ k ∈ db'.keys, ((k : Key) : WithTop Key) < r.end_.key := by
intro k hk
by_cases hkh : head ≤ k
· have : k ∈ db'.keys.filter (fun k => decide (head ≤ k)) :=
List.mem_filter.mpr ⟨hk, by rw [decide_eq_true_eq]; exact hkh⟩
rw [hfil'] at this
exact hhi k this
· exact lt_of_lt_of_le (WithTop.coe_lt_coe.mpr (lt_of_not_ge hkh))
(le_of_lt (hhi head hhead_mem))
have hE' : resolve db' r.end_ = (⊤ : WithTop Key) :=
resolve_eq_top_of_all_lt hall' hend
have hhead_db' : head ∈ db'.keys := by
have : head ∈ db'.keys.filter (fun k => decide (head ≤ k)) := by
rw [hfil']; exact hhead_mem
exact List.mem_of_mem_filter this
have hcount' : db'.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) =
db'.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) +
reportedBelowBegin r res :=
count_eq_of_filter db'.nodup hcross hfil'
have hcB'_ge : beginSlack r + 1 ≤ db'.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) := by
rw [hcount', hhmin]; omega
have hanchor'_ge : 0 ≤ r.begin.anchor db' := by
rw [anchor_eq_count_sub_slack db' r (le_of_lt hbegin)]
have : (beginSlack r : ℤ) + 1 ≤ ((db'.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key))) : ℤ) := by
exact_mod_cast hcB'_ge
omega
have htoNat' : (r.begin.anchor db').toNat =
db'.keys.countP (fun k : Key =>
decide (((k : Key) : WithTop Key) < r.begin.key)) - (beginSlack r + 1) := by
have hz : r.begin.anchor db' = ((db'.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) : ℤ) -
((beginSlack r + 1 : ℕ) : ℤ)) := by
rw [anchor_eq_count_sub_slack db' r (le_of_lt hbegin)]; push_cast; ring
have hz2 : ((db'.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < r.begin.key)) : ℕ) : ℤ) -
((beginSlack r + 1 : ℕ) : ℤ) =
((db'.keys.countP (fun k : Key =>
decide (((k : Key) : WithTop Key) < r.begin.key)) -
(beginSlack r + 1) : ℕ) : ℤ) := by
rw [← Nat.cast_sub hcB'_ge]
rw [hz, hz2, Int.toNat_natCast]
have hidx_eq : (r.begin.anchor db').toNat =
db'.keys.countP (fun k => decide (k < head)) := by
have hcH'_eq : db'.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < ((head : Key) : WithTop Key))) =
db'.keys.countP (fun k => decide (k < head)) := countP_lt_coe head
rw [htoNat', hcount', hhmin, hcH'_eq]
omega
have hltlen' : (r.begin.anchor db').toNat < db'.keys.length := by
rw [hidx_eq]
obtain ⟨i, hi, hix⟩ := List.mem_iff_getElem.mp hhead_db'
rw [countP_lt_eq_of_getElem db'.sorted hi hix]
exact hi
have hval : db'.keys[(r.begin.anchor db').toNat]'hltlen' = head := by
simpa [hidx_eq] using getElem_countP_lt db'.sorted hhead_db'
have hL' : resolve db' r.begin = ((head : Key) : WithTop Key) := by
rw [resolve_eq_getElem (db := db') (s := r.begin) hanchor'_ge hltlen']
exact congrArg (fun x => ((x : Key) : WithTop Key)) hval
have hck' : RangeRead.completeKeys db' r =
db'.keys.filter (fun k => decide (head ≤ k)) :=
completeKeys_eq_topOfLast_keys hrev hE' hL'
exact ⟨hcomp_db.1, Or.inr ⟨hmore, by rw [hck', hfil']⟩⟩
exact ⟨step db₁ db₂ hagree, step db₂ db₁ hagree.symm⟩
/-- **The nonclamp branch of the negative-offset crossed complete overshoot.** The top
range from the reported head is minimal: soundness is above, and every key at or above
the head is necessary by convexity or by the overshoot necessity. -/
theorem minimal_topOfLast_of_negCross_nonclamp {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0) (hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key)
(hnonclamp : beginSlack r < reportedBelowBegin r res) :
Minimal r res (topOfLast (res.keys.head hne)) := by
refine (minimal_iff_sound_and_necessary).mpr
⟨sound_topOfLast_of_negCross_nonclamp hrev hmore hne hbegin hend hhi hcross hnonclamp, ?_⟩
intro k hk
have hhead_le : res.keys.head hne ≤ k := WithTop.coe_le_coe.mp hk.1
by_cases hklast : k ≤ res.keys.getLast hne
· exact necessary_of_between_result hread (List.head_mem hne) (List.getLast_mem hne)
hhead_le hklast
· exact necessary_of_end_offset_ge_two hread hrev hmore hne hend hhi
(le_of_lt (lt_of_not_ge hklast))
theorem headD_eq_head_of_ne {l : List Key} (h : l ≠ []) :
l.headD ([] : Key) = l.head h := by
cases l with
| nil => exact absurd rfl h
| cons a t => rfl
/-- **Closed form for the negative-offset crossed complete overshoot (forward).** -/
theorem minimal_closedForm_of_negCross_overshoot {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hbegin : r.begin.offset < 0)
(hmore : res.more = false) (hne : res.keys ≠ []) (hend : 2 ≤ r.end_.offset)
(hhi : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
(hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key) :
Minimal r res (closedFormNegCrossOvershoot r res) := by
unfold closedFormNegCrossOvershoot
by_cases hclamp : reportedBelowBegin r res ≤ beginSlack r
· rw [ite_eq_left hclamp]
exact minimal_fullRange_of_negCross_clamp hread hrev hmore hne hbegin hend hhi hcross hclamp
· rw [ite_eq_right hclamp]
have hheadD : res.keys.headD ([] : Key) = res.keys.head hne :=
headD_eq_head_of_ne hne
rw [hheadD]
exact minimal_topOfLast_of_negCross_nonclamp hread hrev hmore hne hbegin hend hhi hcross
(lt_of_not_ge hclamp)
theorem getLastD_eq_getLast_of_ne {l : List Key} (h : l ≠ []) :
l.getLastD ([] : Key) = l.getLast h := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast h]; rfl
/-- The crossed nonpositive-begin complete overshoot region (reversed traversal). -/
abbrev negCrossOvershootRev (r : RangeRead) (res : Result) : Prop :=
r.reverse = true ∧ r.begin.offset < 0 ∧ res.more = false ∧ res.keys ≠ [] ∧
2 ≤ r.end_.offset ∧
(∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key) ∧
((res.keys.getLastD ([] : Key) : Key) : WithTop Key) < r.begin.key
/-- The reversed closed form, expressed through the forward rule on the flipped read. -/
noncomputable def closedFormNegCrossOvershootRev (r : RangeRead) (res : Result) :
ConflictRange :=
closedFormNegCrossOvershoot { r with reverse := false }
{ keys := res.keys.reverse, more := false }
/-- **Closed form for the negative-offset crossed complete overshoot (reversed).** -/
theorem minimal_closedForm_of_negCross_overshoot_rev {r : RangeRead} {res : Result}
(hread : Readable r res) (h : negCrossOvershootRev r res) :
Minimal r res (closedFormNegCrossOvershootRev r res) := by
obtain ⟨hrev, hbegin, hmore, hne, hend, hhi, hcross⟩ := h
let r' : RangeRead := { r with reverse := false }
let res' : Result := { keys := res.keys.reverse, more := false }
have hread' : Readable r' res' := by
obtain ⟨db, hcomp⟩ := hread
exact ⟨db, (compatible_flip (b := true) hrev hmore).mpr hcomp⟩
have hne' : res'.keys ≠ [] := by simpa [res'] using hne
have hhi' : ∀ k ∈ res'.keys, ((k : Key) : WithTop Key) < r'.end_.key := by
intro k hk
exact hhi k (by simpa [res'] using hk)
have hhead' : res'.keys.head hne' = res.keys.getLast hne := by
simp [res']
have hcross' : ((res'.keys.head hne' : Key) : WithTop Key) < r'.begin.key := by
rw [hhead']
rw [show res.keys.getLastD ([] : Key) = res.keys.getLast hne from
getLastD_eq_getLast_of_ne hne] at hcross
simpa [r'] using hcross
have hmin' : Minimal r' res' (closedFormNegCrossOvershoot r' res') :=
minimal_closedForm_of_negCross_overshoot hread' rfl hbegin rfl hne' hend hhi' hcross'
exact (minimal_flip (r := r) (res := res) (cr := closedFormNegCrossOvershoot r' res')
(b := true) hrev hmore).mp hmin'
end FormalConflictRange