Files

760 lines
38 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.CrossedClosedForm
/-!
# Crossed selectors at begin offset one: the truncated cells
This module proves the minimal conflict range for a truncated, non-reversed result at
`begin.offset = 1` when the selector keys are crossed, `end_.key < begin_.key`.
The complete-key window starts at the first stored key at or above `begin_.key`, while
the end resolution counts stored keys from `end_.key`. The gap `[end_.key, begin_.key)`
therefore contributes to the end count without contributing to the reported keys.
Writing `e = (end_.offset - 1).toNat`, `t = #reported keys`, and `h = intervalCard
end_.key begin_.key`, the minimal range is
* `[end_.key, keyAfter (last reported))` when `e - t < h`;
* `[begin_.key, keyAfter (last reported))` otherwise.
The lower endpoint moves down to `end_.key` exactly when the gap has room for the
remaining overshoot, mirroring the complete-result crossed rule.
-/
open FormalConflictRange
namespace FormalConflictRange
/-- **B-branch soundness for the forward truncated crossed read.** When the gap
`[end_.key, begin_.key)` has at least the remaining overshoot `e - |res|` keys, the
truncated range `[begin.key, keyAfter (last reported))` is sound. The proof rewrites
the complete keys as a take of the stored keys at or above `begin.key`; the range
equality fixes the filtered take, and the room bound makes the take long enough not to
cut the reported prefix. -/
theorem sound_truncatedRange_of_crossed_B {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hmore : res.more = true) (hne : res.keys ≠ [])
(hbegin : r.begin.offset = 1) (hcross : r.end_.key < r.begin.key)
(hend : 2 ≤ r.end_.offset)
(hcard : intervalCard r.end_.key r.begin.key ≤
(((r.end_.offset - 1).toNat - res.keys.length : ℕ) : ℕ∞)) :
Sound r res (truncatedRange r (res.keys.getLastD ([] : Key))) := by
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
rw [hlast]
intro db₁ db₂ hagree
have key (db : DB) : RangeRead.Compatible db r res ↔
RangeRead.withinLimit r res.keys ∧
(truncatedRange r (res.keys.getLast hne)).keys db = res.keys := by
constructor
· intro hc
refine ⟨hc.1, ?_⟩
set l := db.keys with hl
set A := l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) with hA
have hpre : res.keys <+: RangeRead.completeKeys db r :=
RangeRead.compatible_keys_prefix hc
have htake := completeKeys_eq_filter_take_of_offset_one (db := db) hrev hbegin
(by omega : 1 ≤ r.end_.offset)
have hpreA : res.keys <+: A := by
rw [hA]
refine List.IsPrefix.trans hpre ?_
rw [htake]
exact List.take_prefix _ _
have hAs : A.Pairwise (· < ·) := by
rw [hA]
exact db.sorted.pairwise.filter _
have hfil := filter_le_getLast_eq_of_prefix hAs hpreA hne
rw [truncatedRange_keys_eq_filter_le]
exact hfil
· rintro ⟨hlim, hT⟩
rw [compatible_iff_truncated_keys (db := db) hrev hmore hne]
refine ⟨hlim, ?_⟩
set l := db.keys with hl
set cE := l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) with hcE
set cB := l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hcB
set e := (r.end_.offset - 1).toNat with he
set A := l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) with hA
set n := res.keys.length with hn
set q := A.countP (fun k : Key => decide (k ≤ res.keys.getLast hne)) with hq
have hls : l.SortedLT := by rw [hl]; exact db.sorted
have hAs : A.Pairwise (· < ·) := by
rw [hA]
exact hls.pairwise.filter _
have hAsLT : A.SortedLT := List.sortedLT_iff_pairwise.mpr hAs
have hA_eq : A = l.drop cB := by
rw [hA, hcB]
have hdrop : l.filter (fun k : Key => decide (¬ ((k : WithTop Key) < r.begin.key)))
= l.drop (l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key))) :=
filter_not_lt_eq_drop_countP hls r.begin.key
rw [← hdrop]
apply List.filter_congr
intro k _
rw [decide_eq_decide]
exact not_lt.symm
have hfilT : A.filter (fun k : Key => decide (k ≤ res.keys.getLast hne)) = res.keys := by
rw [← truncatedRange_keys_eq_filter_le (db := db) (r := r) (last := res.keys.getLast hne)]
exact hT
have hresA : res.keys = A.take q := by
rw [← hfilT, filter_le_eq_take_countP hAsLT (res.keys.getLast hne), hq]
have hqle : q ≤ A.length := by rw [hq]; exact List.countP_le_length
have hnq : n = q := by
rw [hn, hresA, List.length_take, Nat.min_eq_left hqle]
have hcnt : cB = cE + (between db r.end_.key r.begin.key).length := by
rw [hcB, hcE]
simpa [cnt, hl] using cnt_eq_add_between db (le_of_lt hcross)
have hn_le_e : n ≤ e := by
by_contra hlt
have hne : e < n := by omega
have hz : e - n = 0 := Nat.sub_eq_zero_of_le (le_of_lt hne)
have hle0 : intervalCard r.end_.key r.begin.key ≤ 0 := by simpa [hz] using hcard
have hzero : intervalCard r.end_.key r.begin.key = 0 :=
le_antisymm hle0 zero_le
exact absurd (intervalCard_eq_zero_iff.mp hzero) (not_le.mpr hcross)
have hgn : (between db r.end_.key r.begin.key).length + n ≤ e := by
have hg : (((between db r.end_.key r.begin.key).length : ℕ) : ℕ∞) ≤
(((e - n : ℕ)) : ℕ∞) := by
refine le_trans (between_length_le_intervalCard (db := db) (le_of_lt hcross)) ?_
simpa [e, n, hn] using hcard
have hg' : (between db r.end_.key r.begin.key).length ≤ e - n := by
exact_mod_cast hg
omega
have hAn : n ≤ A.length := by
rw [hn, hresA, List.length_take]
exact Nat.min_le_right _ _
have hcBl : cB ≤ l.length := by rw [hcB]; exact List.countP_le_length
have hlen : cB + n ≤ l.length := by
rw [hA_eq, List.length_drop] at hAn
omega
have hm_ge : n ≤ min (cE + e) l.length - cB := by
have h1 : cB + n ≤ cE + e := by rw [hcnt]; omega
have h3 : cB + n ≤ min (cE + e) l.length := le_min h1 hlen
omega
rw [completeKeys_eq_filter_take_of_offset_one (db := db) hrev hbegin
(by omega : 1 ≤ r.end_.offset)]
rw [← hA]
rw [filter_take_eq_take_min (p := fun k : Key => decide (k ≤ res.keys.getLast hne))
(h := filter_le_eq_take_countP hAsLT (res.keys.getLast hne))
(m := min (cE + e) l.length - cB)]
have hmin : min (min (cE + e) l.length - cB) q = n := by
rw [← hnq]
exact Nat.min_eq_right hm_ge
rw [hmin, hnq]
exact hresA.symm
rw [key db₁, key db₂, hagree]
private theorem keys_lo_keyAfter_eq_filter_le {db : DB} {lo : WithTop Key} {last : Key} :
(⟨lo, (keyAfter last : Key)⟩ : ConflictRange).keys db =
(db.keys.filter (fun k : Key => decide (lo ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ last)) := by
unfold ConflictRange.keys
rw [show db.keys.filter (fun (k : Key) => decide (lo ≤ (k : WithTop Key) ∧
(k : WithTop Key) < ((keyAfter last : Key) : WithTop Key))) =
db.keys.filter (fun (k : Key) =>
decide ((k : WithTop Key) < ((keyAfter last : Key) : WithTop Key)) &&
decide (lo ≤ (k : WithTop Key))) from
List.filter_congr fun k _ => by rw [Bool.decide_and, Bool.and_comm]]
rw [← List.filter_filter]
apply List.filter_congr
intro k _
rw [decide_eq_decide, WithTop.coe_lt_coe, lt_keyAfter_iff]
private theorem filter_ge_last_eq_filter_of_keys_eq {db : DB} {E B : WithTop Key} {last : Key}
(hEB : E ≤ B) (_hBlast : B ≤ (last : WithTop Key)) :
(db.keys.filter (fun k : Key => decide (B ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ last)) =
((⟨E, (keyAfter last : Key)⟩ : ConflictRange).keys db).filter
(fun k : Key => decide (B ≤ (k : WithTop Key))) := by
rw [keys_lo_keyAfter_eq_filter_le]
simp only [List.filter_filter]
apply List.filter_congr
intro k _
simp only [← Bool.decide_and]
rw [decide_eq_decide]
constructor
· rintro ⟨hl, hB⟩
exact ⟨hB, hl, le_trans hEB hB⟩
· rintro ⟨hB, hl, _⟩
exact ⟨hl, hB⟩
private theorem between_eq_filter_of_keys_eq {db : DB} {E B : WithTop Key} {last : Key}
(_hEB : E ≤ B) (hBlast : B ≤ (last : WithTop Key)) :
between db E B =
((⟨E, (keyAfter last : Key)⟩ : ConflictRange).keys db).filter
(fun k : Key => decide ((k : WithTop Key) < B)) := by
rw [keys_lo_keyAfter_eq_filter_le]
simp only [List.filter_filter]
unfold between
rw [show db.keys.filter (fun k : Key => decide (E ≤ (k : WithTop Key) ∧ (k : WithTop Key) < B)) =
db.keys.filter (fun k : Key => decide ((k : WithTop Key) < B) && decide (E ≤ (k : WithTop
Key))) from
List.filter_congr fun k _ => by rw [Bool.decide_and, Bool.and_comm]]
apply List.filter_congr
intro k _
simp only [← Bool.decide_and]
rw [decide_eq_decide]
constructor
· rintro ⟨hkB, hE⟩
have hklt : (k : WithTop Key) < (last : WithTop Key) := lt_of_lt_of_le hkB hBlast
exact ⟨hkB, le_of_lt (WithTop.coe_lt_coe.mp hklt), hE⟩
· rintro ⟨hkB, _, hE⟩
exact ⟨hkB, hE⟩
/-- Agreement on `[E, keyAfter last)` determines the complete keys filtered at or
below `last`, for a forward offset-one read with `E ≤ begin.key`. -/
theorem completeKeys_filter_le_eq_of_agree_crossed {r : RangeRead} {last : Key}
(hrev : r.reverse = false) (hbegin : r.begin.offset = 1) (hend : 1 ≤ r.end_.offset)
(hEB : r.end_.key ≤ r.begin.key) (hBlast : r.begin.key ≤ (last : WithTop Key))
{db₁ db₂ : DB}
(hagree : (⟨r.end_.key, (keyAfter last : Key)⟩ : ConflictRange).keys db₁ =
(⟨r.end_.key, (keyAfter last : Key)⟩ : ConflictRange).keys db₂) :
(RangeRead.completeKeys db₁ r).filter (fun k : Key => decide (k ≤ last)) =
(RangeRead.completeKeys db₂ r).filter (fun k : Key => decide (k ≤ last)) := by
have hC (db : DB) :
(db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ last)) =
((⟨r.end_.key, (keyAfter last : Key)⟩ : ConflictRange).keys db).filter
(fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) :=
filter_ge_last_eq_filter_of_keys_eq (db := db) hEB hBlast
have hG (db : DB) :
between db r.end_.key r.begin.key =
((⟨r.end_.key, (keyAfter last : Key)⟩ : ConflictRange).keys db).filter
(fun k : Key => decide ((k : WithTop Key) < r.begin.key)) :=
between_eq_filter_of_keys_eq (db := db) hEB hBlast
have hCeq : (db₁.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ last)) =
(db₂.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ last)) := by
rw [hC db₁, hC db₂, hagree]
have hGeq : between db₁ r.end_.key r.begin.key = between db₂ r.end_.key r.begin.key := by
rw [hG db₁, hG db₂, hagree]
let e := (r.end_.offset - 1).toNat
have hformula (db : DB) :
(RangeRead.completeKeys db r).filter (fun k : Key => decide (k ≤ last)) =
(((db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ last))).take
(min (e - (between db r.end_.key r.begin.key).length)
(((db.keys.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key)))).filter
(fun k : Key => decide (k ≤ last))).length))) := by
set l := db.keys with hl
set A := l.filter (fun k : Key => decide (r.begin.key ≤ (k : WithTop Key))) with hA
set C := A.filter (fun k : Key => decide (k ≤ last)) with hCdef
set q := A.countP (fun k : Key => decide (k ≤ last)) with hq
have hls : l.SortedLT := by rw [hl]; exact db.sorted
have hAs : A.SortedLT := by
rw [hA]
exact List.sortedLT_iff_pairwise.mpr (hls.pairwise.filter _)
have hCtake : C = A.take q := by
rw [hCdef, hq]
exact filter_le_eq_take_countP hAs last
have hqC : C.length = q := by rw [hCtake, List.length_take, Nat.min_eq_left (by rw [hq]; exact
List.countP_le_length)]
have hCAlen : C.length ≤ A.length := by rw [hCtake]; exact (List.take_sublist q A).length_le
have hcB : l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) =
l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) +
(between db r.end_.key r.begin.key).length := by
simpa [cnt, hl] using cnt_eq_add_between db hEB
have hM : min (l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) + e)
l.length - l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) =
min (e - (between db r.end_.key r.begin.key).length) A.length := by
have hA_eq : A = l.drop (l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)))
:= by
rw [hA]
have hdrop := filter_not_lt_eq_drop_countP hls r.begin.key
rw [← hdrop]
apply List.filter_congr
intro k _
rw [decide_eq_decide]
exact not_lt.symm
have hAlen : A.length = l.length - l.countP (fun k : Key => decide ((k : WithTop Key) <
r.begin.key)) := by
rw [hA_eq, List.length_drop]
rw [hcB, hAlen]
omega
have htake := completeKeys_eq_filter_take_of_offset_one (db := db) hrev hbegin hend
rw [htake]
rw [filter_take_eq_take_min (p := fun k : Key => decide (k ≤ last))
(h := filter_le_eq_take_countP hAs last)
(m := min (l.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) + e)
l.length - l.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)))]
rw [hM]
change A.take (min (min (e - (between db r.end_.key r.begin.key).length) A.length) q) =
C.take (min (e - (between db r.end_.key r.begin.key).length) C.length)
have hqA : q ≤ A.length := by rw [← hqC]; exact hCAlen
have hminA : min A.length q = q := Nat.min_eq_right hqA
rw [Nat.min_assoc, hminA]
rw [hqC, hCtake, List.take_take]
rw [Nat.min_assoc, Nat.min_self]
rw [hformula db₁, hformula db₂, hCeq, hGeq]
/-- A compatible forward offset-one result's last key is at or above the begin key. -/
theorem le_begin_key_of_compatible_crossed {db : DB} {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hbegin : r.begin.offset = 1)
(hend : 1 ≤ r.end_.offset) (hne : res.keys ≠ [])
(hc : RangeRead.Compatible db r res) :
r.begin.key ≤ ((res.keys.getLast hne : Key) : WithTop Key) := by
have htake := completeKeys_eq_filter_take_of_offset_one (db := db) hrev hbegin hend
have hmem : res.keys.getLast hne ∈ RangeRead.completeKeys db r :=
(RangeRead.compatible_keys_prefix hc).subset (List.getLast_mem hne)
rw [htake] at hmem
have := List.mem_of_mem_take hmem
exact decide_eq_true_eq.mp (List.mem_filter.mp this).2
/-- **E-branch soundness for the forward truncated crossed read.** When the gap
`[end_.key, begin_.key)` is too small to absorb the remaining overshoot, the wider
range `[end_.key, keyAfter (last reported))` is sound: agreement on it fixes the
reported prefix of the complete keys. -/
theorem sound_truncatedRange_of_crossed_E {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hmore : res.more = true) (hne : res.keys ≠ [])
(hbegin : r.begin.offset = 1) (hcross : r.end_.key < r.begin.key)
(hend : 2 ≤ r.end_.offset) :
Sound r res ⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩ := by
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
rw [hlast]
intro db₁ db₂ hagree
constructor
· intro hc₁
have hBlast := le_begin_key_of_compatible_crossed (db := db₁) hrev hbegin (by omega) hne hc₁
have hceq := completeKeys_filter_le_eq_of_agree_crossed (r := r)
(last := res.keys.getLast hne) hrev hbegin (by omega) (le_of_lt hcross) hBlast hagree
rw [compatible_iff_truncated_keys (db := db₁) hrev hmore hne] at hc₁
rw [compatible_iff_truncated_keys (db := db₂) hrev hmore hne]
refine ⟨hc₁.1, ?_⟩
rw [← hceq]
exact hc₁.2
· intro hc₂
have hBlast := le_begin_key_of_compatible_crossed (db := db₂) hrev hbegin (by omega) hne hc₂
have hceq := completeKeys_filter_le_eq_of_agree_crossed (r := r)
(last := res.keys.getLast hne) hrev hbegin (by omega) (le_of_lt hcross) hBlast hagree
rw [compatible_iff_truncated_keys (db := db₂) hrev hmore hne] at hc₂
rw [compatible_iff_truncated_keys (db := db₁) hrev hmore hne]
refine ⟨hc₂.1, ?_⟩
rw [hceq]
exact hc₂.2
private theorem enat_succ_le_of_lt {s : ℕ} {h : ℕ∞} (hs : (s : ℕ∞) < h) :
((s + 1 : ℕ) : ℕ∞) ≤ h := by
cases h with
| top => exact le_top
| coe n =>
rw [ENat.natCast_lt_natCast] at hs
exact_mod_cast Nat.succ_le_of_lt hs
/-- **Gap-key necessity for the forward truncated crossed read.** When the gap
`[end_.key, begin_.key)` is too small to absorb the remaining overshoot, every key in
the gap is necessary: a witness with `s` gap keys whose complete window is exactly the
reported prefix becomes incompatible once the target gap key is inserted, because the
window shrinks by one and drops the last reported key. -/
theorem necessary_of_mem_gap_crossed_truncated {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 = 1)
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
(hlt : (((r.end_.offset - 1).toNat - res.keys.length : ℕ) : ℕ∞) <
intervalCard r.end_.key r.begin.key)
(hkE : r.end_.key ≤ (k : WithTop Key))
(hkB : (k : WithTop Key) < r.begin.key) :
Necessary r res k := by
set t : ℕ := res.keys.length with htdef
set eo : ℕ := (r.end_.offset - 1).toNat with heodef
set s : ℕ := eo - t with hsdef
obtain ⟨db₀, hcomp₀⟩ := hread
have hpre₀ : res.keys <+: RangeRead.completeKeys db₀ r :=
RangeRead.compatible_keys_prefix hcomp₀
have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev
-- The reported keys all lie at or above `begin.key`.
have hall_ge : ∀ x ∈ res.keys, r.begin.key ≤ (x : WithTop Key) := by
intro x hx
have htake := completeKeys_eq_filter_take_of_offset_one (db := db₀) hrev hbegin
(by omega : 1 ≤ r.end_.offset)
have hmem : x ∈ RangeRead.completeKeys db₀ r := hpre₀.subset hx
rw [htake] at hmem
exact decide_eq_true_eq.mp (List.mem_filter.mp (List.mem_of_mem_take hmem)).2
have hlast_ge_B : r.begin.key ≤ (res.keys.getLast hne : WithTop Key) :=
hall_ge _ (List.getLast_mem hne)
-- `t ≤ eo`, so `eo = s + t`.
have ht_le_eo : t ≤ eo := by
have hlen₀ := completeKeys_length_of_offset_one (db := db₀) hrev hbegin
(by omega : 1 ≤ r.end_.offset)
have htl : t ≤ (RangeRead.completeKeys db₀ r).length := by
rw [htdef]; exact hpre₀.length_le
rw [hlen₀] at htl
set a := db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.end_.key)) with ha
set bb := db₀.keys.countP (fun k : Key => decide ((k : WithTop Key) < r.begin.key)) with hbb
set N := db₀.keys.length with hN
have hmono : a ≤ bb := by
rw [ha, hbb]
simpa [cnt] using cnt_le_cnt_of_le db₀ (le_of_lt hcross)
have hmin : min (a + eo) N ≤ a + eo := min_le_left _ _
omega
have heo : eo = s + t := by
rw [hsdef]
exact (Nat.sub_add_cancel ht_le_eo).symm
have hcard : ((s + 1 : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key :=
enat_succ_le_of_lt (s := s) (h := intervalCard r.end_.key r.begin.key) (by
simpa [s, htdef, heodef] using hlt)
obtain ⟨dbH, hHrange, hkH, hHlen⟩ :=
exists_db_keysIn_avoid (B := r.end_.key) (E := r.begin.key) (k := k) (m := s) hcard
have hHgeE : ∀ x ∈ dbH.keys, r.end_.key ≤ (x : WithTop Key) :=
fun x hx => (hHrange x hx).1
have hHltB : ∀ x ∈ dbH.keys, (x : WithTop Key) < r.begin.key :=
fun x hx => (hHrange x hx).2
obtain ⟨C, hCge, hCnotin⟩ :=
exists_le_not_mem (res.keys ++ dbH.keys) (res.keys.getLast hne)
have hCnotres : C ∉ res.keys := fun h => hCnotin (List.mem_append_left _ h)
have hCnotH : C ∉ dbH.keys := fun h => hCnotin (List.mem_append_right _ h)
have hCgtRes : ∀ a ∈ res.keys, a < C := by
intro a ha
have hle : a ≤ res.keys.getLast hne :=
(hsort.pairwise.imp le_of_lt).rel_getLast ha
exact lt_of_le_of_ne (le_trans hle hCge) (fun h => hCnotres (h ▸ ha))
have hHltC : ∀ a ∈ dbH.keys, a < C := by
intro a ha
have h1 : (a : WithTop Key) < (C : WithTop Key) :=
lt_of_lt_of_le (hHltB a ha)
(le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
exact WithTop.coe_lt_coe.mp h1
have hHres_lt : ∀ a ∈ dbH.keys, ∀ b ∈ res.keys, a < b :=
fun a ha b hb =>
WithTop.coe_lt_coe.mp (lt_of_lt_of_le (hHltB a ha) (hall_ge b hb))
have hHres_sorted : (dbH.keys ++ res.keys).SortedLT :=
List.sortedLT_append.mpr ⟨dbH.sorted, hsort, hHres_lt⟩
have hsingle : ([C] : List Key).SortedLT := by
rw [List.sortedLT_cons]
exact ⟨by simp, List.sortedLT_nil⟩
have hcrossList : ∀ a ∈ (dbH.keys ++ res.keys), ∀ b ∈ ([C] : List Key), a < b := by
intro a ha b hb
rw [List.mem_singleton] at hb
subst hb
rcases List.mem_append.mp ha with haH | haR
· exact hHltC a haH
· exact hCgtRes a haR
have hlst_sorted : (dbH.keys ++ res.keys ++ [C]).SortedLT :=
List.sortedLT_append.mpr ⟨hHres_sorted, hsingle, hcrossList⟩
let db₂ : DB := ⟨dbH.keys ++ res.keys ++ [C], hlst_sorted⟩
have hdb₂ : db₂.keys = dbH.keys ++ res.keys ++ [C] := rfl
have hfil₂ : db₂.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = res.keys ++ [C] := by
rw [hdb₂, List.filter_append, List.filter_append]
have hHf : dbH.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx
rw [decide_eq_true_eq]
exact not_le.mpr (hHltB x hx)
have hresf : res.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = res.keys := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact hall_ge x hx
have hCf : ([C] : List Key).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = [C] := by
rw [List.filter_eq_self]
intro x hx
rw [List.mem_singleton] at hx
subst hx
rw [decide_eq_true_eq]
exact le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge)
rw [hHf, hresf, hCf]
simp
have hcE₂ : cnt db₂ r.end_.key = 0 := by
apply cnt_eq_zero_of_forall_ge
intro x hx
rw [hdb₂] at hx
rcases List.mem_append.mp hx with hx' | hxC
· rcases List.mem_append.mp hx' with hxH | hxR
· exact hHgeE x hxH
· exact le_trans (le_of_lt hcross) (hall_ge x hxR)
· rw [List.mem_singleton] at hxC
subst hxC
exact le_trans (le_of_lt hcross)
(le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
have hcB₂ : cnt db₂ r.begin.key = s := by
change db₂.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = s
rw [hdb₂, List.countP_append, List.countP_append]
have hHc : dbH.keys.countP
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = dbH.keys.length :=
cnt_eq_length_of_forall_lt dbH hHltB
have hresc : res.keys.countP
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
rw [decide_eq_true_eq]
exact not_lt.mpr (hall_ge x hx)
have hCc : ([C] : List Key).countP
(fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = 0 := by
rw [List.countP_eq_zero]
intro x hx
rw [List.mem_singleton] at hx
subst hx
rw [decide_eq_true_eq]
exact not_lt.mpr (le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
rw [hHc, hresc, hCc, hHlen]
omega
have hn₂ : db₂.keys.length = s + t + 1 := by
rw [hdb₂, List.length_append, List.length_append, hHlen, htdef, List.length_singleton]
have hck₂ : RangeRead.completeKeys db₂ r = res.keys := by
rw [completeKeys_eq_filter_take_of_offset_one hrev hbegin (by omega : 1 ≤ r.end_.offset),
hfil₂]
have hidx : min (cnt db₂ r.end_.key + eo) db₂.keys.length -
cnt db₂ r.begin.key = t := by
rw [hcE₂, hcB₂, hn₂, heo]
omega
have hidx' : min (List.countP (fun x : Key => decide ((x : WithTop Key) < r.end_.key))
db₂.keys + (r.end_.offset - 1).toNat) db₂.keys.length -
List.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) db₂.keys = t := by
simpa [cnt, eo] using hidx
rw [hidx']
have htake : (res.keys ++ [C]).take t = res.keys := by
rw [List.take_append_of_le_length (le_of_eq htdef)]
rw [htdef]
exact List.take_length
exact htake
have hcomp₂ : RangeRead.Compatible db₂ r res := by
refine ⟨hcomp₀.1, Or.inl ⟨hmore, ?_, hne⟩⟩
rw [hck₂]
have hk_db₂ : k ∉ db₂.keys := by
rw [hdb₂]
intro hmem
rcases List.mem_append.mp hmem with hmem' | hmemC
· rcases List.mem_append.mp hmem' with hmemH | hmemR
· exact hkH hmemH
· exact absurd (hall_ge k hmemR) (not_le.mpr hkB)
· rw [List.mem_singleton] at hmemC
have hkC : k = C := hmemC
have h1 : (k : WithTop Key) < (C : WithTop Key) :=
lt_of_lt_of_le hkB (le_trans hlast_ge_B (WithTop.coe_le_coe.mpr hCge))
rw [hkC] at h1
exact (lt_irrefl (C : WithTop Key)) h1
have hcE₁ : cnt (db₂.insert k hk_db₂) r.end_.key = 0 := by
rw [cnt_insert_not_lt db₂ k hk_db₂ (v := r.end_.key) (not_lt.mpr hkE)]
exact hcE₂
have hcB₁ : cnt (db₂.insert k hk_db₂) r.begin.key = s + 1 := by
rw [cnt_insert_lt db₂ k hk_db₂ (v := r.begin.key) hkB, hcB₂]
have hn₁ : (db₂.insert k hk_db₂).keys.length = s + t + 2 := by
rw [DB.insert_keys, List.orderedInsert_length, hn₂]
have hfil₁ : (db₂.insert k hk_db₂).keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) = res.keys ++ [C] := by
have hsingle_filter : List.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) (k :: db₂.keys) =
db₂.keys.filter (fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))) := by
rw [List.filter_cons]
have hkf : decide (r.begin.key ≤ (k : WithTop Key)) = false := by
rw [decide_eq_false_iff_not]
exact not_le.mpr hkB
rw [hkf]
rfl
have hperm : List.Perm ((List.orderedInsert (· ≤ ·) k db₂.keys).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key))))
(db₂.keys.filter (fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))) := by
have h := (List.perm_orderedInsert (· ≤ ·) k db₂.keys).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))
rwa [hsingle_filter] at h
have hs₁ : ((List.orderedInsert (· ≤ ·) k db₂.keys).filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))).SortedLT :=
List.sortedLT_iff_pairwise.mpr ((db₂.insert k hk_db₂).sorted.pairwise.filter _)
have hs₂ : (db₂.keys.filter
(fun x : Key => decide (r.begin.key ≤ (x : WithTop Key)))).SortedLT :=
List.sortedLT_iff_pairwise.mpr (db₂.sorted.pairwise.filter _)
rw [DB.insert_keys]
exact (List.SortedLT.eq_of_mem_iff hs₁ hs₂ (fun x => hperm.mem_iff)).trans hfil₂
have hck₁ : RangeRead.completeKeys (db₂.insert k hk_db₂) r = res.keys.take (t - 1) := by
rw [completeKeys_eq_filter_take_of_offset_one hrev hbegin (by omega : 1 ≤ r.end_.offset),
hfil₁]
have hidx : min (cnt (db₂.insert k hk_db₂) r.end_.key + eo)
(db₂.insert k hk_db₂).keys.length -
cnt (db₂.insert k hk_db₂) r.begin.key = t - 1 := by
rw [hcE₁, hcB₁, hn₁, heo]
omega
have hidx' : min (List.countP (fun x : Key => decide ((x : WithTop Key) < r.end_.key))
(db₂.insert k hk_db₂).keys + (r.end_.offset - 1).toNat)
(db₂.insert k hk_db₂).keys.length -
List.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key))
(db₂.insert k hk_db₂).keys = t - 1 := by
simpa [cnt, eo] using hidx
rw [hidx']
rw [List.take_append_of_le_length (by omega : t - 1 ≤ res.keys.length)]
have hnot₁ : ¬ RangeRead.Compatible (db₂.insert k hk_db₂) r res := by
intro hc
rw [compatible_iff_truncated_keys (db := db₂.insert k hk_db₂) hrev hmore hne] at hc
rw [hck₁] at hc
have hf : List.filter (fun k : Key => decide (k ≤ res.keys.getLast hne))
(res.keys.take (t - 1)) = res.keys.take (t - 1) := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact (hsort.pairwise.imp le_of_lt).rel_getLast (List.mem_of_mem_take hx)
rw [hf] at hc
have heq : res.keys.take (t - 1) = res.keys := hc.2
have hlen := congrArg List.length heq
rw [List.length_take, htdef] at hlen
have htpos : 0 < t := by rw [htdef]; exact List.length_pos_of_ne_nil hne
omega
intro cr hs
by_contra hkcr
have hagree : AgreeOn cr db₂ (db₂.insert k hk_db₂) :=
(ConflictRange.keys_insert_of_not_mem cr db₂ hk_db₂ hkcr).symm
exact hnot₁ ((hs db₂ (db₂.insert k hk_db₂) hagree).mp hcomp₂)
/-- A `WithTop Key` that is not `⊤` is a coerced genuine key. -/
private theorem begin_key_exists_coe {r : RangeRead}
(h : r.begin.key ≠ (⊤ : WithTop Key)) :
∃ v : Key, r.begin.key = (↑v : WithTop Key) := by
cases hk : r.begin.key with
| top => exact absurd hk h
| coe v => exact ⟨v, rfl⟩
/-- **Forward truncated crossed closed form, small-gap branch.** If the gap
`[end_.key, begin_.key)` holds fewer than the remaining overshoot `e - |res|` keys,
the minimal range is `[end_.key, keyAfter (last reported))`. -/
theorem minimal_truncatedForward_of_crossed {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset = 1)
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
(hsmall : (((r.end_.offset - 1).toNat - res.keys.length : ℕ) : ℕ∞) <
intervalCard r.end_.key r.begin.key) :
Minimal r res ⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩ := by
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
rw [hlast]
rw [minimal_iff_sound_and_necessaryRange]
refine ⟨?_, ?_⟩
· have hs := sound_truncatedRange_of_crossed_E (r := r) (res := res)
hrev hmore hne hbegin hcross hend
rwa [hlast] at hs
· intro k hkE hklt
have hklast : k ≤ res.keys.getLast hne :=
(lt_keyAfter_iff k (res.keys.getLast hne)).mp (WithTop.coe_lt_coe.mp hklt)
by_cases hkB : (k : WithTop Key) < r.begin.key
· exact necessary_of_mem_gap_crossed_truncated hread hmore hrev hne hbegin hcross hend
hsmall hkE hkB
· have hkBle : r.begin.key ≤ (k : WithTop Key) := not_lt.mp hkB
obtain ⟨db₀, hcomp₀⟩ := hread
have hall_ge : ∀ x ∈ res.keys, r.begin.key ≤ (x : WithTop Key) := by
intro x hx
have htake := completeKeys_eq_filter_take_of_offset_one (db := db₀) hrev hbegin
(by omega : 1 ≤ r.end_.offset)
have hmem : x ∈ RangeRead.completeKeys db₀ r :=
(RangeRead.compatible_keys_prefix hcomp₀).subset hx
rw [htake] at hmem
exact decide_eq_true_eq.mp (List.mem_filter.mp (List.mem_of_mem_take hmem)).2
have hbk_ne_top : r.begin.key ≠ (⊤ : WithTop Key) := by
obtain ⟨x, hx⟩ : ∃ x, x ∈ res.keys := by
cases h : res.keys with
| nil => exact absurd h hne
| cons a tl => exact ⟨a, by simp⟩
have h1 : r.begin.key ≤ (x : WithTop Key) := hall_ge x hx
intro htop
rw [htop] at h1
exact not_le.mpr (WithTop.coe_lt_top x) h1
obtain ⟨v, hv⟩ := begin_key_exists_coe hbk_ne_top
have hbegin_nec : Necessary r res v :=
necessary_begin_key ⟨db₀, hcomp₀⟩ hrev (List.length_pos_of_ne_nil hne) (by omega) hv
have hvk : v ≤ k := WithTop.coe_le_coe.mp (hv ▸ hkBle)
have hlast_nec : Necessary r res (res.keys.getLast hne) :=
necessary_of_mem_result ⟨db₀, hcomp₀⟩ (List.getLast_mem hne)
exact hbegin_nec.of_between hlast_nec hvk hklast
/-- **Large-gap branch minimality for the forward truncated crossed read.** When the
gap `[end_.key, begin_.key)` holds at least the remaining overshoot, the smaller range
`[begin_.key, keyAfter (last reported))` is minimal. -/
theorem minimal_truncatedRange_of_crossed_B {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset = 1)
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset)
(hbig : intervalCard r.end_.key r.begin.key ≤
(((r.end_.offset - 1).toNat - res.keys.length : ℕ) : ℕ∞)) :
Minimal r res (truncatedRange r (res.keys.getLastD ([] : Key))) := by
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
rw [hlast]
rw [minimal_iff_sound_and_necessaryRange]
refine ⟨?_, ?_⟩
· have hs := sound_truncatedRange_of_crossed_B (r := r) (res := res)
hrev hmore hne hbegin hcross hend hbig
rwa [hlast] at hs
· intro k hkB hklt
have hklast : k ≤ res.keys.getLast hne :=
(lt_keyAfter_iff k (res.keys.getLast hne)).mp (WithTop.coe_lt_coe.mp hklt)
obtain ⟨db₀, hcomp₀⟩ := hread
have hall_ge : ∀ x ∈ res.keys, r.begin.key ≤ (x : WithTop Key) := by
intro x hx
have htake := completeKeys_eq_filter_take_of_offset_one (db := db₀) hrev hbegin
(by omega : 1 ≤ r.end_.offset)
have hmem : x ∈ RangeRead.completeKeys db₀ r :=
(RangeRead.compatible_keys_prefix hcomp₀).subset hx
rw [htake] at hmem
exact decide_eq_true_eq.mp (List.mem_filter.mp (List.mem_of_mem_take hmem)).2
have hbk_ne_top : r.begin.key ≠ (⊤ : WithTop Key) := by
obtain ⟨x, hx⟩ : ∃ x, x ∈ res.keys := by
cases h : res.keys with
| nil => exact absurd h hne
| cons a tl => exact ⟨a, by simp⟩
have h1 : r.begin.key ≤ (x : WithTop Key) := hall_ge x hx
intro htop
rw [htop] at h1
exact not_le.mpr (WithTop.coe_lt_top x) h1
obtain ⟨v, hv⟩ := begin_key_exists_coe hbk_ne_top
have hbegin_nec : Necessary r res v :=
necessary_begin_key ⟨db₀, hcomp₀⟩ hrev (List.length_pos_of_ne_nil hne) (by omega) hv
have hvk : v ≤ k := WithTop.coe_le_coe.mp (hv ▸ hkB)
have hlast_nec : Necessary r res (res.keys.getLast hne) :=
necessary_of_mem_result ⟨db₀, hcomp₀⟩ (List.getLast_mem hne)
exact hbegin_nec.of_between hlast_nec hvk hklast
/-- The forward truncated crossed closed form: the small-gap branch keeps the end key,
the large-gap branch starts at the begin key. -/
noncomputable def truncatedForwardClosed (r : RangeRead) (res : Result) : ConflictRange :=
if intervalCard r.end_.key r.begin.key ≤
(((r.end_.offset - 1).toNat - res.keys.length : ℕ) : ℕ∞) then
truncatedRange r (res.keys.getLastD ([] : Key))
else
⟨r.end_.key, (keyAfter (res.keys.getLastD ([] : Key)) : WithTop Key)⟩
/-- The forward truncated crossed closed form is minimal on the whole region. -/
theorem minimal_truncatedForwardClosed_of_crossed {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hne : res.keys ≠ []) (hbegin : r.begin.offset = 1)
(hcross : r.end_.key < r.begin.key) (hend : 2 ≤ r.end_.offset) :
Minimal r res (truncatedForwardClosed r res) := by
unfold truncatedForwardClosed
by_cases hbig : intervalCard r.end_.key r.begin.key ≤
(((r.end_.offset - 1).toNat - res.keys.length : ℕ) : ℕ∞)
· rw [ite_eq_left hbig]
exact minimal_truncatedRange_of_crossed_B hread hmore hrev hne hbegin hcross hend hbig
· rw [ite_eq_right hbig]
exact minimal_truncatedForward_of_crossed hread hmore hrev hne hbegin hcross hend
(not_le.mp hbig)
/-- The forward truncated crossed closed form denotes the same key set as the general
conflict range. -/
theorem truncatedForwardClosed_toSet_eq_general {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hbegin : r.begin.offset = 1) (hcross : r.end_.key < r.begin.key)
(hend : 2 ≤ r.end_.offset) :
(truncatedForwardClosed r res).toSet = (conflictRangeGeneral r res).toSet := by
obtain ⟨db₀, hcomp₀⟩ := hread
have hread' : Readable r res := ⟨db₀, hcomp₀⟩
exact (minimal_truncatedForwardClosed_of_crossed hread' hmore hrev
(RangeRead.compatible_ne_nil_of_more hcomp₀ hmore) hbegin hcross hend).toSet_eq
(conflictRangeGeneral_minimal hread')
/-- The same identification with the executable algorithm. -/
theorem truncatedForwardClosed_toSet_eq_simple {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hbegin : r.begin.offset = 1) (hcross : r.end_.key < r.begin.key)
(hend : 2 ≤ r.end_.offset) :
(truncatedForwardClosed r res).toSet = (simpleConflictRange r res).toSet := by
obtain ⟨db₀, hcomp₀⟩ := hread
have hread' : Readable r res := ⟨db₀, hcomp₀⟩
exact (minimal_truncatedForwardClosed_of_crossed hread' hmore hrev
(RangeRead.compatible_ne_nil_of_more hcomp₀ hmore) hbegin hcross hend).toSet_eq
(simpleConflictRange_minimal hread')
end FormalConflictRange