/- Released under Apache 2.0 license as described in the file LICENSE. -/ import FormalConflictRange.NegCrossTruncRevBeginTop /-! # Reversed truncated cells with every reported key below the end key This module closes the reversed negative-begin truncated cell at end offset at least two whose reported keys all lie strictly below `end_.key`, for an arbitrary begin key (not only the sentinel `⊤`). * `reverse = true`, `more = true`, `res.keys ≠ []`, `begin.offset < 0`; * `((res.keys.getLastD []) : WithTop Key) < begin.key` (the reported last is below the begin key); * `2 ≤ end_.offset`; * every reported key is strictly below `end_.key`. The minimal range is `[last reported, ⊤)`, the top range at the reported last key. The key observation is that at end offset at least two, the end resolution is the sentinel `⊤` in every compatible database. Consequently compatibility is unchanged by replacing `end_.key` with `⊤`, and the closed form transfers from the sentinel-end cell `negCrossTruncRevTop`. -/ namespace FormalConflictRange /-- Compatibility depends on the read only through its complete keys and its limit. -/ private theorem compatible_congr_of_completeKeys {db : DB} {r r' : RangeRead} {res : Result} (hck : RangeRead.completeKeys db r = RangeRead.completeKeys db r') (hlim : r.limit = r'.limit) : RangeRead.Compatible db r res ↔ RangeRead.Compatible db r' res := by unfold RangeRead.Compatible RangeRead.withinLimit rw [hck, hlim] /-- The last element of a strictly increasing list is at or above every element. -/ private theorem pairwise_le_getLast' {l : List Key} (h : l.Pairwise (· < ·)) {a : Key} (ha : a ∈ l) {hne : l ≠ []} : a ≤ l.getLast hne := (h.imp le_of_lt).rel_getLast ha /-- For a reversed read, the reported head is the window's last element. -/ private theorem head?_eq_getLast?_of_prefix_rev' {db : DB} {r : RangeRead} {res : Result} (hrev : r.reverse = true) (hpre : res.keys <+: RangeRead.completeKeys db r) (hne : res.keys ≠ []) : res.keys.head? = (RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_)).getLast? := by have hck : RangeRead.completeKeys db r = (RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_)).reverse := by simp [RangeRead.completeKeys, hrev] obtain ⟨t, ht⟩ := hpre rw [← ht] at hck calc res.keys.head? = (res.keys ++ t).head? := (List.head?_append_of_ne_nil _ hne).symm _ = (RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_)).reverse.head? := by rw [hck] _ = (RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_)).getLast? := List.head?_reverse /-- In a reversed read, every complete key is at or below the reported head. -/ private theorem le_head_of_mem_completeKeys_rev' {db : DB} {r : RangeRead} {res : Result} (hrev : r.reverse = true) (hpre : res.keys <+: RangeRead.completeKeys db r) (hne : res.keys ≠ []) {k : Key} (hk : k ∈ RangeRead.completeKeys db r) : k ≤ res.keys.head hne := by have hck : RangeRead.completeKeys db r = (RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_)).reverse := by simp [RangeRead.completeKeys, hrev] have hWne : RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_) ≠ [] := fun h => hpre.ne_nil hne (hck.trans (List.reverse_eq_nil_iff.mpr h)) rw [hck, List.mem_reverse] at hk have h1 : k ≤ (RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_)).getLast hWne := pairwise_le_getLast' (RangeRead.inRange_pairwise db _ _) hk have h2 : res.keys.head hne = (RangeRead.inRange db.keys (resolve db r.begin) (resolve db r.end_)).getLast hWne := by refine (List.head_eq_iff_head?_eq_some hne).mpr ?_ rw [head?_eq_getLast?_of_prefix_rev' hrev hpre hne, List.getLast?_eq_getLast_of_ne_nil hWne] rw [h2] exact h1 /-- **At end offset at least two with every reported key below `end_.key`, the end resolution is the sentinel.** A compatible window whose reported keys all lie below `end_.key` cannot contain a stored key at or above `end_.key`: such a key would be the window's largest element and hence the reported head, contradicting the hypothesis. -/ theorem resolve_end_eq_top_of_below_compat {db : DB} {r : RangeRead} {res : Result} (hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = true) (hne : res.keys ≠ []) (hend : 2 ≤ r.end_.offset) (hbelow : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key) : resolve db r.end_ = (⊤ : WithTop Key) := by refine resolve_end_eq_top_of_hhi hcomp hend hbelow (res.keys.head hne) (List.head_mem hne) (fun k hk => ?_) exact le_head_of_mem_completeKeys_rev' hrev (RangeRead.compatible_keys_prefix hcomp) hne hk /-- **Replacing the end key by the sentinel preserves compatibility.** At end offset at least two with every reported key below `end_.key`, every compatible database resolves the end selector to `⊤`, so the complete keys — and hence compatibility — are unchanged by moving the end key to `⊤`. Conversely, a database compatible with the sentinel-end read cannot store a key at or above `end_.key`: the reported keys are the largest stored keys at or above the resolved begin, and the reported head is below `end_.key`. -/ theorem compatible_iff_topEnd_of_below {db : DB} {r : RangeRead} {res : Result} (hrev : r.reverse = true) (hne : res.keys ≠ []) (hend : 2 ≤ r.end_.offset) (hbelow : ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key) : RangeRead.Compatible db r res ↔ RangeRead.Compatible db { r with end_ := { r.end_ with key := (⊤ : WithTop Key) } } res := by let r' : RangeRead := { r with end_ := { r.end_ with key := (⊤ : WithTop Key) } } have hrev' : r'.reverse = true := by simp [r', hrev] constructor · intro hcomp have hre : resolve db r.end_ = (⊤ : WithTop Key) := resolve_end_eq_top_of_below_compat hcomp hrev hne hend hbelow have hre' : resolve db r'.end_ = (⊤ : WithTop Key) := resolve_eq_top_of_key_eq_top (db := db) (s := r'.end_) rfl (by simp [r']; omega) have hck : RangeRead.completeKeys db r = RangeRead.completeKeys db r' := by simp only [RangeRead.completeKeys, RangeRead.inRange, hrev, hrev', hre, hre'] rfl exact (compatible_congr_of_completeKeys hck (rfl : r.limit = r'.limit)).mp hcomp · intro hcomp' have hpre' : res.keys <+: RangeRead.completeKeys db r' := RangeRead.compatible_keys_prefix hcomp' have hre' : resolve db r'.end_ = (⊤ : WithTop Key) := resolve_eq_top_of_key_eq_top (db := db) (s := r'.end_) rfl (by simp [r']; omega) have hHmem : res.keys.head hne ∈ res.keys := List.head_mem hne have hrbH : resolve db r'.begin ≤ ((res.keys.head hne : Key) : WithTop Key) := (RangeRead.mem_completeKeys.mp (hpre'.subset hHmem)).2.1 have hHE : ((res.keys.head hne : Key) : WithTop Key) < r.end_.key := hbelow _ hHmem have hall : ∀ k ∈ db.keys, ((k : Key) : WithTop Key) < r.end_.key := by intro k hk by_contra hge have hge' : r.end_.key ≤ ((k : Key) : WithTop Key) := not_lt.mp hge have hkrb : resolve db r'.begin ≤ ((k : Key) : WithTop Key) := le_trans hrbH (le_trans (le_of_lt hHE) hge') have hkck : k ∈ RangeRead.completeKeys db r' := RangeRead.mem_completeKeys.mpr ⟨hk, hkrb, by rw [hre']; exact WithTop.coe_lt_top k⟩ have hmax := le_head_of_mem_completeKeys_rev' hrev' hpre' hne hkck exact absurd (lt_of_le_of_lt (WithTop.coe_le_coe.mpr hmax) hHE) (not_lt.mpr hge') have hre : resolve db r.end_ = (⊤ : WithTop Key) := resolve_eq_top_of_all_lt hall hend have hck : RangeRead.completeKeys db r = RangeRead.completeKeys db r' := by simp only [RangeRead.completeKeys, RangeRead.inRange, hrev, hrev', hre, hre'] rfl exact (compatible_congr_of_completeKeys hck (rfl : r.limit = r'.limit)).mpr hcomp' /-- The reversed negative-begin truncated cell at end offset at least two with every reported key below the end key. -/ abbrev negCrossTruncRevBelowEnd (r : RangeRead) (res : Result) : Prop := res.more = true ∧ r.reverse = true ∧ r.begin.offset < 0 ∧ res.keys ≠ [] ∧ ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) < r.begin.key ∧ 2 ≤ r.end_.offset ∧ ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key /-- The closed form of the reversed truncated below-end cell: `[last reported, ⊤)`. -/ noncomputable def closedFormNegCrossTruncRevBelowEnd (_r : RangeRead) (res : Result) : ConflictRange := topOfLast (res.keys.getLastD ([] : Key)) /-- **The reversed truncated below-end closed form is minimal.** The compatibility reduction to the sentinel-end read transfers minimality from `minimal_closedForm_of_negCross_trunc_rev_top`. -/ theorem minimal_closedForm_of_negCross_trunc_rev_belowEnd {r : RangeRead} {res : Result} (hread : Readable r res) (h : negCrossTruncRevBelowEnd r res) : Minimal r res (closedFormNegCrossTruncRevBelowEnd r res) := by obtain ⟨hmore, hrev, hbeg, hne, hcrossD, hend, hbelow⟩ := h let r' : RangeRead := { r with end_ := { r.end_ with key := (⊤ : WithTop Key) } } have hcompiff : ∀ db, RangeRead.Compatible db r res ↔ RangeRead.Compatible db r' res := fun db => compatible_iff_topEnd_of_below (db := db) hrev hne hend hbelow have hread' : Readable r' res := by obtain ⟨db, hcomp⟩ := hread exact ⟨db, (hcompiff db).mp hcomp⟩ have hcell' : negCrossTruncRevTop r' res := by refine ⟨hmore, by simp [r', hrev], by simp [r', hbeg], hne, ?_, rfl⟩ simpa [r'] using hcrossD have hmin' : Minimal r' res (closedFormNegCrossTruncRevBelowEnd r res) := minimal_closedForm_of_negCross_trunc_rev_top hread' hcell' exact (minimal_congr_of_compatible_iff (r := r) (r' := r') (res := res) (cr := closedFormNegCrossTruncRevBelowEnd r res) hcompiff).mpr hmin' end FormalConflictRange