Files

1052 lines
53 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.NegCrossTruncClamp
/-!
# Arbitrary-end high-capacity clamping gaps
This module extends the positive-end clamping certificates to end keys inside the reported
window. When the gap above the reported last has room for the target in addition to a full
begin slack of other keys, the reported keys and those other gap keys form a compatible
database. Inserting the target lifts the begin resolution strictly above the reported
head, so the target is necessary regardless of the end key.
-/
namespace FormalConflictRange
/-- Split the half-open interval above a key at its immediate successor. -/
theorem intervalCard_last_eq_keyAfter_add_one {last : Key} {B : WithTop Key}
(hgap : (((keyAfter last : Key)) : WithTop Key) < B) :
intervalCard ((last : Key) : WithTop Key) B =
intervalCard (((keyAfter last : Key)) : WithTop Key) B + 1 := by
have hcard_one : intervalCard ((last : Key) : WithTop Key)
(((keyAfter last : Key)) : WithTop Key) = 1 := by
have h := intervalCard_succChain last 1
simpa [keyAfter, List.replicate_one] using h
rw [intervalCard_add (b := ((last : Key) : WithTop Key))
(m := (((keyAfter last : Key)) : WithTop Key)) (e := B)
(le_of_lt (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last))) (le_of_lt hgap),
hcard_one, add_comm]
/-- **Insertion necessity in a high-capacity gap, at an arbitrary positive end key.**
Write `T = beginSlack + 1 - #reported`. If the interval
`[keyAfter last, begin.key)` has room for `T` keys avoiding the target, then the reported
keys together with those `T` keys are compatible. Inserting the target moves the negative
begin selector past the reported head, which makes the result incompatible. -/
theorem necessary_gap_insert_of_capacity {r : RangeRead} {res : Result} {k : Key}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0) (hendoff : 1 ≤ r.end_.offset)
(hcrossD : ((leastReported r res : Key) : WithTop Key) < r.begin.key)
(hgap : (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) <
r.begin.key)
(hclamp : reportedBelowBegin r res ≤ beginSlack r)
(hcap : (((beginSlack r + 1 - res.keys.length) + 1 : ℕ) : ℕ∞) ≤
intervalCard (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key)
r.begin.key)
(hkgt : res.keys.getLastD ([] : Key) < k)
(hkB : ((k : Key) : WithTop Key) < r.begin.key) :
Necessary r res k := by
obtain ⟨db₀, hcomp₀⟩ := hread
have hread' : Readable r res := ⟨db₀, hcomp₀⟩
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hlim : r.withinLimit res.keys := hcomp₀.1
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
set t : ℕ := res.keys.length with ht
set q : ℕ := beginSlack r with hq
set T : ℕ := q + 1 - t with hT
have hheadD : res.keys.headD ([] : Key) = head := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
have hlastD : res.keys.getLastD ([] : Key) = last := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hgap' : (((keyAfter last : Key)) : WithTop Key) < r.begin.key := by
rw [← hlastD]; exact hgap
have hlastB : ((last : Key) : WithTop Key) < r.begin.key :=
lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) hgap'
have hkgt' : last < k := by rw [← hlastD]; exact hkgt
have hhead_le : ∀ x ∈ res.keys, head ≤ x := by
intro x hx
rw [hhead]
exact (hsort.pairwise.imp le_of_lt).rel_head hx
have hlast_le : ∀ x ∈ res.keys, x ≤ last := by
intro x hx
rw [hlast]
exact (hsort.pairwise.imp le_of_lt).rel_getLast hx
have hres_lt_B : ∀ 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 (hlast_le x hx)) hlastB
have hreported : reportedBelowBegin r res = t := by
unfold reportedBelowBegin
rw [List.countP_eq_length]
intro x hx
rw [decide_eq_true_eq]
exact hres_lt_B x hx
have htq : t ≤ q := by rw [← hreported, hq]; exact hclamp
have hTpos : 1 ≤ T := by rw [hT]; omega
have hcross : ((head : Key) : WithTop Key) < r.begin.key := by
have hcd := hcrossD
simp only [leastReported, hrev] at hcd
rwa [hheadD] at hcd
have hcnt : (res.keys.filter
(fun x : Key => decide (r.end_.key ≤ (x : WithTop Key)))).length ≤
(r.end_.offset - 1).toNat := by
simpa only [List.countP_eq_length_filter] using
reported_count_ge_le_end_offset hread' hmore hne hendoff
have hcap' : (((T + 1 : ℕ)) : ℕ∞) ≤
intervalCard (((keyAfter last : Key)) : WithTop Key) r.begin.key := by
rw [hlastD] at hcap
simpa only [hT, hq, ht] using hcap
obtain ⟨dbJ, hJmem, hJavoid, hJlen⟩ := exists_db_keysIn_avoid
(B := (((keyAfter last : Key)) : WithTop Key)) (E := r.begin.key) (k := k)
(m := T) hcap'
have hJgt_last : ∀ x ∈ dbJ.keys, last < x := by
intro x hx
have h1 := (hJmem x hx).1
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le
(WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) h1)
have hJlt_B : ∀ x ∈ dbJ.keys, ((x : Key) : WithTop Key) < r.begin.key :=
fun x hx => (hJmem x hx).2
have hres_lt_J : ∀ x ∈ res.keys, ∀ y ∈ dbJ.keys, x < y := by
intro x hx y hy
exact lt_of_le_of_lt (hlast_le x hx) (hJgt_last y hy)
have hsorted : (res.keys ++ dbJ.keys).SortedLT :=
List.sortedLT_append.mpr ⟨hsort, dbJ.sorted, hres_lt_J⟩
let dbw : DB := ⟨res.keys ++ dbJ.keys, hsorted⟩
have hcompw : RangeRead.Compatible dbw r res :=
compatible_of_append_gapKeys_high hrev hmore hne hbegin hendoff hlim htq hcnt hgap
hsort dbJ.sorted
(by intro x hx; rw [hlastD]; exact hJmem x hx)
(by rw [hJlen, hT, hq, ht]) rfl
have hk_le_keyAfter : keyAfter last ≤ k := by
by_contra hcon
rw [not_le] at hcon
exact absurd ((lt_keyAfter_iff k last).mp hcon) (not_le.mpr hkgt')
have hknot_res : k ∉ res.keys := by
intro hk
exact absurd (hlast_le k hk) (not_le.mpr hkgt')
have hknot : k ∉ dbw.keys := by
intro hk
change k ∈ res.keys ++ dbJ.keys at hk
rcases List.mem_append.mp hk with hk | hk
· exact hknot_res hk
· exact hJavoid hk
have hhead_mem : head ∈ dbw.keys := by
change head ∈ res.keys ++ dbJ.keys
exact List.mem_append_left _ (by rw [hhead]; exact List.head_mem hne)
have hk_gt_head : head < k := lt_of_le_of_lt (hhead_le last (by
rw [hlast]; exact List.getLast_mem hne)) hkgt'
have hlen : (dbw.keys.filter (fun x : Key => decide (((head : Key) : WithTop Key) ≤
((x : Key) : WithTop Key) ∧ ((x : Key) : WithTop Key) < r.begin.key))).length =
beginSlack r + 1 := by
have hf : dbw.keys.filter (fun x : Key => decide (((head : Key) : WithTop Key) ≤
((x : Key) : WithTop Key) ∧ ((x : Key) : WithTop Key) < r.begin.key)) =
dbw.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
change x ∈ res.keys ++ dbJ.keys at hx
rcases List.mem_append.mp hx with hx | hx
· exact ⟨WithTop.coe_le_coe.mpr (hhead_le x hx), hres_lt_B x hx⟩
· exact ⟨WithTop.coe_le_coe.mpr (le_trans (hhead_le last (by
rw [hlast]; exact List.getLast_mem hne)) (le_of_lt (hJgt_last x hx))),
hJlt_B x hx⟩
rw [hf]
change (res.keys ++ dbJ.keys).length = beginSlack r + 1
rw [List.length_append, hJlen, ← ht, ← hq]
omega
apply necessary_of_toggle
refine ⟨dbw, hcompw, ?_⟩
rw [toggle_eq_insert_of_not_mem hknot]
intro hcins
have hhead_ck : head ∈ RangeRead.completeKeys (dbw.insert k hknot) r :=
(RangeRead.compatible_keys_prefix hcins).subset (by rw [hhead]; exact List.head_mem hne)
have hle := (RangeRead.mem_completeKeys.mp hhead_ck).2.1
exact (not_lt.mpr hle) (resolve_begin_insert_gt hbegin hhead_mem hcross hknot
hk_gt_head hkB hlen)
/-- **A saturated empty-key end window excludes padding below the reported head.**
If `end_.key = ⊥` and `(end_.offset - 1).toNat` is exactly the number of reported keys,
then a compatible forward truncated read has no stored key strictly below its reported
head. Such a key and all reported keys would lie at or below the reported last, exceeding
the end-count bound forced by `last < resolve end_`. -/
theorem not_lt_head_of_mem_of_compatible_saturated {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false)
(_hmore : res.more = true) (hne : res.keys ≠ []) (hendoff : 1 ≤ r.end_.offset)
(hE : r.end_.key = (([] : Key) : WithTop Key))
(hsat : (r.end_.offset - 1).toNat = res.keys.length)
{x : Key} (hxdb : x ∈ db.keys) (hxhead : x < res.keys.head hne) : False := by
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp hrev
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
have hhead_le : ∀ y ∈ res.keys, head ≤ y := by
intro y hy
rw [hhead]
exact (hsort.pairwise.imp le_of_lt).rel_head hy
have hlast_le : ∀ y ∈ res.keys, y ≤ last := by
intro y hy
rw [hlast]
exact (hsort.pairwise.imp le_of_lt).rel_getLast hy
have hxhead' : x < head := by rwa [hhead]
have hxnot : x ∉ res.keys := by
intro hx
exact (not_lt.mpr (hhead_le x hx)) hxhead'
have hxlast : x ≤ last := by
exact le_of_lt (lt_of_lt_of_le hxhead' (hhead_le last (by
rw [hlast]; exact List.getLast_mem hne)))
have hlast_ck : last ∈ RangeRead.completeKeys db r :=
(RangeRead.compatible_keys_prefix hcomp).subset (by
rw [hlast]; exact List.getLast_mem hne)
have hlastE : ((last : Key) : WithTop Key) < resolve db r.end_ :=
(RangeRead.mem_completeKeys.mp hlast_ck).2.2
have hcnt := filter_length_le_offset_of_resolve_end_gt (db := db) hendoff hlastE
have hfilterE : (db.keys.filter
(fun y : Key => decide (r.end_.key ≤ (y : WithTop Key)))).filter
(fun y : Key => decide (y ≤ last)) = db.keys.filter (fun y : Key => decide (y ≤ last)) := by
have hinner : db.keys.filter
(fun y : Key => decide (r.end_.key ≤ (y : WithTop Key))) = db.keys := by
rw [List.filter_eq_self]
intro y hy
rw [decide_eq_true_eq, hE]
exact coe_nil_le_key_withTop _
rw [hinner]
rw [hfilterE, hsat] at hcnt
have hnodup : (x :: res.keys).Nodup := List.nodup_cons.mpr ⟨hxnot, hsort.nodup⟩
have hsubset : (x :: res.keys) ⊆ db.keys.filter (fun y : Key => decide (y ≤ last)) := by
intro y hy
rw [List.mem_filter, decide_eq_true_eq]
rcases List.mem_cons.mp hy with rfl | hy
· exact ⟨hxdb, hxlast⟩
· exact ⟨RangeRead.compatible_keys_subset hcomp hy, hlast_le y hy⟩
have hlen := hnodup.length_le_of_subset hsubset
rw [List.length_cons] at hlen
omega
/-- If no stored key lies below the reported head, compatibility forces the stored keys
below `keyAfter last` to be exactly the reported list. -/
theorem cnt_keyAfter_getLast_eq_length_of_no_lt_head {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false)
(hmore : res.more = true) (hne : res.keys ≠ [])
(hno : ∀ x ∈ db.keys, ¬ x < res.keys.head hne) :
cnt db (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) = res.keys.length := by
have hhead_ck : res.keys.head hne ∈ RangeRead.completeKeys db r :=
(RangeRead.compatible_keys_prefix hcomp).subset (List.head_mem hne)
have hlast_ck : res.keys.getLast hne ∈ RangeRead.completeKeys db r :=
(RangeRead.compatible_keys_prefix hcomp).subset (List.getLast_mem hne)
have hrb := (RangeRead.mem_completeKeys.mp hhead_ck).2.1
have hlastE := (RangeRead.mem_completeKeys.mp hlast_ck).2.2
have hfil := ((compatible_iff_truncated_keys hrev hmore hne).mp hcomp).2
rw [cnt, List.countP_eq_length_filter]
have hl : db.keys.filter (fun k : Key => decide (((k : Key) : WithTop Key) <
(((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key))) =
(RangeRead.completeKeys db r).filter
(fun k : Key => decide (k ≤ res.keys.getLast hne)) := by
apply eq_of_forall_mem_iff_of_pairwise
· exact db.sorted.pairwise.filter _
· have hcp := RangeRead.completeKeys_pairwise (db := db) (r := r)
rw [hrev] at hcp
exact hcp.sublist List.filter_sublist
· intro k
simp only [List.mem_filter, decide_eq_true_eq]
constructor
· rintro ⟨hkdb, hkK⟩
have hkle : k ≤ res.keys.getLast hne :=
(lt_keyAfter_iff k (res.keys.getLast hne)).mp (WithTop.coe_lt_coe.mp hkK)
have hkhead : res.keys.head hne ≤ k := le_of_not_gt (hno k hkdb)
have hkrb : resolve db r.begin ≤ ((k : Key) : WithTop Key) :=
le_trans hrb (WithTop.coe_le_coe.mpr hkhead)
have hkre : ((k : Key) : WithTop Key) < resolve db r.end_ :=
lt_of_le_of_lt (WithTop.coe_le_coe.mpr hkle) hlastE
exact ⟨RangeRead.mem_completeKeys.mpr ⟨hkdb, hkrb, hkre⟩, hkle⟩
· rintro ⟨hkck, hkle⟩
exact ⟨(RangeRead.mem_completeKeys.mp hkck).1, WithTop.coe_lt_coe.mpr
((lt_keyAfter_iff k (res.keys.getLast hne)).mpr hkle)⟩
rw [hl, hfil]
/-- A nonpositive begin anchor resolves at or below the least stored key. -/
theorem resolve_begin_le_of_anchor_nonpos_of_no_lt_head {db : DB} {r : RangeRead} {head : Key}
(hhead : head ∈ db.keys) (hno : ∀ x ∈ db.keys, ¬ x < head)
(hanchor : r.begin.anchor db ≤ 0) :
resolve db r.begin ≤ ((head : Key) : WithTop Key) := by
rcases lt_or_eq_of_le hanchor with hneg | heq
· rw [resolve_eq_nil hneg]
exact coe_nil_le_key_withTop _
· have h0 : 0 ≤ r.begin.anchor db := le_of_eq heq.symm
have hlt : (r.begin.anchor db).toNat < db.keys.length := by
rw [heq]
simpa using List.length_pos_of_mem hhead
rw [resolve_eq_getElem h0 hlt]
have hmin : ∀ x ∈ db.keys, head ≤ x := fun x hx => le_of_not_gt (hno x hx)
have hget : db.keys[(r.begin.anchor db).toNat] = head := by
have hidx : (r.begin.anchor db).toNat = 0 := by rw [heq]; rfl
have hcount : db.keys.countP (fun x : Key => decide (x < head)) = 0 :=
countP_lt_eq_zero_of_forall_ge hmin
simpa only [hidx, hcount] using getElem_countP_lt db.sorted hhead
rw [hget]
/-- When there are no stored keys below `head`, two forward reads whose begin resolutions
are at or below `head` have the same complete window. -/
theorem completeKeys_noGapRead_eq_of_no_lt_head {db : DB} {r : RangeRead} {res : Result}
{head : Key} (hrev : r.reverse = false) (hno : ∀ x ∈ db.keys, ¬ x < head)
(hbr : resolve db r.begin ≤ ((head : Key) : WithTop Key))
(hbng : resolve db (noGapRead r res).begin ≤ ((head : Key) : WithTop Key)) :
RangeRead.completeKeys db r = RangeRead.completeKeys db (noGapRead r res) := by
unfold RangeRead.completeKeys RangeRead.inRange
simp only [noGapRead, List.getLastD_eq_getLast?] at hbng ⊢
simp only [hrev, Bool.false_eq_true, ite_false]
apply List.filter_congr
intro k hk
have hhead : ((head : Key) : WithTop Key) ≤ ((k : Key) : WithTop Key) :=
WithTop.coe_le_coe.mpr (le_of_not_gt (hno k hk))
have h1 := le_trans hbr hhead
have h2 := le_trans hbng hhead
simp [h1, h2]
/-- A database consisting of the empty key, the reported keys, and `T` gap keys is
compatible whenever its begin selector resolves to the reported head and its reported
end-filter count fits. Unlike `compatible_of_nil_cons_gapKeys_high`, the end key is
arbitrary; the explicit count hypothesis replaces `last < end.key`. -/
theorem compatible_of_nil_cons_gapKeys_high_of_end_count {r : RangeRead} {res : Result}
{db : DB} {J : List Key}
(hrev : r.reverse = false) (hmore : res.more = true) (hne : res.keys ≠ [])
(hbegin : r.begin.offset < 0) (hendoff : 1 ≤ r.end_.offset)
(hlim : r.withinLimit res.keys)
(htq : res.keys.length ≤ beginSlack r)
(hheadne : res.keys.headD ([] : Key) ≠ ([] : Key))
(hgap : (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) <
r.begin.key)
(hsort : res.keys.SortedLT) (_hJ : J.SortedLT)
(hJrange : ∀ x ∈ J, (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) ≤
((x : Key) : WithTop Key) ∧ ((x : Key) : WithTop Key) < r.begin.key)
(hJlen : J.length = beginSlack r + 1 - res.keys.length)
(hkeys : db.keys = ([] : Key) :: (res.keys ++ J))
(hcnt : ((db.keys.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ res.keys.getLast hne))).length ≤
(r.end_.offset - 1).toNat) :
RangeRead.Compatible db r res := by
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
set t : ℕ := res.keys.length with ht
set q : ℕ := beginSlack r with hq
set T : ℕ := q + 1 - t with hT
have hlastD : res.keys.getLastD ([] : Key) = last := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hheadD : res.keys.headD ([] : Key) = head := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
have hheadne' : head ≠ ([] : Key) := by rw [← hheadD]; exact hheadne
have hJlen' : J.length = T := by omega
have hlast_le : ∀ x ∈ res.keys, x ≤ last := by
intro x hx
rw [hlast]
exact (hsort.pairwise.imp le_of_lt).rel_getLast hx
have hhead_le : ∀ x ∈ res.keys, head ≤ x := by
intro x hx
rw [hhead]
exact (hsort.pairwise.imp le_of_lt).rel_head hx
have hJgt_last : ∀ x ∈ J, last < x := by
intro x hx
have h := (hJrange x hx).1
rw [hlastD] at h
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le
(WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) h)
have hJlt_B : ∀ x ∈ J, ((x : Key) : WithTop Key) < r.begin.key :=
fun x hx => (hJrange x hx).2
have hlastB : ((last : Key) : WithTop Key) < r.begin.key := by
exact lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last))
(by rw [← hlastD]; exact hgap)
have hcross : ((head : Key) : WithTop Key) < r.begin.key :=
lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hhead_le last (by
rw [hlast]; exact List.getLast_mem hne))) hlastB
have hnil_lt_head : ([] : Key) < head :=
lt_of_le_of_ne (nil_le_key head) (Ne.symm hheadne')
have hhead_mem : head ∈ db.keys := by
rw [hkeys]
exact List.mem_cons_of_mem _ (List.mem_append_left _ (by
rw [hhead]; exact List.head_mem hne))
have hfilterB : db.keys.filter (fun k : Key => decide (((head : Key) : WithTop Key) ≤
((k : Key) : WithTop Key) ∧ ((k : Key) : WithTop Key) < r.begin.key)) =
res.keys ++ J := by
rw [hkeys, List.filter_cons]
have hnil : ¬ (((head : Key) : WithTop Key) ≤ ((([] : Key) : WithTop Key)) ∧
((([] : Key) : WithTop Key)) < r.begin.key) := by
intro h
exact (not_le.mpr (WithTop.coe_lt_coe.mpr hnil_lt_head)) h.1
rw [ite_eq_right (by simpa only [decide_eq_true_eq] using hnil)]
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
rcases List.mem_append.mp hx with hx | hx
· exact ⟨WithTop.coe_le_coe.mpr (hhead_le x hx),
lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hlast_le x hx)) hlastB⟩
· exact ⟨WithTop.coe_le_coe.mpr (le_trans (hhead_le last (by
rw [hlast]; exact List.getLast_mem hne)) (le_of_lt (hJgt_last x hx))),
hJlt_B x hx⟩
have hlenB : (db.keys.filter (fun k : Key => decide (((head : Key) : WithTop Key) ≤
((k : Key) : WithTop Key) ∧ ((k : Key) : WithTop Key) < r.begin.key))).length =
beginSlack r + 1 := by
rw [hfilterB, List.length_append, hJlen, ← ht, ← hq]
omega
have hresB : resolve db r.begin = ((head : Key) : WithTop Key) :=
resolve_begin_eq_head_of_filter_len hbegin hhead_mem hcross hlenB
have hresE : ((last : Key) : WithTop Key) < resolve db r.end_ := by
apply resolve_end_gt_of_filter_length_le (db := db) hendoff
exact hcnt
have hck : RangeRead.completeKeys db r =
db.keys.filter (fun k : Key => decide (head ≤ k) && decide
(((k : Key) : WithTop Key) < resolve db r.end_)) := by
unfold RangeRead.completeKeys RangeRead.inRange
rw [hrev, ite_eq_right (by simp), hresB]
simp [WithTop.coe_le_coe]
have hfil : (RangeRead.completeKeys db r).filter (fun k : Key => decide (k ≤ last)) =
res.keys := by
rw [hck, hkeys, List.filter_filter, List.filter_cons, List.filter_append]
have hnil_pred : ¬ (decide ((([] : Key)) ≤ last) && (decide (head ≤ (([] : Key))) &&
decide ((([] : Key) : WithTop Key) < resolve db r.end_))) = true := by
intro hcon
rw [Bool.and_eq_true, Bool.and_eq_true] at hcon
exact (not_le.mpr hnil_lt_head) (of_decide_eq_true hcon.2.1)
rw [ite_eq_right hnil_pred]
have h1 : res.keys.filter (fun k : Key => decide (k ≤ last) && (decide (head ≤ k) &&
decide (((k : Key) : WithTop Key) < resolve db r.end_))) = res.keys := by
rw [List.filter_eq_self]
intro k hk
rw [Bool.and_eq_true, Bool.and_eq_true, decide_eq_true_eq, decide_eq_true_eq,
decide_eq_true_eq]
exact ⟨hlast_le k hk, hhead_le k hk,
lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hlast_le k hk)) hresE⟩
have h2 : J.filter (fun k : Key => decide (k ≤ last) && (decide (head ≤ k) &&
decide (((k : Key) : WithTop Key) < resolve db r.end_))) = [] := by
rw [List.filter_eq_nil_iff]
intro k hk hcon
rw [Bool.and_eq_true] at hcon
exact absurd (of_decide_eq_true hcon.1) (not_le.mpr (hJgt_last k hk))
rw [h1, h2, List.append_nil]
rw [compatible_iff_truncated_keys (db := db) hrev hmore hne]
exact ⟨hlim, hfil⟩
/-- The empty key can be padded to the reported keys and gap keys without exceeding the
end-count bound, unless the end selector is the saturated empty-key window. Away from
`end_.key = ⊥`, the empty key is invisible to the end filter. At `end_.key = ⊥`, an
unsaturated window has room for it in addition to all the reported keys. -/
theorem end_count_nil_cons_gapKeys_of_unsaturated {r : RangeRead} {res : Result}
{db : DB} {J : List Key} (hread : Readable r res)
(hrev : r.reverse = false) (hmore : res.more = true) (hne : res.keys ≠ [])
(hendoff : 1 ≤ r.end_.offset)
(hunsat : r.end_.key ≠ (([] : Key) : WithTop Key) ∨
(r.end_.offset - 1).toNat ≠ res.keys.length)
(hkeys : db.keys = ([] : Key) :: (res.keys ++ J))
(hJgt : ∀ x ∈ J, res.keys.getLast hne < x) :
((db.keys.filter (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ res.keys.getLast hne))).length ≤
(r.end_.offset - 1).toNat := by
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
set last : Key := res.keys.getLast hne with hlast
have hlast_le : ∀ x ∈ res.keys, x ≤ last := by
intro x hx
rw [hlast]
exact (hsort.pairwise.imp le_of_lt).rel_getLast hx
have hbase : (res.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).length ≤
(r.end_.offset - 1).toNat := by
simpa only [List.countP_eq_length_filter] using
reported_count_ge_le_end_offset ⟨db₀, hcomp₀⟩ hmore hne hendoff
have hlast_filter : db.keys.filter (fun k : Key => decide (k ≤ last)) =
([] : Key) :: res.keys := by
rw [hkeys, List.filter_cons, List.filter_append]
have hnil : decide (([] : Key) ≤ last) = true := by simp [nil_le_key]
rw [ite_eq_left hnil]
have h1 : res.keys.filter (fun k : Key => decide (k ≤ last)) = res.keys := by
rw [List.filter_eq_self]
intro x hx
exact decide_eq_true (hlast_le x hx)
have h2 : J.filter (fun k : Key => decide (k ≤ last)) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx hcon
exact (not_le.mpr (by rw [hlast]; exact hJgt x hx)) (of_decide_eq_true hcon)
rw [h1, h2, List.append_nil]
rw [List.filter_comm]
rw [show db.keys.filter (fun k : Key => decide (k ≤ res.keys.getLast hne)) =
([] : Key) :: res.keys from by rwa [← hlast]]
by_cases hE : r.end_.key = (([] : Key) : WithTop Key)
· have hresE : res.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) = res.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq, hE]
exact coe_nil_le_key_withTop _
have hnilE : decide (r.end_.key ≤ ((([] : Key) : WithTop Key))) = true := by
rw [decide_eq_true_eq, hE]
rw [List.filter_cons, ite_eq_left hnilE, hresE, List.length_cons]
have hbase' : res.keys.length ≤ (r.end_.offset - 1).toNat := by
rwa [hresE] at hbase
have hne_count := hunsat.resolve_left (not_not.mpr hE)
omega
· have hnilE : decide (r.end_.key ≤ ((([] : Key) : WithTop Key))) = false := by
rw [decide_eq_false_iff_not]
intro hle
exact hE (le_antisymm hle (coe_nil_le_key_withTop _))
rw [List.filter_cons, hnilE]
simpa only [Bool.false_eq_true, ↓reduceIte] using hbase
/-- A nonempty-head clamping gap with room for the full begin slack and an unsaturated
end window. The arbitrary-end padded witness applies to this whole region. -/
abbrev negCrossTruncClampGapPadded (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = false ∧ r.begin.offset < 0 ∧ res.keys ≠ [] ∧
1 ≤ r.end_.offset ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key ∧
(((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) < r.begin.key ∧
reportedBelowBegin r res ≤ beginSlack r ∧
res.keys.headD ([] : Key) ≠ ([] : Key) ∧
((beginSlack r + 1 - res.keys.length : ℕ) : ℕ∞) ≤
intervalCard (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key)
r.begin.key ∧
(r.end_.key ≠ (([] : Key) : WithTop Key) ∨
(r.end_.offset - 1).toNat ≠ res.keys.length)
/-- **Gap keys are necessary at an arbitrary positive end key when the end window is
unsaturated.** The witness stores the empty key, the reported keys, and `T` gap keys
including the target. Its begin selector resolves to the reported head. Erasing the
target lowers the begin anchor to zero, so the empty key enters the truncated window. -/
theorem necessary_gap_padded {r : RangeRead} {res : Result} {k : Key}
(hread : Readable r res) (hcell : negCrossTruncClampGapPadded r res)
(hkgt : res.keys.getLastD ([] : Key) < k)
(hkB : ((k : Key) : WithTop Key) < r.begin.key) :
Necessary r res k := by
obtain ⟨hmore, hrev, hbegin, hne, hendoff, hcrossD, hgap, hclamp, hheadne, hcap,
hunsat⟩ := hcell
obtain ⟨db₀, hcomp₀⟩ := hread
intro cr hs
by_contra hkcr
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hlim : r.withinLimit res.keys := hcomp₀.1
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
set t : ℕ := res.keys.length with ht
set q : ℕ := beginSlack r with hq
set T : ℕ := q + 1 - t with hT
have hlastD : res.keys.getLastD ([] : Key) = last := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hheadD : res.keys.headD ([] : Key) = head := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
have hheadne' : head ≠ ([] : Key) := by rw [← hheadD]; exact hheadne
have hgap' : (((keyAfter last : Key)) : WithTop Key) < r.begin.key := by
rw [← hlastD]; exact hgap
have hlastB : ((last : Key) : WithTop Key) < r.begin.key :=
lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) hgap'
have hkgt' : last < k := by rw [← hlastD]; exact hkgt
have hlast_le : ∀ x ∈ res.keys, x ≤ last := by
intro x hx
rw [hlast]
exact (hsort.pairwise.imp le_of_lt).rel_getLast hx
have hreported : reportedBelowBegin r res = t := by
unfold reportedBelowBegin
rw [List.countP_eq_length]
intro x hx
rw [decide_eq_true_eq]
exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hlast_le x hx)) hlastB
have htq : t ≤ q := by rw [← hreported, hq]; exact hclamp
have hTpos : 1 ≤ q + 1 - t := by omega
have hres_lt_B : ∀ 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 (hlast_le x hx)) hlastB
have hnil_lt_head : ([] : Key) < head :=
lt_of_le_of_ne (nil_le_key head) (Ne.symm hheadne')
have hhead_le : ∀ x ∈ res.keys, head ≤ x := by
intro x hx
rw [hhead]
exact (hsort.pairwise.imp le_of_lt).rel_head hx
have hnil_lt_mem : ∀ x ∈ res.keys, ([] : Key) < x := by
intro x hx
exact lt_of_lt_of_le hnil_lt_head (hhead_le x hx)
have hnil_lt_B : (([] : Key) : WithTop Key) < r.begin.key :=
lt_trans (WithTop.coe_lt_coe.mpr hnil_lt_head)
(hres_lt_B head (List.head_mem hne))
have hnil_lt_lastK : ([] : Key) < last :=
lt_of_lt_of_le hnil_lt_head (hlast_le head (List.head_mem hne))
have hnil_lt_last : (([] : Key) : WithTop Key) < ((last : Key) : WithTop Key) :=
WithTop.coe_lt_coe.mpr hnil_lt_lastK
have hD : ((T : ℕ) : ℕ∞) ≤
intervalCard (((keyAfter last : Key)) : WithTop Key) r.begin.key := by
rw [hlastD] at hcap
simpa only [hT, hq, ht] using hcap
have hcard' : (((T - 1) + 1 : ℕ) : ℕ∞) ≤
intervalCard (((keyAfter last : Key)) : WithTop Key) r.begin.key := by
rw [Nat.sub_add_cancel hTpos]
exact hD
obtain ⟨dbJ, hJmem, hJavoid, hJlen⟩ := exists_db_keysIn_avoid
(B := (((keyAfter last : Key)) : WithTop Key)) (E := r.begin.key) (k := k)
(m := T - 1) hcard'
have hJ'range : ∀ x ∈ dbJ.keys,
(((keyAfter last : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
((x : Key) : WithTop Key) < r.begin.key :=
fun x hx => hJmem x hx
have hJ'gt_last : ∀ x ∈ dbJ.keys, last < x := by
intro x hx
have h1 := (hJ'range x hx).1
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le
(WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) h1)
have hres_lt_J' : ∀ x ∈ res.keys, ∀ y ∈ dbJ.keys, x < y := by
intro x hx y hy
exact lt_of_le_of_lt (hlast_le x hx) (hJ'gt_last y hy)
have hk_le_keyAfter : keyAfter last ≤ k := by
by_contra hcon
rw [not_le] at hcon
exact absurd ((lt_keyAfter_iff k last).mp hcon) (not_le.mpr hkgt')
have hk_not_res : k ∉ res.keys := by
intro hk
exact absurd (hlast_le k hk) (not_le.mpr hkgt')
have hk_ne_nil : k ≠ ([] : Key) := by
intro h
have hnil_lt_k : ([] : Key) < k := lt_of_le_of_lt (nil_le_key last) hkgt'
rw [h] at hnil_lt_k
exact (lt_irrefl ([] : Key)) hnil_lt_k
have hk_not_dbJ : k ∉ dbJ.keys := hJavoid
let J : List Key := dbJ.keys.orderedInsert (· ≤ ·) k
have hJlen' : J.length = T := by
unfold J
rw [List.orderedInsert_length, hJlen]
omega
have hJnodup : J.Nodup := by
unfold J
exact (List.perm_orderedInsert (· ≤ ·) k dbJ.keys).nodup_iff.mpr
(List.nodup_cons.mpr ⟨hk_not_dbJ, dbJ.nodup⟩)
have hJle : J.Pairwise (· ≤ ·) := by
unfold J
exact (dbJ.sorted.pairwise.imp le_of_lt).orderedInsert k
have hJsorted : J.SortedLT :=
List.sortedLT_iff_pairwise.mpr (DB.pairwise_lt_of_le_of_nodup hJle hJnodup)
have hJrange : ∀ x ∈ J,
(((keyAfter last : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) ∧
((x : Key) : WithTop Key) < r.begin.key := by
intro x hx
unfold J at hx
rw [List.mem_orderedInsert] at hx
rcases hx with rfl | hx
· exact ⟨WithTop.coe_le_coe.mpr hk_le_keyAfter, hkB⟩
· exact hJ'range x hx
have hJgt_last : ∀ x ∈ J, last < x := by
intro x hx
have h1 := (hJrange x hx).1
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le
(WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) h1)
have hres_lt_J : ∀ x ∈ res.keys, ∀ y ∈ J, x < y := by
intro x hx y hy
exact lt_of_le_of_lt (hlast_le x hx) (hJgt_last y hy)
have hsorted0 : (([] : Key) :: (res.keys ++ dbJ.keys)).SortedLT := by
rw [List.sortedLT_cons]
refine ⟨?_, ?_⟩
· intro x hx
rcases List.mem_append.mp hx with hx | hx
· exact hnil_lt_mem x hx
· exact lt_trans hnil_lt_lastK (hJ'gt_last x hx)
· exact List.sortedLT_append.mpr ⟨hsort, dbJ.sorted, hres_lt_J'⟩
let db0 : DB := ⟨([] : Key) :: (res.keys ++ dbJ.keys), hsorted0⟩
have hsorted1 : (([] : Key) :: (res.keys ++ J)).SortedLT := by
rw [List.sortedLT_cons]
refine ⟨?_, ?_⟩
· intro x hx
rcases List.mem_append.mp hx with hx | hx
· exact hnil_lt_mem x hx
· exact lt_trans hnil_lt_lastK (hJgt_last x hx)
· exact List.sortedLT_append.mpr ⟨hsort, hJsorted, hres_lt_J⟩
let db1 : DB := ⟨([] : Key) :: (res.keys ++ J), hsorted1⟩
have hcnt1 : ((db1.keys.filter
(fun x : Key => decide (r.end_.key ≤ (x : WithTop Key)))).filter
(fun x : Key => decide (x ≤ res.keys.getLast hne))).length ≤
(r.end_.offset - 1).toNat :=
end_count_nil_cons_gapKeys_of_unsaturated (db := db1) (J := J) ⟨db₀, hcomp₀⟩
hrev hmore hne hendoff hunsat rfl (by
intro x hx
rw [← hlast]
exact hJgt_last x hx)
have hcomp1 : RangeRead.Compatible db1 r res :=
compatible_of_nil_cons_gapKeys_high_of_end_count hrev hmore hne hbegin hendoff hlim htq
hheadne hgap hsort hJsorted
(by intro x hx; rw [hlastD]; exact hJrange x hx)
(by rw [hJlen']) rfl hcnt1
have hnotcomp0 : ¬ RangeRead.Compatible db0 r res := by
intro hc0
have hfil0 := ((compatible_iff_truncated_keys (db := db0) hrev hmore hne).mp hc0).2
rw [← hlast] at hfil0
have hcnt0 : cnt db0 r.begin.key = 1 + t + (T - 1) := by
rw [cnt, List.countP_eq_length_filter]
have hf : db0.keys.filter (fun x : Key => decide (((x : Key) : WithTop Key) <
r.begin.key)) = db0.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
rw [show db0.keys = ([] : Key) :: (res.keys ++ dbJ.keys) from rfl] at hx
rcases List.mem_cons.mp hx with rfl | hx
· exact hnil_lt_B
· rcases List.mem_append.mp hx with hx | hx
· exact hres_lt_B x hx
· exact (hJ'range x hx).2
rw [hf, show db0.keys = ([] : Key) :: (res.keys ++ dbJ.keys) from rfl]
rw [List.length_cons, List.length_append, ht, hJlen]
omega
have hanchor0 : r.begin.anchor db0 = 0 := by
rw [anchor_eq_count_sub_slack db0 r (le_of_lt hbegin)]
change ((cnt db0 r.begin.key : ℕ) : ℤ) - (beginSlack r : ℤ) - 1 = 0
rw [hcnt0, ← hq]
have : ((1 + t + (T - 1) : ℕ) : ℤ) - (q : ℤ) - 1 = 0 := by rw [hT]; omega
exact this
have hbot_mem : ([] : Key) ∈ db0.keys := by
rw [show db0.keys = ([] : Key) :: (res.keys ++ dbJ.keys) from rfl]
exact List.mem_cons_self ..
have hresB0 : resolve db0 r.begin = ((↑([] : Key)) : WithTop Key) := by
have h0 : 0 ≤ r.begin.anchor db0 := by rw [hanchor0]
have hlt : (r.begin.anchor db0).toNat < db0.keys.length := by
rw [hanchor0]
exact List.length_pos_of_mem hbot_mem
have hval : db0.keys[(r.begin.anchor db0).toNat]'(hlt) = ([] : Key) := by
apply Option.some.inj
rw [← List.getElem?_eq_getElem (h := hlt)]
have hidx : (r.begin.anchor db0).toNat = 0 := by rw [hanchor0]; rfl
rw [hidx, List.getElem?_eq_getElem (h := List.length_pos_of_mem hbot_mem)]
exact congrArg some (keys_getElem_zero_eq_nil_of_mem hbot_mem)
rw [resolve_eq_getElem h0 hlt]
exact congrArg (fun z : Key => ((z : Key) : WithTop Key)) hval
have hlast_ck0 : last ∈ RangeRead.completeKeys db0 r :=
(RangeRead.compatible_keys_prefix hc0).subset (by
rw [hlast]
exact List.getLast_mem hne)
have hresE0 : ((last : Key) : WithTop Key) < resolve db0 r.end_ :=
(RangeRead.mem_completeKeys.mp hlast_ck0).2.2
have hnil_ck : ([] : Key) ∈ RangeRead.completeKeys db0 r := by
rw [RangeRead.mem_completeKeys]
refine ⟨hbot_mem, ?_, ?_⟩
· rw [hresB0]
· exact lt_trans hnil_lt_last hresE0
have hnil_fil : ([] : Key) ∈ (RangeRead.completeKeys db0 r).filter
(fun x : Key => decide (x ≤ last)) := by
rw [List.mem_filter]
exact ⟨hnil_ck, by rw [decide_eq_true_eq]; exact nil_le_key last⟩
rw [hfil0] at hnil_fil
have hnil_not_mem : ([] : Key) ∉ res.keys := by
intro hmem
exact (not_le.mpr hnil_lt_head) (hhead_le [] hmem)
exact hnil_not_mem hnil_fil
have hagree : AgreeOn cr db1 db0 := by
unfold AgreeOn ConflictRange.keys
apply List.SortedLT.eq_of_mem_iff
· exact List.sortedLT_iff_pairwise.mpr (db1.sorted.pairwise.filter _)
· exact List.sortedLT_iff_pairwise.mpr (db0.sorted.pairwise.filter _)
· intro x
simp only [List.mem_filter, decide_eq_true_eq]
have hdbiff : x ∈ db1.keys ↔ x = k ∨ x ∈ db0.keys := by
change x ∈ ([] : Key) :: (res.keys ++ J) ↔
x = k ∨ x ∈ ([] : Key) :: (res.keys ++ dbJ.keys)
unfold J
simp only [List.mem_cons, List.mem_append, List.mem_orderedInsert]
tauto
constructor
· rintro ⟨hdb, hcr⟩
rcases (hdbiff.mp hdb) with rfl | hdb0
· exact absurd hcr hkcr
· exact ⟨hdb0, hcr⟩
· rintro ⟨hdb, hcr⟩
exact ⟨hdbiff.mpr (Or.inr hdb), hcr⟩
exact hnotcomp0 ((hs db1 db0 hagree).mp hcomp1)
/-- **Minimality of `[⊥, begin.key)` for an unsaturated padded gap.** Soundness is the
arbitrary-end clamping argument. Keys below the reported head use the reported-list
witness, reported-span keys use convexity, and gap keys use `necessary_gap_padded`. -/
theorem minimal_beginRange_of_gap_padded {r : RangeRead} {res : Result}
(hread : Readable r res) (hcell : negCrossTruncClampGapPadded r res) :
Minimal r res (closedFormNegCrossTruncClampNoGapTop r res) := by
obtain ⟨hmore, hrev, hbegin, hne, hendoff, hcrossD, hgap, hclamp, hheadne, hcap,
hunsat⟩ := hcell
obtain ⟨db₀, hcomp₀⟩ := hread
have hread' : Readable r res := ⟨db₀, hcomp₀⟩
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
have hheadD : res.keys.headD ([] : Key) = head := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
have hlastD : res.keys.getLastD ([] : Key) = last := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hlastB : ((last : Key) : WithTop Key) < r.begin.key := by
have hgap' : (((keyAfter last : Key)) : WithTop Key) < r.begin.key := by
rw [← hlastD]; exact hgap
exact lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) hgap'
have hcross : ((head : Key) : WithTop Key) < r.begin.key := by
have hcd := hcrossD
simp only [leastReported, hrev] at hcd
rwa [hheadD] at hcd
have hsound : Sound r res (closedFormNegCrossTruncClampNoGapTop r res) := by
intro db1 db2 hagree
exact ⟨fun h => compatible_of_agree_negCross_trunc_clamp hrev hmore hne hbegin
hendoff (by rwa [← hlast]) h hagree,
fun h => compatible_of_agree_negCross_trunc_clamp hrev hmore hne hbegin
hendoff (by rwa [← hlast]) h hagree.symm⟩
refine (minimal_iff_sound_and_necessaryRange).mpr ⟨hsound, ?_⟩
intro k _ hkend
by_cases hkhead : ((k : Key) : WithTop Key) < ((head : Key) : WithTop Key)
· exact necessary_below_head_of_negCross_trunc_clamp hread' hrev hmore hne hbegin
hendoff hcross hclamp hkhead
· by_cases hkle : k ≤ last
· exact necessary_of_between_result hread' (a := head) (b := last)
(by rw [hhead]; exact List.head_mem hne)
(by rw [hlast]; exact List.getLast_mem hne)
(WithTop.coe_le_coe.mp (le_of_not_gt hkhead)) hkle
· apply necessary_gap_padded hread'
⟨hmore, hrev, hbegin, hne, hendoff, hcrossD, hgap, hclamp, hheadne, hcap, hunsat⟩
· rw [hlastD]
exact lt_of_not_ge hkle
· exact hkend
/-- A genuine clamping gap at exact nonempty-head capacity, with a saturated empty-key
end window. Writing `T = beginSlack + 1 - #reported`, the gap above `keyAfter last` has
exactly `T` available keys, and the end window has exactly one position per reported key. -/
abbrev negCrossTruncClampGapExactSaturated (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = false ∧ r.begin.offset < 0 ∧ res.keys ≠ [] ∧
1 ≤ r.end_.offset ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key ∧
(((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) < r.begin.key ∧
reportedBelowBegin r res ≤ beginSlack r ∧
r.end_.key = (([] : Key) : WithTop Key) ∧
(r.end_.offset - 1).toNat = res.keys.length ∧
intervalCard (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key)
r.begin.key = ((beginSlack r + 1 - res.keys.length : ℕ) : ℕ∞)
/-- Compatibility is unchanged by lowering the begin key in the saturated exact-capacity
cell. Saturation excludes stored keys below the reported head. The exact capacity then
keeps the original begin resolution at or below that head, while the lowered read clamps;
both reads therefore have the same complete window. -/
theorem compatible_iff_noGapRead_of_gapExactSaturated {r : RangeRead} {res : Result}
(hread : Readable r res) (hcell : negCrossTruncClampGapExactSaturated r res) (db : DB) :
RangeRead.Compatible db r res ↔ RangeRead.Compatible db (noGapRead r res) res := by
obtain ⟨hmore, hrev, hbegin, hne, hendoff, hcrossD, hgap, hclamp, hE, hsat, hcap⟩ := hcell
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
set t : ℕ := res.keys.length with ht
set q : ℕ := beginSlack r with hq
set T : ℕ := q + 1 - t with hT
have hlastD : res.keys.getLastD ([] : Key) = last := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hlastD' : res.keys.getLast?.getD ([] : Key) = last := by
rw [List.getLast?_eq_some_getLast hne]; rfl
have hheadD : res.keys.headD ([] : Key) = head := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
have hgap' : (((keyAfter last : Key)) : WithTop Key) < r.begin.key := by
rw [← hlastD]; exact hgap
have hlastB : ((last : Key) : WithTop Key) < r.begin.key :=
lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) hgap'
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
have hmem_le_last : ∀ k ∈ res.keys, k ≤ last := by
intro k hk
rw [hlast]
exact (hsort.pairwise.imp le_of_lt).rel_getLast hk
have hreported : reportedBelowBegin r res = t := by
unfold reportedBelowBegin
rw [List.countP_eq_length]
intro k hk
rw [decide_eq_true_eq]
exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hmem_le_last k hk)) hlastB
have htq : t ≤ q := by rw [← hreported, hq]; exact hclamp
have hcap' : intervalCard (((keyAfter last : Key)) : WithTop Key) r.begin.key =
((T : ℕ) : ℕ∞) := by
rw [hlastD] at hcap
simpa only [hT, hq, ht] using hcap
constructor
· intro hcomp
have hno : ∀ x ∈ db.keys, ¬ x < head := by
intro x hx hlt
exact not_lt_head_of_mem_of_compatible_saturated hcomp hrev hmore hne hendoff hE
hsat hx (by simpa only [hhead] using hlt)
have hcntK : cnt db (((keyAfter last : Key)) : WithTop Key) = t := by
have h := cnt_keyAfter_getLast_eq_length_of_no_lt_head hcomp hrev hmore hne
(by simpa [hhead] using hno)
simpa [hlast, ht] using h
have hanchorNG : (noGapRead r res).begin.anchor db < 0 := by
have h_eq : (noGapRead r res).begin.anchor db =
(cnt db (((keyAfter last : Key)) : WithTop Key) : ℤ) -
(beginSlack r : ℤ) - 1 := by
have hs : beginSlack (noGapRead r res) = beginSlack r := rfl
rw [anchor_eq_count_sub_slack db (noGapRead r res) (le_of_lt hbegin), hs]
simp [cnt, noGapRead, hlastD']
rw [h_eq, hcntK]
have h1 : (t : ℤ) ≤ (q : ℤ) := by exact_mod_cast htq
rw [← hq]
omega
have hbng : resolve db (noGapRead r res).begin ≤ ((head : Key) : WithTop Key) := by
rw [resolve_eq_nil hanchorNG]
exact coe_nil_le_key_withTop _
have hbr : resolve db r.begin ≤ ((head : Key) : WithTop Key) := by
have hhead_ck : head ∈ RangeRead.completeKeys db r :=
(RangeRead.compatible_keys_prefix hcomp).subset (by rw [hhead]; exact List.head_mem hne)
exact (RangeRead.mem_completeKeys.mp hhead_ck).2.1
have hck := completeKeys_noGapRead_eq_of_no_lt_head hrev hno hbr hbng
rw [compatible_iff_truncated_keys (r := noGapRead r res) hrev hmore hne]
exact ⟨by change RangeRead.withinLimit r res.keys; exact hcomp.1,
by rw [← hck]; exact ((compatible_iff_truncated_keys hrev hmore hne).mp hcomp).2⟩
· intro hcompNG
have hno : ∀ x ∈ db.keys, ¬ x < head := by
intro x hx hlt
exact not_lt_head_of_mem_of_compatible_saturated (r := noGapRead r res) hcompNG hrev
hmore hne hendoff (by simpa [noGapRead] using hE) (by simpa [noGapRead] using hsat)
hx (by simpa only [hhead] using hlt)
have hcntK : cnt db (((keyAfter last : Key)) : WithTop Key) = t := by
have h := cnt_keyAfter_getLast_eq_length_of_no_lt_head (r := noGapRead r res) hcompNG
hrev hmore hne (by simpa [hhead] using hno)
simpa [hlast, ht] using h
have hbng : resolve db (noGapRead r res).begin ≤ ((head : Key) : WithTop Key) := by
have hhead_ck : head ∈ RangeRead.completeKeys db (noGapRead r res) :=
(RangeRead.compatible_keys_prefix hcompNG).subset (by rw [hhead]; exact List.head_mem hne)
exact (RangeRead.mem_completeKeys.mp hhead_ck).2.1
set g : ℕ := (between db (((keyAfter last : Key)) : WithTop Key) r.begin.key).length
with hg
have hcntB : cnt db r.begin.key = t + g := by
rw [cnt_eq_add_between db (le_of_lt hgap'), hcntK, ← hg]
have hgT : g ≤ T := by
have hgA : (g : ℕ∞) ≤ intervalCard (((keyAfter last : Key)) : WithTop Key)
r.begin.key := by
rw [hg]
exact between_length_le_intervalCard (db := db) (le_of_lt hgap')
exact ENat.natCast_le_natCast.mp (hgA.trans hcap'.le)
have htg : t + g ≤ q + 1 := by rw [hT] at hgT; omega
have hanchor : r.begin.anchor db ≤ 0 := by
have h_eq : r.begin.anchor db =
(cnt db r.begin.key : ℤ) - (beginSlack r : ℤ) - 1 := by
rw [anchor_eq_count_sub_slack db r (le_of_lt hbegin)]
simp [cnt]
rw [h_eq, hcntB]
have h1 : ((t + g : ℕ) : ℤ) ≤ (q : ℤ) + 1 := by exact_mod_cast htg
rw [← hq]
omega
have hheadDB : head ∈ db.keys :=
RangeRead.compatible_keys_subset hcompNG (by rw [hhead]; exact List.head_mem hne)
have hbr := resolve_begin_le_of_anchor_nonpos_of_no_lt_head hheadDB hno hanchor
have hck := completeKeys_noGapRead_eq_of_no_lt_head hrev hno hbr hbng
rw [compatible_iff_truncated_keys hrev hmore hne]
rw [compatible_iff_truncated_keys (r := noGapRead r res) hrev hmore hne] at hcompNG
exact ⟨by exact hcompNG.1,
by rw [hck]; exact hcompNG.2⟩
/-- The lowered read satisfies the arbitrary-end no-gap clamping cell. -/
theorem negCrossTruncClampNoGap_noGapRead_of_gapExactSaturated {r : RangeRead} {res : Result}
(hread : Readable r res) (hcell : negCrossTruncClampGapExactSaturated r res) :
negCrossTruncClampNoGap (noGapRead r res) res := by
obtain ⟨hmore, hrev, hbegin, hne, hendoff, hcrossD, hgap, hclamp, hE, hsat, hcap⟩ := hcell
obtain ⟨db₀, hcomp₀⟩ := hread
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
set t : ℕ := res.keys.length with ht
have hlastD : res.keys.getLastD ([] : Key) = last := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hheadD' : res.keys.head?.getD ([] : Key) = head := by
rw [List.head?_eq_some_head hne]; rfl
have hgap' : (((keyAfter last : Key)) : WithTop Key) < r.begin.key := by
rw [← hlastD]; exact hgap
have hlastB : ((last : Key) : WithTop Key) < r.begin.key :=
lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) hgap'
have hmem_le_last : ∀ k ∈ res.keys, k ≤ last := by
intro k hk
rw [hlast]
exact (hsort.pairwise.imp le_of_lt).rel_getLast hk
have hreported : reportedBelowBegin r res = t := by
unfold reportedBelowBegin
rw [List.countP_eq_length]
intro k hk
rw [decide_eq_true_eq]
exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hmem_le_last k hk)) hlastB
have htq : t ≤ beginSlack r := by rw [← hreported]; exact hclamp
have hcrossNG : ((leastReported (noGapRead r res) res : Key) : WithTop Key) <
(noGapRead r res).begin.key := by
have hle : leastReported (noGapRead r res) res = head := by
unfold leastReported
rw [show (noGapRead r res).reverse = false from hrev]
simp [hheadD']
rw [hle, show (noGapRead r res).begin.key =
(((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) from rfl, hlastD]
exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hmem_le_last head (List.head_mem hne)))
(WithTop.coe_lt_coe.mpr (keyAfter_self_lt last))
have hreportedNG : reportedBelowBegin (noGapRead r res) res = t := by
unfold reportedBelowBegin
rw [List.countP_eq_length]
intro k hk
rw [decide_eq_true_eq]
rw [show (noGapRead r res).begin.key =
(((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) from rfl, hlastD]
exact WithTop.coe_lt_coe.mpr ((lt_keyAfter_iff k last).mpr (hmem_le_last k hk))
have hclampNG : reportedBelowBegin (noGapRead r res) res ≤
beginSlack (noGapRead r res) := by
rw [hreportedNG]
exact htq
exact ⟨hmore, hrev, hbegin, hne, hendoff, hcrossNG, rfl, hclampNG⟩
/-- **The saturated exact-capacity branch has the shorter range `[⊥, keyAfter last)`.** -/
theorem minimal_closedForm_of_negCross_trunc_clamp_gapExactSaturated
{r : RangeRead} {res : Result} (hread : Readable r res)
(hcell : negCrossTruncClampGapExactSaturated r res) :
Minimal r res (closedFormNegCrossTruncClampGapLow r res) := by
have hiff : ∀ db, RangeRead.Compatible db r res ↔
RangeRead.Compatible db (noGapRead r res) res :=
fun db => compatible_iff_noGapRead_of_gapExactSaturated hread hcell db
have hreadNG : Readable (noGapRead r res) res := by
obtain ⟨db₀, hcomp₀⟩ := hread
exact ⟨db₀, (hiff db₀).mp hcomp₀⟩
have hcellNG : negCrossTruncClampNoGap (noGapRead r res) res :=
negCrossTruncClampNoGap_noGapRead_of_gapExactSaturated hread hcell
exact (minimal_congr_of_compatible_iff hiff).mpr
(minimal_closedForm_of_negCross_trunc_clamp_noGap hreadNG hcellNG)
/-- **Minimality of `[⊥, begin.key)` under the insertion-capacity bound.** Soundness is
the arbitrary-end clamping argument. Keys below the reported head use the reported-list
toggle witness, keys in the reported span are necessary by convexity, and gap keys use
`necessary_gap_insert_of_capacity`. -/
theorem minimal_beginRange_of_gap_insert_capacity {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0) (hendoff : 1 ≤ r.end_.offset)
(hcrossD : ((leastReported r res : Key) : WithTop Key) < r.begin.key)
(hgap : (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key) <
r.begin.key)
(hclamp : reportedBelowBegin r res ≤ beginSlack r)
(hcap : (((beginSlack r + 1 - res.keys.length) + 1 : ℕ) : ℕ∞) ≤
intervalCard (((keyAfter (res.keys.getLastD ([] : Key)) : Key)) : WithTop Key)
r.begin.key) :
Minimal r res (closedFormNegCrossTruncClampNoGapTop r res) := by
obtain ⟨db₀, hcomp₀⟩ := hread
have hread' : Readable r res := ⟨db₀, hcomp₀⟩
set head : Key := res.keys.head hne with hhead
set last : Key := res.keys.getLast hne with hlast
have hheadD : res.keys.headD ([] : Key) = head := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
have hlastD : res.keys.getLastD ([] : Key) = last := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hlastB : ((last : Key) : WithTop Key) < r.begin.key := by
have hgap' : (((keyAfter last : Key)) : WithTop Key) < r.begin.key := by
rw [← hlastD]; exact hgap
exact lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt last)) hgap'
have hcross : ((head : Key) : WithTop Key) < r.begin.key := by
have hcd := hcrossD
simp only [leastReported, hrev] at hcd
rwa [hheadD] at hcd
have hsound : Sound r res (closedFormNegCrossTruncClampNoGapTop r res) := by
intro db1 db2 hagree
exact ⟨fun h => compatible_of_agree_negCross_trunc_clamp hrev hmore hne hbegin
hendoff (by rwa [← hlast]) h hagree,
fun h => compatible_of_agree_negCross_trunc_clamp hrev hmore hne hbegin
hendoff (by rwa [← hlast]) h hagree.symm⟩
refine (minimal_iff_sound_and_necessaryRange).mpr ⟨hsound, ?_⟩
intro k _ hkend
by_cases hkhead : ((k : Key) : WithTop Key) < ((head : Key) : WithTop Key)
· exact necessary_below_head_of_negCross_trunc_clamp hread' hrev hmore hne hbegin
hendoff hcross hclamp hkhead
· by_cases hkle : k ≤ last
· exact necessary_of_between_result hread' (a := head) (b := last)
(by rw [hhead]; exact List.head_mem hne)
(by rw [hlast]; exact List.getLast_mem hne)
(WithTop.coe_le_coe.mp (le_of_not_gt hkhead)) hkle
· apply necessary_gap_insert_of_capacity hread' hmore hrev hne hbegin hendoff hcrossD
hgap hclamp hcap
· rw [hlastD]
exact lt_of_not_ge hkle
· exact hkend
end FormalConflictRange