Files

523 lines
27 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.NegCrossTruncClampLastGe
import FormalConflictRange.Empty
/-!
# The crossed negative-begin truncated cell with the end sentinel
This module closes a cell left open by the compact residual: a forward, crossed,
truncated read with a negative begin offset, a nonpositive end offset, the reported
keys below `begin.key`, and the end key at the sentinel `⊤`. The end key being the
sentinel means the end selector resolves to an ordinary stored key (since its offset is
nonpositive) and the whole key space above `begin.key` is available for padding.
The minimal sound range is `[⊥, ⊤)`: every genuine key is necessary. Below the reported
head, inserting the key prepends it to the complete window; at or above `begin.key`, a
witness database stores the reported keys together with `1 - end.offset` pad keys above
`begin.key`, so erasing the target shortens the complete window and breaks the reported
prefix. Convexity between the reported last and `begin.key` fills the gap.
-/
open FormalConflictRange
namespace FormalConflictRange
/-- A forward truncated, crossed, negative-begin read with a nonpositive end offset, a
clamped begin selector, the reported keys below `begin.key`, and the end key at the
sentinel. -/
def negCrossTruncStrictTop (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = false ∧ r.begin.offset < 0 ∧ res.keys ≠ [] ∧
((res.keys.headD ([] : Key) : Key) : WithTop Key) < r.begin.key ∧
r.end_.offset ≤ 0 ∧ reportedBelowBegin r res ≤ beginSlack r ∧
r.end_.key = (⊤ : WithTop Key) ∧
((res.keys.getLastD ([] : Key) : Key) : WithTop Key) < r.begin.key ∧
r.begin.key < r.end_.key
/-- Storing the reported keys followed by pad keys at or above `begin.key` gives a
compatible database whose begin selector clamps and whose end selector lands on the
first pad key. -/
theorem compat_of_pad_top {r : RangeRead} {res : Result} {F : List Key} {m : ℕ}
(hread : Readable r res) (hne : res.keys ≠ []) (hrev : r.reverse = false)
(hmore : res.more = true) (hbegin : r.begin.offset < 0)
(hend : r.end_.offset ≤ 0)
(htop : r.end_.key = (⊤ : WithTop Key))
(hclamp : reportedBelowBegin r res ≤ beginSlack r)
(hallB : ∀ x ∈ res.keys, ((x : Key) : WithTop Key) < r.begin.key)
(hFsorted : F.SortedLT) (hFlen : F.length = m)
(hm : m = (1 - r.end_.offset).toNat)
(hFne : F ≠ []) (hFge : ∀ x ∈ F, r.begin.key ≤ ((x : Key) : WithTop Key))
(hFlast : ∀ x ∈ F, res.keys.getLast hne < x) :
∃ dbw : DB, dbw.keys = res.keys ++ F ∧ RangeRead.Compatible dbw r res ∧
resolve dbw r.begin = (([] : Key) : WithTop Key) ∧
resolve dbw r.end_ = ((F.head hFne : Key) : WithTop Key) := by
classical
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hle_last : ∀ x ∈ res.keys, x ≤ res.keys.getLast hne :=
fun x hx => (hsort.pairwise.imp le_of_lt).rel_getLast hx
have hDsort : (res.keys ++ F).SortedLT := by
refine List.sortedLT_append.mpr ⟨hsort, hFsorted, ?_⟩
intro a ha b hb
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le (hallB a ha) (hFge b hb))
let dbw : DB := ⟨res.keys ++ F, hDsort⟩
have hdbw_keys : dbw.keys = res.keys ++ F := rfl
have hcountB : dbw.keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res := by
rw [hdbw_keys, List.countP_append]
have h1 : res.keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res := rfl
have h2 : F.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
simp only [decide_eq_true_eq]
exact not_lt.mpr (hFge x hx)
rw [h1, h2, Nat.add_zero]
have hanchorB : r.begin.anchor dbw < 0 := by
rw [anchor_eq_count_sub_slack dbw r (le_of_lt hbegin), hcountB]
have hle : (reportedBelowBegin r res : ℤ) ≤ (beginSlack r : ℤ) := by exact_mod_cast hclamp
omega
have hrb : resolve dbw r.begin = (([] : Key) : WithTop Key) := resolve_eq_nil hanchorB
have hlenD : (res.keys ++ F).length = res.keys.length + m := by
rw [List.length_append, hFlen]
have hm_int : (m : Int) = 1 - r.end_.offset := by
rw [hm]; exact Int.toNat_of_nonneg (by omega)
have hanchorE : r.end_.anchor dbw = (res.keys.length : Int) := by
rw [anchor_of_top (s := r.end_) htop, hdbw_keys, hlenD]
push_cast
rw [hm_int]; ring
have hDget? : dbw.keys[res.keys.length]? = some (F.head hFne) := by
change (res.keys ++ F)[res.keys.length]? = some (F.head hFne)
rw [List.getElem?_append]
rw [ite_eq_right (not_lt.mpr (le_refl _)), Nat.sub_self]
rw [List.getElem?_eq_getElem (by rw [hFlen]; omega), List.head_eq_getElem hFne]
have hre : resolve dbw r.end_ = ((F.head hFne : Key) : WithTop Key) := by
rw [resolve, ite_eq_right (by rw [hanchorE]; omega)]
rw [hanchorE, Int.toNat_natCast, hDget?]
have hltF : ((res.keys.getLast hne : Key) : WithTop Key) < resolve dbw r.end_ := by
rw [hre]
exact WithTop.coe_lt_coe.mpr (hFlast (F.head hFne) (List.head_mem hFne))
have hckw : (RangeRead.completeKeys dbw r).filter
(fun x : Key => decide (x ≤ res.keys.getLast hne)) = res.keys := by
rw [completeKeys_filter_le_of_resolve_begin (db := dbw) hrev (H := ([] : Key)) hrb hltF]
rw [hdbw_keys, List.filter_append]
have hres_fil : res.keys.filter (fun x : Key => decide
(((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x ≤ res.keys.getLast hne)) = res.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact ⟨coe_nil_le_key_withTop _, hle_last x hx⟩
have hF_fil : F.filter (fun x : Key => decide
(((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x ≤ res.keys.getLast hne)) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx
simp only [Bool.not_eq_true, decide_eq_false_iff_not, not_and]
exact fun _ => not_le.mpr (hFlast x hx)
rw [hres_fil, hF_fil, List.append_nil]
have hcompw : RangeRead.Compatible dbw r res := by
rw [compatible_iff_truncated_keys hrev hmore hne]
exact ⟨hcomp₀.1, hckw⟩
exact ⟨dbw, hdbw_keys, hcompw, hrb, hre⟩
/-- Below the reported head, inserting the key into the padded witness prepends it to
the complete window, breaking the truncated prefix. -/
theorem exists_witness_below_head_of_negCross_trunc_strict_top {r : RangeRead} {res : Result}
{k : Key}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = true)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0)
(hend : r.end_.offset ≤ 0)
(htop : r.end_.key = (⊤ : WithTop Key))
(hBltTop : r.begin.key < (⊤ : WithTop Key))
(hclamp : reportedBelowBegin r res ≤ beginSlack r)
(hallB : ∀ x ∈ res.keys, ((x : Key) : WithTop Key) < r.begin.key)
(hk : ((k : Key) : WithTop Key) < ((res.keys.head hne : Key) : WithTop Key)) :
∃ dbw : DB, ∃ hkdb : k ∉ dbw.keys, RangeRead.Compatible dbw r res ∧
¬ RangeRead.Compatible (dbw.insert k hkdb) r res := by
classical
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hhead_le_last : res.keys.head hne ≤ res.keys.getLast hne :=
(hsort.pairwise.imp le_of_lt).rel_getLast (List.head_mem hne)
have hhead_le : ∀ x ∈ res.keys, res.keys.head hne ≤ x :=
fun x hx => (hsort.pairwise.imp le_of_lt).rel_head hx
have hk_head : k < res.keys.head hne := WithTop.coe_lt_coe.mp hk
set m : ℕ := (1 - r.end_.offset).toNat with hm
have hm1 : 1 ≤ m := by rw [hm]; omega
have hcard : (m : ℕ∞) ≤ intervalCard r.begin.key (⊤ : WithTop Key) := by
rw [intervalCard_top_right (ne_of_lt hBltTop)]
exact le_top
obtain ⟨dbf, hdbfIn, hdbfLen⟩ :=
exists_db_keysIn (B := r.begin.key) (E := (⊤ : WithTop Key)) (m := m) hcard
set F : List Key := dbf.keys with hF
have hFsorted : F.SortedLT := dbf.sorted
have hFlen : F.length = m := hdbfLen
have hFne : F ≠ [] := by
intro h; rw [h] at hFlen; simp at hFlen; omega
have hFge : ∀ x ∈ F, r.begin.key ≤ ((x : Key) : WithTop Key) :=
fun x hx => (hdbfIn x hx).1
have hlast_lt_B : ((res.keys.getLast hne : Key) : WithTop Key) < r.begin.key :=
hallB _ (List.getLast_mem hne)
have hFlast : ∀ x ∈ F, res.keys.getLast hne < x := by
intro x hx
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le hlast_lt_B (hFge x hx))
obtain ⟨dbw, hdbw_keys, hcompw, _hrb, _hre⟩ :=
compat_of_pad_top ⟨db₀, hcomp₀⟩ hne hrev hmore hbegin hend htop hclamp hallB hFsorted hFlen
hm hFne hFge hFlast
have hk_not_res : k ∉ res.keys := fun hx => absurd (hhead_le k hx) (not_le.mpr hk_head)
have hhead_lt_B : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key :=
hallB _ (List.head_mem hne)
have hk_lt_B : ((k : Key) : WithTop Key) < r.begin.key := lt_trans hk hhead_lt_B
have hk_not_F : k ∉ F := fun hx => absurd (hFge k hx) (not_le.mpr hk_lt_B)
have hkdb : k ∉ dbw.keys := by
rw [hdbw_keys]
simp [hk_not_res, hk_not_F]
have hins_keys : (dbw.insert k hkdb).keys = k :: (res.keys ++ F) := by
rw [DB.insert_keys, hdbw_keys]
cases hres : res.keys with
| nil => exact absurd hres hne
| cons a t =>
have hka : k ≤ a := le_of_lt (WithTop.coe_lt_coe.mp (by simpa [hres] using hk))
rw [List.cons_append]
rw [List.orderedInsert_cons_of_le (r := (· ≤ ·)) (a := k) (b := a) (l := t ++ F) hka]
have hcountB' : (dbw.insert k hkdb).keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res + 1 := by
rw [hins_keys, List.countP_cons, List.countP_append]
have h1 : res.keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res := rfl
have h2 : F.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
simp only [decide_eq_true_eq]
exact not_lt.mpr (hFge x hx)
simp [h1, h2, hk_lt_B]
have hanchorB' : r.begin.anchor (dbw.insert k hkdb) ≤ 0 := by
rw [anchor_eq_count_sub_slack (dbw.insert k hkdb) r (le_of_lt hbegin), hcountB']
have hle : (reportedBelowBegin r res : ℤ) ≤ (beginSlack r : ℤ) := by exact_mod_cast hclamp
omega
have hlen' : (dbw.insert k hkdb).keys.length = res.keys.length + m + 1 := by
rw [hins_keys, List.length_cons, List.length_append, hFlen]
have hm_int : (m : Int) = 1 - r.end_.offset := by
rw [hm]; exact Int.toNat_of_nonneg (by omega)
have hanchorE' : r.end_.anchor (dbw.insert k hkdb) = (res.keys.length : Int) + 1 := by
rw [anchor_of_top (s := r.end_) htop, hlen']
push_cast
rw [hm_int]; ring
have hD'get? : (dbw.insert k hkdb).keys[res.keys.length + 1]? = some (F.head hFne) := by
rw [hins_keys, List.getElem?_cons_succ]
rw [List.getElem?_append]
rw [ite_eq_right (not_lt.mpr (le_refl _)), Nat.sub_self]
rw [List.getElem?_eq_getElem (by rw [hFlen]; omega), List.head_eq_getElem hFne]
have hre' : resolve (dbw.insert k hkdb) r.end_ =
((F.head hFne : Key) : WithTop Key) := by
rw [resolve, ite_eq_right (by rw [hanchorE']; omega)]
have hnat : ((res.keys.length : Int) + 1).toNat = res.keys.length + 1 := by
rw [← Nat.cast_one, ← Nat.cast_add, Int.toNat_natCast]
rw [hanchorE', hnat, hD'get?]
have hltF' : ((res.keys.getLast hne : Key) : WithTop Key) <
resolve (dbw.insert k hkdb) r.end_ := by
rw [hre']
exact WithTop.coe_lt_coe.mpr (hFlast (F.head hFne) (List.head_mem hFne))
have hck' : (RangeRead.completeKeys (dbw.insert k hkdb) r).filter
(fun x : Key => decide (x ≤ res.keys.getLast hne)) = k :: res.keys := by
by_cases hneg : r.begin.anchor (dbw.insert k hkdb) < 0
· have hrb' : resolve (dbw.insert k hkdb) r.begin = (([] : Key) : WithTop Key) :=
resolve_eq_nil hneg
rw [completeKeys_filter_le_of_resolve_begin (db := dbw.insert k hkdb) hrev
(H := ([] : Key)) hrb' hltF']
rw [hins_keys, List.filter_cons_of_pos]
· rw [List.filter_append]
have hres_fil : res.keys.filter (fun x : Key => decide
(((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x ≤ res.keys.getLast hne)) = res.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact ⟨coe_nil_le_key_withTop _, (hsort.pairwise.imp le_of_lt).rel_getLast hx⟩
have hF_fil : F.filter (fun x : Key => decide
(((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x ≤ res.keys.getLast hne)) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx
simp only [Bool.not_eq_true, decide_eq_false_iff_not, not_and]
exact fun _ => not_le.mpr (hFlast x hx)
rw [hres_fil, hF_fil, List.append_nil]
· rw [decide_eq_true_eq]
exact ⟨coe_nil_le_key_withTop _, le_of_lt (lt_of_lt_of_le hk_head hhead_le_last)⟩
· have hzero : r.begin.anchor (dbw.insert k hkdb) = 0 := by omega
have hltlen : (r.begin.anchor (dbw.insert k hkdb)).toNat <
(dbw.insert k hkdb).keys.length := by
rw [hzero, hins_keys]; simp
have hins_ord : dbw.keys.orderedInsert (fun x1 x2 : Key => x1 ≤ x2) k =
k :: dbw.keys := by
rw [← DB.insert_keys (hk := hkdb)]
rw [hins_keys, hdbw_keys]
have hrb' : resolve (dbw.insert k hkdb) r.begin = ((k : Key) : WithTop Key) := by
rw [resolve_eq_ite, hzero]
simp [hins_ord]
rw [completeKeys_filter_le_of_resolve_begin (db := dbw.insert k hkdb) hrev
(H := k) hrb' hltF']
rw [hins_keys, List.filter_cons_of_pos]
· rw [List.filter_append]
have hres_fil : res.keys.filter (fun x : Key => decide
(((k : Key) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x ≤ res.keys.getLast hne)) = res.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact ⟨WithTop.coe_le_coe.mpr (le_trans (le_of_lt hk_head) (hhead_le x hx)),
(hsort.pairwise.imp le_of_lt).rel_getLast hx⟩
have hF_fil : F.filter (fun x : Key => decide
(((k : Key) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x ≤ res.keys.getLast hne)) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx
simp only [Bool.not_eq_true, decide_eq_false_iff_not, not_and]
exact fun _ => not_le.mpr (hFlast x hx)
rw [hres_fil, hF_fil, List.append_nil]
· rw [decide_eq_true_eq]
exact ⟨le_rfl, le_of_lt (lt_of_lt_of_le hk_head hhead_le_last)⟩
have hnot : ¬ RangeRead.Compatible (dbw.insert k hkdb) r res := by
intro hc
have heq := ((compatible_iff_truncated_keys hrev hmore hne).mp hc).2
rw [hck'] at heq
have hlen := congrArg List.length heq
rw [List.length_cons] at hlen
omega
exact ⟨dbw, hkdb, hcompw, hnot⟩
/-- At or above `begin.key`, erasing the target from the padded witness drops the end
resolution onto the reported last, so the complete window loses its last key. -/
theorem exists_witness_above_begin_of_negCross_trunc_strict_top {r : RangeRead} {res : Result}
{k : Key}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = true)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0)
(hend : r.end_.offset ≤ 0)
(htop : r.end_.key = (⊤ : WithTop Key))
(hBltTop : r.begin.key < (⊤ : WithTop Key))
(hclamp : reportedBelowBegin r res ≤ beginSlack r)
(hallB : ∀ x ∈ res.keys, ((x : Key) : WithTop Key) < r.begin.key)
(hkB : r.begin.key ≤ ((k : Key) : WithTop Key)) :
∃ dbw : DB, k ∈ dbw.keys ∧ RangeRead.Compatible dbw r res ∧
¬ RangeRead.Compatible (dbw.erase k) r res := by
classical
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hle_last : ∀ x ∈ res.keys, x ≤ res.keys.getLast hne :=
fun x hx => (hsort.pairwise.imp le_of_lt).rel_getLast hx
set m : ℕ := (1 - r.end_.offset).toNat with hm
have hm1 : 1 ≤ m := by rw [hm]; omega
have hcard : ((m - 1 + 1 : ℕ) : ℕ∞) ≤ intervalCard r.begin.key (⊤ : WithTop Key) := by
rw [Nat.sub_add_cancel hm1, intervalCard_top_right (ne_of_lt hBltTop)]
exact le_top
obtain ⟨dba, hdbaIn, hknot, hdbaLen⟩ :=
exists_db_keysIn_avoid (B := r.begin.key) (E := (⊤ : WithTop Key)) (k := k) (m := m - 1)
hcard
have hrawNodup : (k :: dba.keys).Nodup := List.nodup_cons.mpr ⟨hknot, dba.nodup⟩
set F : List Key := (k :: dba.keys).insertionSort (· ≤ ·) with hF
have hFperm : (k :: dba.keys).Perm F := (List.perm_insertionSort (· ≤ ·) _).symm
have hFsorted : F.SortedLT := by
rw [hF, List.sortedLT_iff_pairwise]
exact DB.pairwise_lt_of_le_of_nodup
(List.pairwise_insertionSort (r := (· ≤ ·)) (k :: dba.keys))
(hFperm.nodup_iff.mp hrawNodup)
have hFlen : F.length = m := by
rw [hF, List.length_insertionSort, List.length_cons, hdbaLen]; omega
have hFk : k ∈ F := hFperm.mem_iff.mp (List.mem_cons_self ..)
have hFge : ∀ x ∈ F, r.begin.key ≤ ((x : Key) : WithTop Key) := by
intro x hx
have hx' := hFperm.mem_iff.mpr hx
rcases List.mem_cons.mp hx' with rfl | hx''
· exact hkB
· exact (hdbaIn x hx'').1
have hlast_lt_B : ((res.keys.getLast hne : Key) : WithTop Key) < r.begin.key :=
hallB _ (List.getLast_mem hne)
have hFlast : ∀ x ∈ F, res.keys.getLast hne < x := by
intro x hx
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le hlast_lt_B (hFge x hx))
have hFne : F ≠ [] := by
intro h; rw [h] at hFlen; simp at hFlen; omega
obtain ⟨dbw, hdbw_keys, hcompw, _hrb, _hre⟩ :=
compat_of_pad_top ⟨db₀, hcomp₀⟩ hne hrev hmore hbegin hend htop hclamp hallB hFsorted hFlen
hm hFne hFge hFlast
have hlast_lt_k : res.keys.getLast hne < k := by
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le hlast_lt_B hkB)
have hk_not_res : k ∉ res.keys := fun hx => absurd (hle_last k hx) (not_le.mpr hlast_lt_k)
have hD' : (dbw.erase k).keys = res.keys ++ F.erase k := by
rw [DB.erase_keys, hdbw_keys]
exact List.erase_append_right F hk_not_res
have hF'ge : ∀ x ∈ F.erase k, r.begin.key ≤ ((x : Key) : WithTop Key) :=
fun x hx => hFge x (List.mem_of_mem_erase hx)
have hF'zero : (F.erase k).countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
simp only [decide_eq_true_eq]
exact not_lt.mpr (hF'ge x hx)
have hcnt' : (dbw.erase k).keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res := by
rw [hD', List.countP_append]
have h1 : res.keys.countP
(fun x : Key => decide (((x : Key) : WithTop Key) < r.begin.key)) =
reportedBelowBegin r res := rfl
rw [h1, hF'zero, Nat.add_zero]
have hanchor' : r.begin.anchor (dbw.erase k) < 0 := by
rw [anchor_eq_count_sub_slack (dbw.erase k) r (le_of_lt hbegin), hcnt']
have hle : (reportedBelowBegin r res : ℤ) ≤ (beginSlack r : ℤ) := by exact_mod_cast hclamp
omega
have hrb' : resolve (dbw.erase k) r.begin = (([] : Key) : WithTop Key) := resolve_eq_nil hanchor'
have hlenD' : (dbw.erase k).keys.length = res.keys.length + m - 1 := by
rw [hD', List.length_append, List.length_erase_of_mem hFk, hFlen]
omega
have hm_int : (m : Int) = 1 - r.end_.offset := by
rw [hm]; exact Int.toNat_of_nonneg (by omega)
have hanchor_end' : r.end_.anchor (dbw.erase k) = (res.keys.length : Int) - 1 := by
rw [anchor_of_top (s := r.end_) htop, hlenD']
rw [Nat.cast_sub (by omega : 1 ≤ res.keys.length + m)]
push_cast
rw [hm_int]; ring
have ht1 : 1 ≤ res.keys.length := List.length_pos_of_ne_nil hne
have hEqInt : (res.keys.length : Int) - 1 = ((res.keys.length - 1 : ℕ) : Int) := by
rw [Nat.cast_sub ht1]; norm_num
have htoNat' : (r.end_.anchor (dbw.erase k)).toNat = res.keys.length - 1 := by
rw [hanchor_end', hEqInt, Int.toNat_natCast]
have hD'get? : (dbw.erase k).keys[res.keys.length - 1]? =
some (res.keys.getLast hne) := by
rw [hD', List.getElem?_append]
rw [ite_eq_left (by omega : res.keys.length - 1 < res.keys.length)]
rw [List.getElem?_eq_getElem (by omega : res.keys.length - 1 < res.keys.length)]
congr 1
rw [List.getLast_eq_getElem hne]
have hre' : resolve (dbw.erase k) r.end_ = ((res.keys.getLast hne : Key) : WithTop Key) := by
rw [resolve, ite_eq_right (by rw [hanchor_end']; omega)]
rw [hanchor_end', hEqInt, Int.toNat_natCast, hD'get?]
have hckE : RangeRead.completeKeys (dbw.erase k) r = res.keys.dropLast := by
unfold RangeRead.completeKeys RangeRead.inRange
rw [ite_eq_right (by simp [hrev]), hrb', hre']
have hpred : ∀ x ∈ (dbw.erase k).keys,
decide (((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
((x : Key) : WithTop Key) < (((res.keys.getLast hne) : Key) : WithTop Key)) =
decide (((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x < res.keys.getLast hne) := by
intro x _
rw [decide_eq_decide]
exact and_congr_right fun _ => WithTop.coe_lt_coe
rw [List.filter_congr hpred, hD', List.filter_append]
conv_lhs => arg 1; arg 2; rw [← List.dropLast_append_getLast hne]
rw [List.filter_append]
have hfil : res.keys.dropLast.filter (fun x : Key => decide
(((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x < res.keys.getLast hne)) = res.keys.dropLast := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact ⟨coe_nil_le_key_withTop _, by
have h := hsort.pairwise.rel_dropLast_getLast hx
simpa using h⟩
rw [hfil]
have hFnil : (F.erase k).filter (fun x : Key => decide
(((([] : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
x < res.keys.getLast hne)) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx
simp only [Bool.not_eq_true, decide_eq_false_iff_not, not_and]
exact fun _ => not_lt.mpr (le_of_lt (hFlast x (List.mem_of_mem_erase hx)))
rw [hFnil, List.append_nil]
simp
have hnot : ¬ RangeRead.Compatible (dbw.erase k) r res := by
rw [compatible_iff_truncated_keys hrev hmore hne]
intro h
have heq := h.2
rw [hckE] at heq
have hfil : res.keys.dropLast.filter
(fun x : Key => decide (x ≤ res.keys.getLast hne)) = res.keys.dropLast := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact le_of_lt (hsort.pairwise.rel_dropLast_getLast hx)
rw [hfil] at heq
have hlen := congrArg List.length heq
rw [List.length_dropLast] at hlen
omega
exact ⟨dbw, by rw [hdbw_keys]; exact List.mem_append.mpr (Or.inr hFk), hcompw, hnot⟩
/-- The sentinel-end strict cell is minimal with the full range `[⊥, ⊤)`. -/
theorem minimal_fullRange_of_negCross_trunc_strict_top {r : RangeRead} {res : Result}
(hread : Readable r res) (h : negCrossTruncStrictTop r res) :
Minimal r res ⟨(([] : Key) : WithTop Key), (⊤ : WithTop Key)⟩ := by
obtain ⟨hmore, hrev, hbegin, hne, _hcrossD, hend, hclamp, htop, hlastD, hBltE⟩ := h
have hreadP : Readable r res := hread
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hlastD' : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hlastB : ((res.keys.getLast hne : Key) : WithTop Key) < r.begin.key := by
rw [← hlastD']; exact hlastD
have hBltTop : r.begin.key < (⊤ : WithTop Key) := by
rw [← htop]; exact hBltE
have hallB : ∀ x ∈ res.keys, ((x : Key) : WithTop Key) < r.begin.key := by
intro x hx
exact lt_of_le_of_lt
(WithTop.coe_le_coe.mpr ((hsort.pairwise.imp le_of_lt).rel_getLast hx)) hlastB
have hbExists : ∃ b : Key, r.begin.key = ((b : Key) : WithTop Key) := by
obtain ⟨b, hb⟩ := WithTop.ne_top_iff_exists.mp (ne_of_lt hBltTop)
exact ⟨b, hb.symm⟩
obtain ⟨b, hb⟩ := hbExists
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)
· obtain ⟨dbw, hkdb, hcomp, hnot⟩ :=
exists_witness_below_head_of_negCross_trunc_strict_top hreadP hrev hmore hne hbegin hend
htop hBltTop hclamp hallB hkhead
exact necessary_of_toggle ⟨dbw, hcomp, by
rw [toggle_eq_insert_of_not_mem hkdb]; exact hnot⟩
· 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 hreadP (List.head_mem hne) (List.getLast_mem hne)
hhead_le hklast
· have hlast_lt_k : res.keys.getLast hne < k := lt_of_not_ge hklast
by_cases hkB : ((k : Key) : WithTop Key) < r.begin.key
· have hlast_nec : Necessary r res (res.keys.getLast hne) :=
necessary_of_mem_result hreadP (List.getLast_mem hne)
have hB_nec : Necessary r res b := by
obtain ⟨dbw, hkdb, hcomp, hnot⟩ :=
exists_witness_above_begin_of_negCross_trunc_strict_top hreadP hrev hmore hne hbegin
hend htop hBltTop hclamp hallB (by rw [hb])
exact necessary_of_toggle ⟨dbw, hcomp, by
rw [toggle_eq_erase_of_mem hkdb]; exact hnot⟩
have hk_le_b : k ≤ b := by
rw [hb] at hkB
exact le_of_lt (WithTop.coe_lt_coe.mp hkB)
exact Necessary.of_between hlast_nec hB_nec (le_of_lt hlast_lt_k) hk_le_b
· have hkge : r.begin.key ≤ ((k : Key) : WithTop Key) := le_of_not_gt hkB
obtain ⟨dbw, hkdb, hcomp, hnot⟩ :=
exists_witness_above_begin_of_negCross_trunc_strict_top hreadP hrev hmore hne hbegin
hend htop hBltTop hclamp hallB hkge
exact necessary_of_toggle ⟨dbw, hcomp, by
rw [toggle_eq_erase_of_mem hkdb]; exact hnot⟩
/-- The compact closed form for the sentinel-end strict cell. -/
noncomputable def closedFormNegCrossTruncStrictTop (_r : RangeRead) (_res : Result) :
ConflictRange :=
⟨(([] : Key) : WithTop Key), (⊤ : WithTop Key)⟩
/-- The compact sentinel-end strict closed form is minimal. -/
theorem minimal_closedForm_of_negCross_trunc_strict_top {r : RangeRead} {res : Result}
(hread : Readable r res) (h : negCrossTruncStrictTop r res) :
Minimal r res (closedFormNegCrossTruncStrictTop r res) :=
minimal_fullRange_of_negCross_trunc_strict_top hread h
end FormalConflictRange