Files
conflict-range/FormalConflictRange/NegCrossTruncRevResidualFiniteOver.lean

710 lines
35 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.NegCrossTruncRevResidualFinite
/-!
# The finite *over* cell of the reversed crossed negative-begin truncated residual
This module starts closing the last reversed crossed negative-begin truncated cell of
the total closed form: the finite branch of the residual on which the reported last lies
strictly above `end_.key`.
The setting is
* `res.more = true`, `r.reverse = true`, `r.begin.offset < 0`, `res.keys ≠ []`;
* `2 ≤ r.end_.offset`;
* `r.end_.key < last` (the reported last `L` is above the end key);
* `last < begin.key` (the begin selector lies above the reported last);
* the finite count `|res.keys| = end_.offset - 1`.
Since all reported keys lie above `end_.key`, the finite count says exactly that the
stored keys in `[end_.key, resolve end_)` are the reported ones. The first structural
fact is that no compatible database stores a key in `[end_.key, last)`.
The main reduction is that compatibility with `r` is the same as compatibility with the
read whose end key is `last` (same offset), *provided* the database stores nothing in
`[end_.key, last)`. The reduced read lies in the already-closed finite under cell, so
minimality transfers. When `begin.key ≤ head`, the capacity condition `finiteUnderCond`
holds automatically, so the upper endpoint is `keyAfter head`; when the head lies below
`begin.key`, the remaining gap keys are supplied by a toggle witness.
-/
namespace FormalConflictRange
/-- A subset of a duplicate-free list is no longer than it. -/
theorem length_le_of_nodup_subset {l₁ l₂ : List Key} (h : l₁.Nodup) (hsub : l₁ ⊆ l₂) :
l₁.length ≤ l₂.length := by
obtain ⟨l, hperm, hsub'⟩ := List.subperm_iff.mp (h.subperm hsub)
calc l₁.length ≤ l.length := hsub'.length_le
_ = l₂.length := hperm.length_eq
/-- **No stored key lies in `[end_.key, last)` in the finite over cell.** The end
resolution window `[end_.key, resolve end_)` is exactly as long as the reported list and
already contains every reported key, so it cannot also contain a key strictly below the
reported last. -/
theorem between_end_key_last_eq_nil {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hmore : res.more = true)
(hrev : r.reverse = true) (hne : res.keys ≠ [])
(hend : 2 ≤ r.end_.offset)
(hEL : r.end_.key < ((res.keys.getLastD ([] : Key) : Key) : WithTop Key))
(ht : res.keys.length = (r.end_.offset - 1).toNat) :
between db r.end_.key ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) = [] := by
classical
have hLlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne :=
getLastD_eq_getLast_of_ne hne
set L : Key := res.keys.getLast hne with hLdef
have hLmem : L ∈ res.keys := List.getLast_mem hne
have hEL' : r.end_.key < ((L : Key) : WithTop Key) := by rw [← hLlast]; exact hEL
have hELE : r.end_.key ≤ ((L : Key) : WithTop Key) := le_of_lt hEL'
set e : ℕ := (r.end_.offset - 1).toNat with hedef
have ht' : res.keys.length = e := by rw [ht, hedef]
have hsort : res.keys.SortedGT := RangeRead.compatible_sortedGT hcomp hrev
have hLle : ∀ x ∈ res.keys, L ≤ x :=
fun x hx => (hsort.pairwise.imp (fun h => le_of_lt h)).rel_getLast hx
have hLR : ((L : Key) : WithTop Key) < resolve db r.end_ := by
have hck : L ∈ RangeRead.completeKeys db r :=
(RangeRead.compatible_keys_prefix hcomp).subset hLmem
exact (RangeRead.mem_completeKeys.mp hck).2.2
have hLRle : ((L : Key) : WithTop Key) ≤ resolve db r.end_ := le_of_lt hLR
have hoff : 1 ≤ r.end_.offset := by omega
have hnsub : res.keys.Nodup :=
List.Nodup.sublist (RangeRead.compatible_keys_prefix hcomp).sublist
(RangeRead.completeKeys_nodup db r)
rcases eq_or_ne (resolve db r.end_) (⊤ : WithTop Key) with hRtop | hRne
· -- the end resolution is the sentinel
have hresend := resolve_eq_filter_getElem? (db := db) (s := r.end_) hoff
have hgetnone : (db.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))))[e]? = none := by
cases hq : (db.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))))[e]? with
| none => rfl
| some k =>
rw [hq] at hresend
exact absurd hresend (by simp [hRtop])
have hQle : (db.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).length ≤ e :=
List.getElem?_eq_none_iff.mp hgetnone
-- every reported key is stored at or above `end_.key`
have hsubQ : res.keys ⊆ db.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) := by
intro k hk
exact List.mem_filter.mpr ⟨RangeRead.compatible_keys_subset hcomp hk,
by rw [decide_eq_true_eq]; exact le_trans hELE (WithTop.coe_le_coe.mpr (hLle k hk))⟩
have htQ : res.keys.length ≤ (db.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).length :=
length_le_of_nodup_subset hnsub hsubQ
-- so `[end_.key, last)` is empty: any key there would enlarge the above-list
rw [List.eq_nil_iff_forall_not_mem]
intro x hx
rw [between_eq_filter_above] at hx
obtain ⟨hxA, hxL⟩ := List.mem_filter.mp hx
rw [hLlast] at hxL
have hxL' : ((x : Key) : WithTop Key) < ((L : Key) : WithTop Key) :=
of_decide_eq_true hxL
have hxnotres : x ∉ res.keys := fun hres =>
absurd (WithTop.coe_le_coe.mpr (hLle x hres)) (not_le.mpr hxL')
have hnsub2 : (x :: res.keys).Nodup := by
rw [List.nodup_cons]; exact ⟨hxnotres, hnsub⟩
have hsub2 : (x :: res.keys) ⊆ db.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) := by
intro y hy
rcases List.mem_cons.mp hy with rfl | hy
· exact hxA
· exact hsubQ hy
have hlen : (x :: res.keys).length ≤ (db.keys.filter
(fun k : Key => decide (r.end_.key ≤ (k : WithTop Key)))).length :=
length_le_of_nodup_subset hnsub2 hsub2
simp only [List.length_cons, ht'] at hlen
omega
· -- a genuine end resolution
have hlenER : (between db r.end_.key (resolve db r.end_)).length = e :=
length_between_end_resolve_eq_of_ne_top hend hRne
have hLRrev : res.keys = (between db ((L : Key) : WithTop Key)
(resolve db r.end_)).reverse :=
res_keys_eq_reverse_between_resolve_end hcomp hmore hrev hne
have hlenLR : (between db ((L : Key) : WithTop Key) (resolve db r.end_)).length =
res.keys.length := by
have h := congrArg List.length hLRrev
rw [List.length_reverse] at h
exact h.symm
have h1 := cnt_eq_add_between (db := db) hELE
have h2 := cnt_eq_add_between (db := db) hLRle
have h3 := cnt_eq_add_between (db := db) (le_trans hELE hLRle)
rw [ht'] at hlenLR
have : (between db r.end_.key ((L : Key) : WithTop Key)).length = 0 := by
omega
rw [hLlast]
exact List.eq_nil_of_length_eq_zero this
/-- When the interval `[E, L)` stores no key, the lists of keys at or above `E` and at
or above `L` coincide. -/
theorem above_eq_of_between_eq_nil {db : DB} {E L : WithTop Key} (hE : E ≤ L)
(h : between db E L = []) : above db E = above db L := by
rw [above_B_eq_filter hE]
exact (List.filter_eq_self.mpr fun x hx => by
rw [decide_eq_true_eq]
by_contra hlt
push Not at hlt
have hmem : x ∈ between db E L := by
rw [between_eq_filter_above]
exact List.mem_filter.mpr ⟨hx, by rw [decide_eq_true_eq]; exact hlt⟩
rw [h] at hmem
exact absurd hmem List.not_mem_nil).symm
/-- **The finite over cell reduces to the read whose end key is the reported last.**
Provided no key is stored in `[end_.key, last)`, replacing the end key by the reported
last at the same offset leaves the complete keys — hence compatibility — unchanged. -/
theorem compatible_iff_over_reduce {r : RangeRead} {res : Result}
(hmore : res.more = true) (hrev : r.reverse = true) (hne : res.keys ≠ [])
(hend : 2 ≤ r.end_.offset)
(hEL : r.end_.key < ((res.keys.getLastD ([] : Key) : Key) : WithTop Key))
(ht : res.keys.length = (r.end_.offset - 1).toNat) :
∀ db, RangeRead.Compatible db r res ↔
(between db r.end_.key ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) = []) ∧
RangeRead.Compatible db
{ r with end_ := ⟨((res.keys.getLastD ([] : Key) : Key) : WithTop Key),
r.end_.offset⟩ } res := by
intro db
set Lk : Key := res.keys.getLastD ([] : Key) with hLk
have hLlast : Lk = res.keys.getLast hne := getLastD_eq_getLast_of_ne hne
have hELE : r.end_.key ≤ ((Lk : Key) : WithTop Key) := le_of_lt hEL
have hoff : 1 ≤ r.end_.offset := by omega
let r' : RangeRead :=
{ r with end_ := ⟨((Lk : Key) : WithTop Key), r.end_.offset⟩ }
have hr'end : r'.end_ = ⟨((Lk : Key) : WithTop Key), r.end_.offset⟩ := rfl
have hr'beg : r'.begin = r.begin := rfl
have hr'rev : r'.reverse = r.reverse := rfl
have hr'lim : r'.limit = r.limit := rfl
have hresolve : ∀ (_ : between db r.end_.key ((Lk : Key) : WithTop Key) = []),
resolve db r.end_ = resolve db r'.end_ := by
intro hnil
have habove : above db r.end_.key = above db ((Lk : Key) : WithTop Key) :=
above_eq_of_between_eq_nil hELE hnil
rw [resolve_eq_filter_getElem? (db := db) (s := r.end_) hoff,
resolve_eq_filter_getElem? (db := db) (s := r'.end_) hoff, hr'end]
simp only [above] at habove
rw [habove]
have hck : ∀ (_ : between db r.end_.key ((Lk : Key) : WithTop Key) = []),
RangeRead.completeKeys db r = RangeRead.completeKeys db r' := by
intro hnil
have hres := hresolve hnil
unfold RangeRead.completeKeys
rw [hr'rev, hrev]
simp only [ ite_true]
rw [hres]
constructor
· intro hcomp
have hnil := between_end_key_last_eq_nil hcomp hmore hrev hne hend hEL ht
exact ⟨hnil, (compatible_congr_completeKeys (hck hnil) hr'lim).mp hcomp⟩
· rintro ⟨hnil, hcomp'⟩
exact (compatible_congr_completeKeys (hck hnil) hr'lim).mpr hcomp'
/-- A key absent from every compatible database is necessary: a sound range omitting it
would see a compatible database and the same database with the key inserted as agreeing,
though only the former is compatible. -/
theorem necessary_of_forall_not_mem {r : RangeRead} {res : Result} {k : Key}
(hread : Readable r res)
(habs : ∀ db, RangeRead.Compatible db r res → k ∉ db.keys) :
Necessary r res k := by
obtain ⟨db₀, hcomp₀⟩ := hread
intro cr hs
by_contra hkcr
have hkdb : k ∉ db₀.keys := habs db₀ hcomp₀
have hagree : AgreeOn cr db₀ (db₀.insert k hkdb) :=
(ConflictRange.keys_insert_of_not_mem cr db₀ hkdb hkcr).symm
have hcomp₁ : RangeRead.Compatible (db₀.insert k hkdb) r res :=
(hs db₀ (db₀.insert k hkdb) hagree).mp hcomp₀
exact habs (db₀.insert k hkdb) hcomp₁ (DB.mem_insert_self db₀ k hkdb)
/-- If one database stores no key in `[E, L)` and two databases agree on `[E, U)` with
`L ≤ U`, then neither does the other. -/
theorem between_eq_nil_of_agreeOn {db₁ db₂ : DB} {E L U : WithTop Key}
(_hE : E ≤ L) (hLU : L ≤ U) (hnil : between db₁ E L = [])
(hagree : AgreeOn ⟨E, U⟩ db₁ db₂) :
between db₂ E L = [] := by
rw [List.eq_nil_iff_forall_not_mem]
intro k hk
rw [between_eq_filter_above] at hk
obtain ⟨hkA, hkL⟩ := List.mem_filter.mp hk
have hkE : E ≤ ((k : Key) : WithTop Key) := (mem_above.mp hkA).2
have hkL' : ((k : Key) : WithTop Key) < L := of_decide_eq_true hkL
have hkdb₂ : k ∈ db₂.keys := (mem_above.mp hkA).1
have hkcr₂ : k ∈ (⟨E, U⟩ : ConflictRange).keys db₂ :=
ConflictRange.mem_keys_iff.mpr ⟨hkdb₂, hkE, lt_of_lt_of_le hkL' hLU⟩
rw [← hagree] at hkcr₂
obtain ⟨hkdb₁, _hkE', hkU'⟩ := ConflictRange.mem_keys_iff.mp hkcr₂
have hkbetween : k ∈ between db₁ E L := by
rw [between_eq_filter_above]
exact List.mem_filter.mpr ⟨mem_above.mpr ⟨hkdb₁, hkE⟩,
by rw [decide_eq_true_eq]; exact hkL'⟩
rw [hnil] at hkbetween
exact absurd hkbetween List.not_mem_nil
/-- The finite over cell of the reversed crossed negative-begin truncated residual:
the finite branch with the reported last strictly above `end_.key`, with the reported last
below `begin.key`. -/
abbrev negCrossTruncRevResidualFiniteOver (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = true ∧ r.begin.offset < 0 ∧ res.keys ≠ [] ∧
2 ≤ r.end_.offset ∧
r.end_.key < ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) ∧
((res.keys.getLastD ([] : Key) : Key) : WithTop Key) < r.begin.key ∧
res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) =
(r.end_.offset - 1).toNat
/-- The closed form of the finite over cell: the reduced under-cell rule with its lower
endpoint lifted to `end_.key`. -/
noncomputable def closedFormNegCrossTruncRevResidualFiniteOver
(r : RangeRead) (res : Result) : ConflictRange := by
classical
let U : WithTop Key :=
if finiteUnderCond r res then
(((keyAfter (res.keys.headD ([] : Key)) : Key)) : WithTop Key)
else r.begin.key
exact ⟨r.end_.key, U⟩
/-- **Gap-key necessity in the finite over cell.** The witness database stores the
reported keys in ascending order together with `beginSlack + 1 - t` gap keys in
`[keyAfter head, begin.key)` avoiding the target, so its begin anchor is exactly zero,
resolving onto the reported last, while its end resolution is the first gap key and
excludes them. Inserting the target raises the begin anchor to one: the reported last
leaves the window and the reported keys can no longer be a prefix of the complete keys.
The capacity hypothesis is the negation of `finiteUnderCond`. -/
theorem necessary_of_mem_gap_of_negCross_trunc_rev_residualFiniteOver
{r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = true)
(hne : res.keys ≠ []) (hbeg : r.begin.offset < 0)
(hend : 2 ≤ r.end_.offset)
(hEL : r.end_.key < ((res.keys.getLastD ([] : Key) : Key) : WithTop Key))
(hheadB : ((res.keys.headD ([] : Key) : Key) : WithTop Key) < r.begin.key)
(hcount : res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) =
(r.end_.offset - 1).toNat)
(hcond : ¬ finiteUnderCond r res)
{k : Key}
(hkH : ((res.keys.headD ([] : Key) : Key) : WithTop Key) < (k : WithTop Key))
(hkB : ((k : Key) : WithTop Key) < r.begin.key) :
Necessary r res k := by
obtain ⟨db₀, hcomp₀⟩ := hread
set L : Key := res.keys.getLast hne with hLdef
set H : Key := res.keys.head hne with hHdef
set t : ℕ := res.keys.length with htdef
set e : ℕ := (r.end_.offset - 1).toNat with hedef
have hlastD : res.keys.getLastD ([] : Key) = L := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]
exact hLdef.symm
have hheadD : res.keys.headD ([] : Key) = H := by
rw [List.headD_eq_head?_getD, List.head?_eq_some_head hne]
exact hHdef.symm
have hheadOpt : res.keys.head?.getD ([] : Key) = H := by
rw [List.head?_eq_some_head hne]
exact hHdef.symm
have hLmem : L ∈ res.keys := by rw [hLdef]; exact List.getLast_mem hne
have hHmem : H ∈ res.keys := by rw [hHdef]; exact List.head_mem hne
have hsort : res.keys.SortedGT := RangeRead.compatible_sortedGT hcomp₀ hrev
have hLle : ∀ x ∈ res.keys, L ≤ x := by
intro x hx; rw [hLdef]; exact (hsort.pairwise.imp le_of_lt).rel_getLast hx
have hHge : ∀ x ∈ res.keys, x ≤ H := by
intro x hx; rw [hHdef]; exact (hsort.pairwise.imp le_of_lt).rel_head hx
have hEL' : r.end_.key < ((L : Key) : WithTop Key) := by rw [← hlastD]; exact hEL
have hheadB' : ((H : Key) : WithTop Key) < r.begin.key := by rw [← hheadD]; exact hheadB
have hkH' : ((H : Key) : WithTop Key) < (k : WithTop Key) := by rw [← hheadD]; exact hkH
have hHk : H < k := WithTop.coe_lt_coe.mp hkH'
have hE_le_reported : ∀ x ∈ res.keys, r.end_.key ≤ ((x : Key) : WithTop Key) := by
intro x hx
exact le_trans (le_of_lt hEL') (WithTop.coe_le_coe.mpr (hLle x hx))
have hreported_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 (hHge x hx)) hheadB'
have hcount_t : res.keys.countP (fun k : Key => decide (r.end_.key ≤ (k : WithTop Key))) =
t := by
rw [htdef, List.countP_eq_length]
intro x hx; rw [decide_eq_true_eq]; exact hE_le_reported x hx
have ht_e : t = e := by rw [← hcount_t, hcount, hedef]
have hrepB : reportedBelowBegin r res = t := by
unfold reportedBelowBegin
rw [htdef, List.countP_eq_length]
intro x hx; rw [decide_eq_true_eq]; exact hreported_lt_B x hx
have ht_le : t ≤ beginSlack r + 1 := by
have h := reportedBelowBegin_le_beginSlack_succ hcomp₀ hbeg
rwa [hrepB] at h
-- the negation of the capacity condition gives one more gap slot than witness keys
have hcond_ineq : (beginSlack r : ℕ∞) <
((t - 1 : ℕ) : ℕ∞) +
intervalCard (((keyAfter H : Key)) : WithTop Key) r.begin.key := by
have h := not_le.mp (by simpa [finiteUnderCond] using hcond)
rwa [hrepB, hheadOpt] at h
have hcard : (((beginSlack r + 1 - t) + 1 : ℕ) : ℕ∞) ≤
intervalCard (((keyAfter H : Key)) : WithTop Key) r.begin.key := by
cases hcap : intervalCard (((keyAfter H : Key)) : WithTop Key) r.begin.key with
| top => exact le_top
| coe n =>
have h' : (beginSlack r : ℕ∞) < ((t - 1 : ℕ) : ℕ∞) + ((n : ℕ) : ℕ∞) := by
rw [hcap] at hcond_ineq; exact hcond_ineq
rw [← ENat.natCast_add] at h'
have hnat : beginSlack r < (t - 1) + n := by exact_mod_cast h'
have hn : beginSlack r + 1 - t + 1 ≤ n := by omega
exact_mod_cast hn
obtain ⟨dbG, hGrange, hkG, hGlen⟩ :=
exists_db_keysIn_avoid (B := (((keyAfter H : Key)) : WithTop Key))
(E := r.begin.key) (k := k) (m := beginSlack r + 1 - t) hcard
set G : List Key := dbG.keys with hGdef
have hGmem : ∀ x ∈ G, (((keyAfter H : Key)) : WithTop Key) ≤ (x : WithTop Key) ∧
(x : WithTop Key) < r.begin.key := by
intro x hx
simpa only [G, keysIn, Set.mem_ofPred_eq] using hGrange x (by simpa [hGdef] using hx)
have hGlen' : G.length = beginSlack r + 1 - t := by rw [hGdef]; exact hGlen
have hH_lt_G : ∀ x ∈ G, ((H : Key) : WithTop Key) < (x : WithTop Key) := by
intro x hx
exact lt_of_lt_of_le (by exact_mod_cast keyAfter_self_lt H) (hGmem x hx).1
-- assemble the ascending witness database
have hresSort : res.keys.reverse.SortedLT := hsort.reverse
have hGsorted : G.SortedLT := by rw [hGdef]; exact dbG.sorted
have hcrossG : ∀ x ∈ res.keys.reverse, ∀ y ∈ G, x < y := by
intro x hx y hy
have hx' : x ∈ res.keys := List.mem_reverse.mp hx
exact WithTop.coe_lt_coe.mp (lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hHge x hx')) (hH_lt_G y
hy))
have hkeysSorted : (res.keys.reverse ++ G).SortedLT :=
List.sortedLT_append.mpr ⟨hresSort, hGsorted, hcrossG⟩
let db_a : DB := ⟨res.keys.reverse ++ G, hkeysSorted⟩
have hdb_a : db_a.keys = res.keys.reverse ++ G := rfl
have hcntB : db_a.keys.countP (fun x : Key =>
decide (((x : Key) : WithTop Key) < r.begin.key)) = t + G.length := by
rw [hdb_a, List.countP_append, List.countP_reverse]
have h1 : res.keys.countP (fun x : Key =>
decide (((x : Key) : WithTop Key) < r.begin.key)) = t := by
rw [htdef, List.countP_eq_length]
intro x hx; rw [decide_eq_true_eq]; exact hreported_lt_B x hx
have h2 : G.countP (fun x : Key =>
decide (((x : Key) : WithTop Key) < r.begin.key)) = G.length := by
rw [List.countP_eq_length]
intro x hx; rw [decide_eq_true_eq]; exact (hGmem x hx).2
rw [h1, h2]
have hanchor : r.begin.anchor db_a = 0 := by
rw [anchor_eq_count_sub_slack db_a r (le_of_lt hbeg), hcntB, hGlen']
have hts : t + (beginSlack r + 1 - t) = beginSlack r + 1 := Nat.add_sub_of_le ht_le
rw [hts]; push_cast; ring
have h0lt : (0 : ℕ) < db_a.keys.length := by
rw [hdb_a, List.length_append, List.length_reverse]
have htpos : 0 < res.keys.length := List.length_pos_of_ne_nil hne
omega
have hmin_a : ∀ x ∈ db_a.keys, L ≤ x := by
intro x hx
rw [hdb_a] at hx
rcases List.mem_append.mp hx with hxr | hxG
· exact hLle x (List.mem_reverse.mp hxr)
· exact le_trans (hLle H hHmem) (le_of_lt (WithTop.coe_lt_coe.mp (hH_lt_G x hxG)))
have hLmem_a : L ∈ db_a.keys := by
rw [hdb_a]; exact List.mem_append_left _ (List.mem_reverse.mpr hLmem)
have hget0 : db_a.keys[(0 : ℕ)] = L :=
getElem_zero_eq_of_forall_le hkeysSorted hmin_a hLmem_a h0lt
have hresBegin : resolve db_a r.begin = ((L : Key) : WithTop Key) := by
have h0 : 0 ≤ r.begin.anchor db_a := by rw [hanchor]
have hlt : (r.begin.anchor db_a).toNat < db_a.keys.length := by
rw [hanchor]; simpa using h0lt
rw [resolve_eq_getElem h0 hlt]
have hidx : (r.begin.anchor db_a).toNat = 0 := by rw [hanchor]; rfl
simpa [hidx] using hget0
-- the end filter is the whole ascending list
have hEfilt : db_a.keys.filter (fun x : Key => decide (r.end_.key ≤ (x : WithTop Key))) =
res.keys.reverse ++ G := by
rw [hdb_a]
apply List.filter_eq_self.mpr
intro x hx
rw [decide_eq_true_eq]
rcases List.mem_append.mp hx with hxr | hxG
· exact hE_le_reported x (List.mem_reverse.mp hxr)
· exact le_of_lt (lt_of_lt_of_le hEL' (WithTop.coe_le_coe.mpr
(le_trans (hLle H hHmem) (le_of_lt (WithTop.coe_lt_coe.mp (hH_lt_G x hxG))))))
have hresEnd : resolve db_a r.end_ =
(match G[0]? with
| some x => ((x : Key) : WithTop Key)
| none => (⊤ : WithTop Key)) := by
rw [resolve_eq_filter_getElem? (db := db_a) (s := r.end_) (by omega)]
rw [hEfilt]
have hidx : (r.end_.offset - 1).toNat = t := by omega
rw [hidx]
have h1 : (res.keys.reverse ++ G)[t]? = G[0]? := by
rw [List.getElem?_append_right (by rw [List.length_reverse, htdef])]
rw [htdef, List.length_reverse, Nat.sub_self]
rw [h1]
rfl
-- every reported key is below the end resolution, no gap key is
have hrep_lt_res : ∀ x ∈ res.keys, ((x : Key) : WithTop Key) < resolve db_a r.end_ := by
intro x hx
rw [hresEnd]
cases hG : G with
| nil => exact WithTop.coe_lt_top _
| cons g gs =>
simp only [List.getElem?_cons_zero]
exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hHge x hx)) (hH_lt_G g (by rw [hG]; exact
List.mem_cons_self))
have hG_not_lt_res : ∀ y ∈ G, ¬ ((y : Key) : WithTop Key) < resolve db_a r.end_ := by
intro y hy
rw [hresEnd]
cases hG : G with
| nil => rw [hG] at hy; exact absurd hy List.not_mem_nil
| cons g gs =>
simp only [List.getElem?_cons_zero]
have hgle : g ≤ y := by
have hpair : (g :: gs).Pairwise (· < ·) := by
rw [← List.sortedLT_iff_pairwise]; rw [← hG]; exact hGsorted
have := (hpair.imp le_of_lt).rel_head (by rw [hG] at hy; exact hy)
simpa using this
exact not_lt.mpr (WithTop.coe_le_coe.mpr hgle)
have hfilter : db_a.keys.filter (fun x : Key => decide
(((L : Key) : WithTop Key) ≤ (x : WithTop Key) ∧
(x : WithTop Key) < resolve db_a r.end_)) = res.keys.reverse := by
rw [hdb_a, List.filter_append]
have h1 : (res.keys.reverse).filter (fun x : Key => decide
(((L : Key) : WithTop Key) ≤ (x : WithTop Key) ∧
(x : WithTop Key) < resolve db_a r.end_)) = res.keys.reverse := by
rw [List.filter_eq_self]
intro x hx
rw [decide_eq_true_eq]
exact ⟨WithTop.coe_le_coe.mpr (hLle x (List.mem_reverse.mp hx)),
hrep_lt_res x (List.mem_reverse.mp hx)⟩
have h2 : G.filter (fun x : Key => decide
(((L : Key) : WithTop Key) ≤ (x : WithTop Key) ∧
(x : WithTop Key) < resolve db_a r.end_)) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx
rw [decide_eq_true_eq]
intro hP
exact hG_not_lt_res x hx hP.2
rw [h1, h2, List.append_nil]
have hcomplete : RangeRead.completeKeys db_a r = res.keys := by
unfold RangeRead.completeKeys RangeRead.inRange
rw [hrev]
simp only [ite_true]
rw [hresBegin, hfilter, List.reverse_reverse]
have hcompat_a : RangeRead.Compatible db_a r res :=
⟨hcomp₀.1, Or.inl ⟨hmore, by rw [hcomplete], hne⟩⟩
have hk_a : k ∉ db_a.keys := by
rw [hdb_a]
intro hmem
rcases List.mem_append.mp hmem with hx | hx
· exact absurd (WithTop.coe_le_coe.mpr (hHge k (List.mem_reverse.mp hx))) (not_le.mpr hkH')
· exact hkG (by simpa [hGdef] using hx)
-- insert the target: it lands above the reported keys and at the gap bottom
let db_b : DB := db_a.insert k hk_a
have hins : (res.keys.reverse ++ G).orderedInsert (· ≤ ·) k =
res.keys.reverse ++ G.orderedInsert (· ≤ ·) k := by
refine orderedInsert_append_of_forall_lt_left ?_
intro x hx
exact WithTop.coe_lt_coe.mp
(lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hHge x (List.mem_reverse.mp hx))) hkH')
have hb_keys : db_b.keys = res.keys.reverse ++ G.orderedInsert (· ≤ ·) k := by
rw [show db_b.keys = db_a.keys.orderedInsert (· ≤ ·) k from rfl, hdb_a, hins]
have hb_all : ∀ x ∈ db_b.keys,
decide (((x : Key) : WithTop Key) < r.begin.key) = true := by
intro x hx
rw [decide_eq_true_eq]
rw [hb_keys] at hx
rcases List.mem_append.mp hx with hx' | hx'
· exact hreported_lt_B x (List.mem_reverse.mp hx')
· rw [List.mem_orderedInsert] at hx'
rcases hx' with rfl | hxG
· exact hkB
· exact (hGmem x hxG).2
have hb_len : db_b.keys.length = t + (beginSlack r + 1 - t) + 1 := by
rw [hb_keys, List.length_append, List.length_reverse, List.orderedInsert_length,
hGlen', htdef]
omega
have hb_cntB : db_b.keys.countP (fun x : Key =>
decide (((x : Key) : WithTop Key) < r.begin.key)) = t + (beginSlack r + 1 - t) + 1 := by
rw [← hb_len, List.countP_eq_length]
exact hb_all
have hanchor_b : r.begin.anchor db_b = 1 := by
rw [anchor_eq_count_sub_slack db_b r (le_of_lt hbeg), hb_cntB]
have hts : t + (beginSlack r + 1 - t) = beginSlack r + 1 := Nat.add_sub_of_le ht_le
rw [hts]; push_cast; ring
have hb_min : ∀ x ∈ db_b.keys, L ≤ x := by
intro x hx
rw [hb_keys] at hx
rcases List.mem_append.mp hx with hxr | hxG
· exact hLle x (List.mem_reverse.mp hxr)
· rw [List.mem_orderedInsert] at hxG
rcases hxG with rfl | hxG
· exact le_trans (hLle H hHmem) (le_of_lt (WithTop.coe_lt_coe.mp hkH'))
· exact le_trans (hLle H hHmem) (le_of_lt (WithTop.coe_lt_coe.mp (hH_lt_G x hxG)))
have hLmem_b : L ∈ db_b.keys := by
rw [hb_keys]; exact List.mem_append_left _ (List.mem_reverse.mpr hLmem)
have h0lt_b : 0 < db_b.keys.length := by rw [hb_len]; omega
have hget0_b : db_b.keys[(0 : ℕ)] = L :=
getElem_zero_eq_of_forall_le db_b.sorted hb_min hLmem_b h0lt_b
have h1lt : (1 : ℕ) < db_b.keys.length := by rw [hb_len]; omega
have hresBegin_b : resolve db_b r.begin = ((db_b.keys[(1 : ℕ)] : Key) : WithTop Key) := by
have h0 : 0 ≤ r.begin.anchor db_b := by rw [hanchor_b]; norm_num
have hlt : (r.begin.anchor db_b).toNat < db_b.keys.length := by
rw [hanchor_b]; simpa using h1lt
rw [resolve_eq_getElem h0 hlt]
have hidx : (r.begin.anchor db_b).toNat = 1 := by rw [hanchor_b]; rfl
simp [hidx]
have hLlt : L < db_b.keys[(1 : ℕ)] := by
have h01 : (0 : ℕ) < db_b.keys.length := by omega
have h := (List.SortedLT.getElem_lt_getElem_iff db_b.sorted (hi := h01)
(hj := h1lt)).mpr (show (0 : ℕ) < 1 by omega)
rwa [hget0_b] at h
have hLnot_ck : L ∉ RangeRead.completeKeys db_b r := by
intro hmem
obtain ⟨_, hck, _⟩ := RangeRead.mem_completeKeys.mp hmem
rw [hresBegin_b] at hck
exact absurd hck (not_le.mpr (WithTop.coe_lt_coe.mpr hLlt))
have hnotCompat_b : ¬ RangeRead.Compatible db_b r res := by
intro hc
rcases hc.2 with ⟨_, hpre, _⟩ | ⟨hm, _⟩
· exact hLnot_ck (hpre.subset hLmem)
· rw [hmore] at hm; exact absurd hm (by simp)
refine necessary_of_toggle ⟨db_a, hcompat_a, ?_⟩
rw [toggle_eq_insert_of_not_mem hk_a]
exact hnotCompat_b
/-- **The finite over cell of the reversed residual is minimal.** The closed form is
`[end_.key, U)` with `U` the under-cell upper endpoint. Keys in `[end_.key, last)` are
absent from every compatible database, keys in `[last, head]` are reported (hence
necessary), and keys in `(head, U)` are necessary by the gap-toggle witness when `U` is
`begin.key`; the alternative `U = keyAfter head` leaves no key in that gap. Soundness
transfers from the reduced finite-under read, using that agreement on `[end_.key, U)`
also fixes the absence in `[end_.key, last)`. -/
theorem minimal_closedForm_of_negCross_trunc_rev_residualFinite_over
{r : RangeRead} {res : Result}
(hread : Readable r res) (hcell : negCrossTruncRevResidualFiniteOver r res) :
Minimal r res (closedFormNegCrossTruncRevResidualFiniteOver r res) := by
classical
obtain ⟨db₀, hcomp₀⟩ := hread
obtain ⟨hmore, hrev, hbeg, hne, hend, hEL, hLB, hcount⟩ := hcell
set L : Key := res.keys.getLastD ([] : Key) with hLdef
set H : Key := res.keys.headD ([] : Key) with hHdef
have hLg : L = res.keys.getLast hne := by
rw [hLdef, getLastD_eq_getLast_of_ne hne]
have hHg : H = res.keys.head hne := by
rw [hHdef, headD_eq_head_of_ne hne]
have hLmem : L ∈ res.keys := by rw [hLg]; exact List.getLast_mem hne
have hHmem : H ∈ res.keys := by rw [hHg]; exact List.head_mem hne
have hsort : res.keys.SortedGT := RangeRead.compatible_sortedGT hcomp₀ hrev
have hLle : ∀ x ∈ res.keys, L ≤ x := by
intro x hx; rw [hLg]; exact (hsort.pairwise.imp le_of_lt).rel_getLast hx
have hHge : ∀ x ∈ res.keys, x ≤ H := by
intro x hx; rw [hHg]; exact (hsort.pairwise.imp le_of_lt).rel_head hx
have hEL' : r.end_.key < ((L : Key) : WithTop Key) := hEL
have hLB' : ((L : Key) : WithTop Key) < r.begin.key := hLB
-- the finite count is the length, because every reported key is at or above `L`
have ht : res.keys.length = (r.end_.offset - 1).toNat := by
rw [← hcount]
exact (List.countP_eq_length.mpr (fun x hx => by
rw [decide_eq_true_eq]
exact le_trans (le_of_lt hEL') (WithTop.coe_le_coe.mpr (hLle x hx)))).symm
let U : WithTop Key :=
if finiteUnderCond r res then
(((keyAfter (res.keys.headD ([] : Key)) : Key)) : WithTop Key)
else r.begin.key
let r' : RangeRead :=
{ r with end_ := ⟨((L : Key) : WithTop Key), r.end_.offset⟩ }
have hcompat : ∀ db, RangeRead.Compatible db r res ↔
between db r.end_.key ((L : Key) : WithTop Key) = [] ∧
RangeRead.Compatible db r' res := by
intro db
simpa [r', hLdef] using
compatible_iff_over_reduce (r := r) (res := res) hmore hrev hne hend hEL ht db
have hread' : Readable r' res :=
⟨db₀, ((hcompat db₀).mp hcomp₀).2⟩
-- the reduced read lies in the finite under cell
have hr'beg : r'.begin = r.begin := rfl
have hr'rev : r'.reverse = true := hrev
have hr'endoff : r'.end_.offset = r.end_.offset := rfl
have hr'endkey : r'.end_.key = ((L : Key) : WithTop Key) := by
change ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) = ((L : Key) : WithTop Key)
exact congrArg (fun x : Key => (x : WithTop Key)) hLdef.symm
have hcountL : res.keys.countP (fun k : Key =>
decide (((L : Key) : WithTop Key) ≤ (k : WithTop Key))) =
(r.end_.offset - 1).toNat := by
rw [← ht]
exact List.countP_eq_length.mpr (fun x hx => by
rw [decide_eq_true_eq]; exact WithTop.coe_le_coe.mpr (hLle x hx))
have hbase : negCrossTruncRevResidualFiniteUnder r' res := by
refine ⟨hmore, hr'rev, ?_, hne, ?_, ?_, ?_, ?_⟩
· rw [hr'beg]; exact hbeg
· rw [hr'endoff]; exact hend
· rw [hr'endkey]
· rw [hr'beg]; rw [← hLdef]; exact hLB
· rw [hr'endoff, hr'endkey]; exact hcountL
have hcrUnder : closedFormNegCrossTruncRevResidualFiniteUnder r' res =
(⟨((L : Key) : WithTop Key), U⟩ : ConflictRange) := by
have hcondEq : finiteUnderCond r' res = finiteUnderCond r res := rfl
simp only [closedFormNegCrossTruncRevResidualFiniteUnder, U, hcondEq, hLdef]
rfl
have hcrOver : closedFormNegCrossTruncRevResidualFiniteOver r res =
(⟨r.end_.key, U⟩ : ConflictRange) := by
simp only [closedFormNegCrossTruncRevResidualFiniteOver, U]
have hLU : ((L : Key) : WithTop Key) ≤ U := by
simp only [U]
split
· exact le_of_lt (lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hLle H hHmem))
(by exact_mod_cast keyAfter_self_lt H))
· exact le_of_lt hLB'
have hmain : Sound r' res (⟨((L : Key) : WithTop Key), U⟩ : ConflictRange) →
Minimal r res (closedFormNegCrossTruncRevResidualFiniteOver r res) := by
intro hsnd'
rw [hcrOver]
refine (minimal_iff_sound_and_necessary).mpr ⟨?_, ?_⟩
· intro db₁ db₂ hagree
rw [hcompat db₁, hcompat db₂]
constructor
· rintro ⟨hnil₁, hcomp₁⟩
exact ⟨between_eq_nil_of_agreeOn (le_of_lt hEL') hLU hnil₁ hagree,
(hsnd' db₁ db₂ (agreeOn_of_subrange
(subrange_of_le (le_of_lt hEL') (le_refl U)) hagree)).mp hcomp₁⟩
· rintro ⟨hnil₂, hcomp₂⟩
exact ⟨between_eq_nil_of_agreeOn (le_of_lt hEL') hLU hnil₂ (AgreeOn.symm hagree),
(hsnd' db₁ db₂ (agreeOn_of_subrange
(subrange_of_le (le_of_lt hEL') (le_refl U)) hagree)).mpr hcomp₂⟩
· intro k hk
rw [ConflictRange.mem_iff] at hk
obtain ⟨hkE, hkU⟩ := hk
by_cases hkL : ((k : Key) : WithTop Key) < ((L : Key) : WithTop Key)
· refine necessary_of_forall_not_mem ⟨db₀, hcomp₀⟩ ?_
intro db hcomp hkdb
obtain ⟨hnil, _⟩ := (hcompat db).mp hcomp
have hkbet : k ∈ between db r.end_.key ((L : Key) : WithTop Key) := by
rw [between_eq_filter_above]
exact List.mem_filter.mpr ⟨mem_above.mpr ⟨hkdb, hkE⟩,
by rw [decide_eq_true_eq]; exact hkL⟩
rw [hnil] at hkbet
exact absurd hkbet List.not_mem_nil
· push Not at hkL
by_cases hkH : k ≤ H
· exact Necessary.of_between (necessary_of_mem_result ⟨db₀, hcomp₀⟩ hLmem)
(necessary_of_mem_result ⟨db₀, hcomp₀⟩ hHmem) (WithTop.coe_le_coe.mp hkL) hkH
· push Not at hkH
have hnotcond : ¬ finiteUnderCond r res := by
intro hcond
have hUeq : U = (((keyAfter (res.keys.headD ([] : Key)) : Key)) : WithTop Key) := by
simp only [U, hcond, ite_true]
rw [hUeq] at hkU
have hHk' : res.keys.headD ([] : Key) < k := by rw [← hHdef]; exact hkH
have hkK : k < keyAfter (res.keys.headD ([] : Key)) := WithTop.coe_lt_coe.mp hkU
exact absurd hHk' (not_lt.mpr ((lt_keyAfter_iff k _).mp hkK))
have hkUI : ((k : Key) : WithTop Key) < r.begin.key := by
simp only [U, hnotcond, ite_false] at hkU
exact hkU
exact necessary_of_mem_gap_of_negCross_trunc_rev_residualFiniteOver
⟨db₀, hcomp₀⟩ hmore hrev hne hbeg hend (by rw [← hLdef]; exact hEL)
(by rw [← hHdef]; exact lt_trans (WithTop.coe_lt_coe.mpr hkH) hkUI)
hcount hnotcond
(WithTop.coe_lt_coe.mpr hkH) hkUI
by_cases hcross : (((keyAfter (res.keys.headD ([] : Key)) : Key)) : WithTop Key) <
r'.begin.key
· refine hmain ?_
rw [← hcrUnder]
exact (minimal_closedForm_of_negCross_trunc_rev_residualFinite_under_crossed hread'
⟨hbase, hcross⟩).sound
· refine hmain ?_
rw [← hcrUnder]
exact (minimal_closedForm_of_negCross_trunc_rev_residualFinite_under_notCrossed hread'
⟨hbase, hcross⟩).sound
end FormalConflictRange