Files
conflict-range/FormalConflictRange/NegCrossTruncRevBeginTop.lean

332 lines
17 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.NegCrossTruncRevFinite
/-!
# Reversed crossed negative-begin truncated cells with a sentinel begin key
This module closes the reversed crossed negative-begin truncated cell whose begin
selector targets the sentinel `⊤` and whose end offset is at most one. The minimal
range is `[last reported, ⊤)`, the top range at the reported last key.
Soundness reuses the reduction to the read whose begin is the reported last at offset
one: the begin-anchor count bound keeps the resolved begin at or below the reported last
under agreement on `[last, ⊤)`, so the complete keys are fixed.
Necessity is uniform in the key. If a sound range omitted a key `k ≥ last`, then its
end must be finite: a sound range ending at `⊤` contains `last` (a reported key), hence
starts at or below `last ≤ k`, so it cannot omit `k`. With a finite end, inserting
fresh keys above both the range's end and `last` (there are arbitrarily many such keys)
raises the begin anchor past `last` without moving `last` in the database, so the
reported keys stop being a prefix of the complete keys.
-/
namespace FormalConflictRange
/-- Agreement on `[a, ⊤)` restricts to agreement on `[a, b)` for any `b`. -/
theorem agreeOn_top_narrow {db₁ db₂ : DB} {a b : WithTop Key}
(h : AgreeOn ⟨a, (⊤ : WithTop Key)⟩ db₁ db₂) : AgreeOn ⟨a, b⟩ db₁ db₂ := by
have hp : ∀ k : Key, decide (a ≤ ((k : Key) : WithTop Key) ∧
((k : Key) : WithTop Key) < (⊤ : WithTop Key)) =
decide (a ≤ ((k : Key) : WithTop Key)) := by
intro k
rw [decide_eq_decide]
exact ⟨fun h => h.1, fun h => ⟨h, WithTop.coe_lt_top k⟩⟩
have h' : db₁.keys.filter (fun k : Key => decide (a ≤ ((k : Key) : WithTop Key))) =
db₂.keys.filter (fun k : Key => decide (a ≤ ((k : Key) : WithTop Key))) := by
unfold AgreeOn ConflictRange.keys at h
simpa only [hp] using h
have hstep : ∀ l : List Key,
l.filter (fun k : Key => decide (a ≤ ((k : Key) : WithTop Key) ∧
((k : Key) : WithTop Key) < b)) =
(l.filter (fun k : Key => decide (a ≤ ((k : Key) : WithTop Key)))).filter
(fun k : Key => decide (((k : Key) : WithTop Key) < b)) := by
intro l
rw [List.filter_filter]
apply List.filter_congr
intro k _
simp only [Bool.decide_and, Bool.and_comm]
unfold AgreeOn ConflictRange.keys
rw [hstep db₁.keys, hstep db₂.keys, h']
/-- **Soundness of the top range at the reported last in the sentinel-begin reversed
truncated cell.** Agreement on `[last, ⊤)` fixes the begin resolution at or below
`last`, hence fixes the complete keys up to their prefix. -/
theorem sound_topOfLast_of_negCross_trunc_rev_beginTop {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = true)
(hne : res.keys ≠ []) (hend : r.end_.offset ≤ 1)
(hB : r.begin.key = (⊤ : WithTop Key)) :
Sound r res (topOfLast (res.keys.getLast hne)) := by
set L : Key := res.keys.getLast hne with hLdef
have hLmem : L ∈ res.keys := by rw [hLdef]; exact List.getLast_mem hne
have hcross : ((L : Key) : WithTop Key) < r.begin.key := by
rw [hB]; exact WithTop.coe_lt_top L
obtain ⟨db₀, hcomp₀⟩ := hread
let r' : RangeRead :=
{ r with begin := { key := ((L : Key) : WithTop Key), offset := 1 } }
have hr'_rev : r'.reverse = true := by simp [r', hrev]
have hr'_end : r'.end_ = r.end_ := rfl
have hr'_beg : r'.begin = ({ key := ((L : Key) : WithTop Key), offset := 1 } : Selector) :=
rfl
have hr'_off : r'.begin.offset = 1 := rfl
have hreduce : ∀ (db : DB), RangeRead.Compatible db r res →
RangeRead.Compatible db r' res := by
intro db hcomp
have hfil : (RangeRead.completeKeys db r).filter (fun k => decide (L ≤ k)) =
res.keys :=
(compatible_iff_truncated_keys_rev (db := db) hrev hmore hne).mp hcomp |>.2
have hLfilt : L ∈ (RangeRead.completeKeys db r).filter (fun k => decide (L ≤ k)) := by
rw [hfil]; exact hLmem
have hrb : resolve db r.begin ≤ ((L : Key) : WithTop Key) :=
(RangeRead.mem_completeKeys.mp (List.mem_filter.mp hLfilt).1).2.1
have hLdb : L ∈ db.keys := RangeRead.compatible_keys_subset hcomp hLmem
have hres' : resolve db r'.begin = ((L : Key) : WithTop Key) := by
rw [hr'_beg]; exact resolve_offset_one_key_of_mem hLdb
have hLck_filter : (RangeRead.completeKeys db r').filter (fun k => decide (L ≤ k)) =
RangeRead.completeKeys db r' := by
rw [List.filter_eq_self]
intro k hk
rw [decide_eq_true_eq]
have hk' := (RangeRead.mem_completeKeys.mp hk).2.1
exact WithTop.coe_le_coe.mp (by rwa [hres'] at hk')
have hck' : RangeRead.completeKeys db r' = res.keys := by
rw [← hLck_filter]
exact (completeKeys_filter_ge_eq_of_both_le (db := db) (r₁ := r) (r₂ := r')
hrev hr'_rev hr'_end hrb (le_of_eq hres')).symm.trans hfil
refine ⟨by simpa [r', RangeRead.withinLimit] using hcomp.1, Or.inl ⟨hmore, ?_, hne⟩⟩
rw [hck']
have hread' : Readable r' res := ⟨db₀, hreduce db₀ hcomp₀⟩
have hgetLastD : res.keys.getLastD ([] : Key) = L := by
rw [hLdef, List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
have hmin' : Minimal r' res (truncatedRangeRev r L) := by
rcases lt_or_eq_of_le hend with hlt | heq
· have hle : r.end_.offset ≤ 0 := by omega
have hm := minimal_truncatedRangeRev_of_end_offset_nonpos (r := r') hread' hmore
hr'_rev hr'_off (by simpa [r'] using hle)
rwa [hgetLastD] at hm
· have hm := minimal_truncatedRangeRev_of_offset_one (r := r') hread' hmore
hr'_rev hr'_off heq
rwa [hgetLastD] at hm
have hS' : Sound r' res (truncatedRangeRev r L) := hmin'.sound
have step : ∀ db db', AgreeOn (topOfLast L) db db' →
RangeRead.Compatible db r res → RangeRead.Compatible db' r res := by
intro db db' hag' hcomp
have hcomp' : RangeRead.Compatible db r' res := hreduce db hcomp
have hag'' : AgreeOn (truncatedRangeRev r L) db db' := agreeOn_top_narrow hag'
have hcomp'' : RangeRead.Compatible db' r' res := (hS' db db' hag'').mp hcomp'
have hfil : (RangeRead.completeKeys db r).filter (fun k => decide (L ≤ k)) =
res.keys :=
(compatible_iff_truncated_keys_rev (db := db) hrev hmore hne).mp hcomp |>.2
have hbound : ((between db ((L : Key) : WithTop Key) r.begin.key).length : Int) +
r.begin.offset - 1 ≤ 0 :=
between_add_offset_le_one (db := db) hcomp hmore hrev hne hcross
-- the agreement, restricted to the stored keys at or above `L`
have hfilEq : db'.keys.filter (fun k => decide (L ≤ k)) =
db.keys.filter (fun k => decide (L ≤ k)) := by
have h := hag'
unfold AgreeOn at h
rw [topOfLast_keys, topOfLast_keys] at h
exact h.symm
have hbetween_eq : between db' ((L : Key) : WithTop Key) r.begin.key =
between db ((L : Key) : WithTop Key) r.begin.key := by
rw [hB]
unfold between
simpa [WithTop.coe_le_coe] using hfilEq
have hbound' : ((between db' ((L : Key) : WithTop Key) r.begin.key).length : Int) +
r.begin.offset - 1 ≤ 0 := by
rw [hbetween_eq]; exact hbound
have hLdb : L ∈ db.keys := RangeRead.compatible_keys_subset hcomp hLmem
have hLdb' : L ∈ db'.keys := by
have hmem : L ∈ db'.keys.filter (fun k => decide (L ≤ k)) := by
rw [hfilEq]
exact List.mem_filter.mpr ⟨hLdb, by simp⟩
exact (List.mem_filter.mp hmem).1
have hrb' : resolve db' r.begin ≤ ((L : Key) : WithTop Key) :=
resolve_begin_le_of_between_bound hLdb' hcross hbound'
have hres'_db' : resolve db' r'.begin = ((L : Key) : WithTop Key) := by
rw [hr'_beg]; exact resolve_offset_one_key_of_mem hLdb'
rw [compatible_iff_truncated_keys_rev (db := db') hrev hmore hne]
refine ⟨by simpa [r', RangeRead.withinLimit] using hcomp''.1, ?_⟩
have h1 := completeKeys_filter_ge_eq_resolve_end (db := db') (r := r) hrev hrb'
have h2' := completeKeys_filter_ge_eq_resolve_end (db := db') (r := r') hr'_rev
(le_of_eq hres'_db')
have h2 := (compatible_iff_truncated_keys_rev (db := db') hr'_rev hmore hne).mp
hcomp'' |>.2
rw [h1, ← h2']
exact h2
intro db₁ db₂ hagree
exact ⟨step db₁ db₂ hagree, step db₂ db₁ hagree.symm⟩
/-- **Necessity of every key at or above the reported last in the sentinel-begin
reversed truncated cell.** A sound range omitting such a key must end below `⊤`;
inserting fresh keys above its end and above the reported last then breaks the reported
prefix by lifting the begin resolution alone. -/
theorem necessary_of_ge_last_of_negCross_trunc_rev_beginTop {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = true)
(hne : res.keys ≠ []) (_hbeg : r.begin.offset < 0)
(hB : r.begin.key = (⊤ : WithTop Key)) {k : Key}
(hkL : ((res.keys.getLast hne : Key) : WithTop Key) ≤ ((k : Key) : WithTop Key)) :
Necessary r res k := by
set L : Key := res.keys.getLast hne with hLdef
have hLmem : L ∈ res.keys := by rw [hLdef]; exact List.getLast_mem hne
intro cr hs
by_contra hkcr
have hread' := hread
obtain ⟨db₀, hcomp₀⟩ := hread
-- a sound range ending at `⊤` contains `last`, hence cannot omit `k ≥ last`
have hLcr : L ∈ cr := necessary_of_mem_result hread' hLmem cr hs
have hL_lt_end : ((L : Key) : WithTop Key) < cr.end_ := (ConflictRange.mem_iff.mp hLcr).2
have hcr_end_lt_top : cr.end_ < (⊤ : WithTop Key) := by
by_contra h
have htop : cr.end_ = (⊤ : WithTop Key) := le_antisymm le_top (le_of_not_gt h)
have hk_lt_begin : ((k : Key) : WithTop Key) < cr.begin := by
have hnot : ¬ (cr.begin ≤ ((k : Key) : WithTop Key)) := by
intro hb
exact hkcr (ConflictRange.mem_iff.mpr ⟨hb, by rw [htop]; exact WithTop.coe_lt_top k⟩)
exact lt_of_not_ge hnot
have hbegin_le_L : cr.begin ≤ ((L : Key) : WithTop Key) := (ConflictRange.mem_iff.mp hLcr).1
exact (not_lt_of_ge hkL) (lt_of_lt_of_le hk_lt_begin hbegin_le_L)
-- a key above every stored key
have hexU : ∃ U : Key, ∀ x ∈ db₀.keys, x < U := by
have hlist : ∀ l : List Key, ∃ U : Key, ∀ x ∈ l, x < U := by
intro l
induction l with
| nil => exact ⟨[], by simp⟩
| cons a t ih =>
obtain ⟨U, hU⟩ := ih
refine ⟨max (keyAfter a) U, ?_⟩
intro x hx
rcases List.mem_cons.mp hx with hxa | hx
· rw [hxa]; exact lt_of_lt_of_le (keyAfter_self_lt a) (le_max_left _ _)
· exact lt_of_lt_of_le (hU x hx) (le_max_right _ _)
exact hlist db₀.keys
obtain ⟨U, hU⟩ := hexU
-- the insertion threshold, above the range end, above `last`, and above all stored keys
set B : WithTop Key :=
max (max cr.end_ (((keyAfter L : Key)) : WithTop Key)) ((U : Key) : WithTop Key) with hBdef
have hB_lt_top : B < (⊤ : WithTop Key) := by
rw [hBdef]
rw [max_lt_iff, max_lt_iff]
exact ⟨⟨hcr_end_lt_top, WithTop.coe_lt_top _⟩, WithTop.coe_lt_top U⟩
obtain ⟨b, hb⟩ : ∃ b : Key, B = ((b : Key) : WithTop Key) := by
cases hBv : B with
| top => rw [hBv] at hB_lt_top; exact absurd le_top (not_le.mpr hB_lt_top)
| coe b => exact ⟨b, rfl⟩
-- the number of keys to insert
set m : ℕ := (1 - r.begin.offset).toNat with hmdef
have hm_cast : (m : Int) = 1 - r.begin.offset := by
rw [hmdef, Int.toNat_of_nonneg]; omega
have hmpos : 1 ≤ m := by
rw [hmdef]
have : 0 ≤ 1 - r.begin.offset := by omega
omega
obtain ⟨dbJ, hJmem, hJlen⟩ := exists_db_keysIn (B := B) (E := (⊤ : WithTop Key))
(m := m) (by rw [hb, intervalCard_coe_top]; exact le_top)
have hJge : ∀ x ∈ dbJ.keys, B ≤ ((x : Key) : WithTop Key) := fun x hx => (hJmem x hx).1
have hJgtL : ∀ x ∈ dbJ.keys, L < x := by
intro x hx
have h1 : (((keyAfter L : Key)) : WithTop Key) ≤ ((x : Key) : WithTop Key) :=
le_trans (le_trans (le_max_right _ _) (le_max_left _ _)) (hJge x hx)
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le (WithTop.coe_lt_coe.mpr (keyAfter_self_lt L)) h1)
have hJgt_db : ∀ x ∈ db₀.keys, ∀ y ∈ dbJ.keys, x < y := by
intro x hx y hy
have hxU : x < U := hU x hx
have hUle : ((U : Key) : WithTop Key) ≤ B := le_max_right _ _
have : ((U : Key) : WithTop Key) ≤ ((y : Key) : WithTop Key) := le_trans hUle (hJge y hy)
exact lt_of_lt_of_le hxU (WithTop.coe_le_coe.mp this)
have hsorted : (db₀.keys ++ dbJ.keys).SortedLT :=
List.sortedLT_append.mpr ⟨db₀.sorted, dbJ.sorted, hJgt_db⟩
let db₂ : DB := ⟨db₀.keys ++ dbJ.keys, hsorted⟩
have hdb₂_keys : db₂.keys = db₀.keys ++ dbJ.keys := rfl
have hJnotin_cr : ∀ y ∈ dbJ.keys, y ∉ cr := by
intro y hy hycr
have hyge : cr.end_ ≤ ((y : Key) : WithTop Key) :=
le_trans (le_trans (le_max_left _ _) (le_max_left _ _)) (hJge y hy)
exact absurd (ConflictRange.mem_iff.mp hycr).2 (not_lt.mpr hyge)
have hagree : AgreeOn cr db₀ db₂ := by
unfold AgreeOn ConflictRange.keys
rw [hdb₂_keys, List.filter_append]
have hnil : dbJ.keys.filter (fun k : Key => decide (cr.begin ≤ ((k : Key) : WithTop Key) ∧
((k : Key) : WithTop Key) < cr.end_)) = [] := by
apply List.filter_eq_nil_iff.mpr
intro y hy
have hnot : ¬ (cr.begin ≤ ((y : Key) : WithTop Key) ∧
((y : Key) : WithTop Key) < cr.end_) := by
simpa only [ConflictRange.mem_iff] using hJnotin_cr y hy
simpa only [decide_eq_true_eq] using hnot
rw [hnil, List.append_nil]
-- the inserted database is incompatible: the begin resolves above `last`
have hnotcomp : ¬ RangeRead.Compatible db₂ r res := by
intro hcomp₂
have hfil₂ : (RangeRead.completeKeys db₂ r).filter (fun k => decide (L ≤ k)) = res.keys :=
(compatible_iff_truncated_keys_rev (db := db₂) hrev hmore hne).mp hcomp₂ |>.2
have hLck : L ∈ RangeRead.completeKeys db₂ r := by
have : L ∈ (RangeRead.completeKeys db₂ r).filter (fun k => decide (L ≤ k)) := by
rw [hfil₂]; exact hLmem
exact (List.mem_filter.mp this).1
have hrb₂ : resolve db₂ r.begin ≤ ((L : Key) : WithTop Key) :=
(RangeRead.mem_completeKeys.mp hLck).2.1
have hcnt : cnt db₂ r.begin.key = db₀.keys.length + m := by
rw [hB]
unfold cnt
rw [List.countP_eq_length.mpr (by intro x _; simp)]
rw [hdb₂_keys, List.length_append, hJlen]
have hanchor : r.begin.anchor db₂ = (db₀.keys.length : Int) := by
change (cnt db₂ r.begin.key : Int) + r.begin.offset - 1 = (db₀.keys.length : Int)
rw [hcnt]
push_cast [hm_cast]
ring
have hlen₂ : db₂.keys.length = db₀.keys.length + m := by
rw [hdb₂_keys, List.length_append, hJlen]
have hanchor_nonneg : 0 ≤ r.begin.anchor db₂ := by rw [hanchor]; exact Int.natCast_nonneg _
have hlt : (r.begin.anchor db₂).toNat < db₂.keys.length := by
rw [hanchor, hlen₂]
simp only [Int.toNat_natCast]
omega
have hresolve : resolve db₂ r.begin =
((db₂.keys[db₀.keys.length] : Key) : WithTop Key) := by
rw [resolve_eq_getElem hanchor_nonneg hlt]
have hidx : (r.begin.anchor db₂).toNat = db₀.keys.length := by
rw [hanchor]; simp
simp only [hidx]
have hget_gt : L < db₂.keys[db₀.keys.length] := by
have hpos : 0 < dbJ.keys.length := by rw [hJlen]; omega
have hsplit : db₂.keys[db₀.keys.length] = dbJ.keys[0] := by
simp only [hdb₂_keys]
simp
rw [hsplit]
exact hJgtL (dbJ.keys[0]'hpos) (List.getElem_mem hpos)
have hnotle : ¬ (resolve db₂ r.begin ≤ ((L : Key) : WithTop Key)) := by
rw [hresolve]
exact not_le.mpr (WithTop.coe_lt_coe.mpr hget_gt)
exact hnotle hrb₂
exact hnotcomp ((hs db₀ db₂ hagree).mp hcomp₀)
/-- **The reversed crossed negative-begin truncated cell with a sentinel begin key.** -/
abbrev negCrossTruncRevBeginTop (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = true ∧ r.begin.offset < 0 ∧ res.keys ≠ [] ∧
r.end_.offset ≤ 1 ∧ r.begin.key = (⊤ : WithTop Key) ∧ r.end_.key < (⊤ : WithTop Key)
/-- The closed form of the sentinel-begin reversed truncated cell: `[last, ⊤)`. -/
noncomputable def closedFormNegCrossTruncRevBeginTop (_r : RangeRead) (res : Result) :
ConflictRange :=
topOfLast (res.keys.getLastD ([] : Key))
/-- **The sentinel-begin reversed truncated closed form is minimal.** -/
theorem minimal_closedForm_of_negCross_trunc_rev_beginTop {r : RangeRead} {res : Result}
(hread : Readable r res) (h : negCrossTruncRevBeginTop r res) :
Minimal r res (closedFormNegCrossTruncRevBeginTop r res) := by
obtain ⟨hmore, hrev, hbeg, hne, hend, hB, _hE⟩ := h
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
unfold closedFormNegCrossTruncRevBeginTop
rw [hlast]
refine minimal_iff_sound_and_necessary.mpr
⟨sound_topOfLast_of_negCross_trunc_rev_beginTop hread hmore hrev hne hend hB, ?_⟩
intro k hk
exact necessary_of_ge_last_of_negCross_trunc_rev_beginTop hread hmore hrev hne hbeg hB hk.1
end FormalConflictRange