Files

184 lines
8.7 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.NegCrossLongNonpos
/-!
# The truncated negative-begin anchor bound
The complete negative-begin cells show that a negative begin anchor forces the capacity
bound `clampNonposBottom` (`clampNonposBottom_of_anchor_neg`,
`clampNonposBottom_of_anchor_neg_long`). This module proves the truncated analogue: for a
forward result reporting `more`, a negative begin offset and a nonpositive end offset, a
negative begin anchor still forces `clampNonposBottom`.
The only difference from the complete case is that the reported keys are a prefix of the
complete window rather than the whole window. The reported keys below `begin.key` are
therefore a *sub*-count of the complete keys, which is enough: the complete window has
`clampNonposD + 1` keys in `[resolve end, end.key)`, so the count below `begin.key` still
forces the capacity inequality.
-/
open FormalConflictRange
namespace FormalConflictRange
/-- In a compatible forward truncated nonpositive-end read, the reported keys below
`begin.key` are no more numerous than the complete window, i.e. the stored keys below
`resolve end`. -/
theorem reportedBelowBegin_le_cnt_resolve_end {db : DB} {r : RangeRead} {res : Result}
(hcomp : RangeRead.Compatible db r res) (hrev : r.reverse = false) :
reportedBelowBegin r res ≤ cnt db (resolve db r.end_) := by
have htlen : reportedBelowBegin r res ≤ res.keys.length :=
List.countP_le_length
have hpre := RangeRead.compatible_keys_prefix hcomp
have hlenle : res.keys.length ≤ (RangeRead.completeKeys db r).length :=
hpre.length_le
have hck : (RangeRead.completeKeys db r).length ≤ cnt db (resolve db r.end_) := by
rw [RangeRead.completeKeys, ite_eq_right (by simp [hrev]), RangeRead.inRange]
calc (db.keys.filter
(fun k : Key => decide (resolve db r.begin ≤ (k : WithTop Key) ∧
(k : WithTop Key) < resolve db r.end_))).length
= db.keys.countP
(fun k : Key => decide (resolve db r.begin ≤ (k : WithTop Key) ∧
(k : WithTop Key) < resolve db r.end_)) := by
rw [List.countP_eq_length_filter]
_ ≤ db.keys.countP
(fun k : Key => decide (((k : Key) : WithTop Key) < resolve db r.end_)) := by
apply countP_le_countP_of_imp
intro k _ hk
rw [decide_eq_true_eq] at hk ⊢
exact hk.2
_ = cnt db (resolve db r.end_) := by rw [cnt]
omega
/-- If the begin key lies at or below the end resolution in a nonpositive-end read, the
capacity of `[begin.key, end.key)` already contains the `clampNonposD + 1` stored keys in
`[resolve end, end.key)`. Hence the clamping capacity test `clampNonposBottom` holds
whenever the reported keys below the begin key fit in the begin slack. -/
theorem clampNonposBottom_of_le_resolve_end {r : RangeRead} {res : Result} {db : DB}
(hend : r.end_.offset ≤ 0)
(hRne : resolve db r.end_ ≠ (([] : Key) : WithTop Key))
(hB_le_R : r.begin.key ≤ resolve db r.end_)
(hmq : reportedBelowBegin r res ≤ beginSlack r) :
clampNonposBottom r res := by
have hRE : resolve db r.end_ ≤ r.end_.key := resolve_le_key_of_offset_nonpos hend
have hlen : (between db (resolve db r.end_) r.end_.key).length = clampNonposD r + 1 :=
between_resolve_end_length hend hRne
have hbetween_le : ((between db (resolve db r.end_) r.end_.key).length : ℕ∞) ≤
intervalCard (resolve db r.end_) r.end_.key :=
between_length_le_intervalCard hRE
have hmono : intervalCard (resolve db r.end_) r.end_.key ≤
intervalCard r.begin.key r.end_.key := by
rw [intervalCard_eq_encard_keysIn, intervalCard_eq_encard_keysIn]
apply Set.encard_le_encard
intro k hk
exact ⟨le_trans hB_le_R hk.1, hk.2⟩
have hcap : (((clampNonposD r + 1 : ℕ)) : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by
rw [← hlen]
exact le_trans hbetween_le hmono
have hsub : (((clampNonposD r + 1 : ℕ)) : ℕ∞) -
intervalCard r.begin.key r.end_.key = 0 := by
rw [tsub_eq_zero_iff_le]
exact hcap
unfold clampNonposBottom
rw [hsub, add_zero]
exact Nat.cast_le.mpr hmq
/-- **The truncated negative-begin anchor bound.** In a compatible forward truncated
result with a negative begin offset, a nonpositive end offset, and reported keys below the
begin key within the begin slack, a negative begin anchor forces `clampNonposBottom`. -/
theorem clampNonposBottom_of_anchor_neg_trunc {r : RangeRead} {res : Result} {db : DB}
(hcomp : RangeRead.Compatible db r res)
(hrev : r.reverse = false) (_hmore : res.more = true)
(hne : res.keys ≠ []) (hbegin : r.begin.offset < 0) (hend : r.end_.offset ≤ 0)
(hmq : reportedBelowBegin r res ≤ beginSlack r)
(hanchor : r.begin.anchor db < 0) :
clampNonposBottom r res := by
have hL : resolve db r.begin = (([] : Key) : WithTop Key) := resolve_eq_nil hanchor
have hck : RangeRead.completeKeys db r =
db.keys.filter (fun k : Key => decide (((k : Key) : WithTop Key) < resolve db r.end_)) := by
rw [RangeRead.completeKeys, ite_eq_right (by simp [hrev])]
unfold RangeRead.inRange
rw [hL]
apply List.filter_congr
intro k _
rw [decide_eq_decide]
exact ⟨fun h => h.2, fun h => ⟨coe_nil_le_key_withTop _, h⟩⟩
have hRne : resolve db r.end_ ≠ (([] : Key) : WithTop Key) := by
intro hR
have hpre := RangeRead.compatible_keys_prefix (db := db) (r := r) (res := res) hcomp
rw [hck, hR] at hpre
have hempty : db.keys.filter
(fun k : Key => decide (((k : Key) : WithTop Key) < (([] : Key) : WithTop Key))) = [] := by
rw [List.filter_eq_nil_iff]
intro k _
simp only [decide_eq_true_eq, not_lt]
exact coe_nil_le_key_withTop _
rw [hempty] at hpre
exact hne (List.prefix_nil.mp hpre)
have hRE : resolve db r.end_ ≤ r.end_.key := resolve_le_key_of_offset_nonpos hend
have hlen : (between db (resolve db r.end_) r.end_.key).length = clampNonposD r + 1 :=
between_resolve_end_length hend hRne
have htR : reportedBelowBegin r res ≤ cnt db (resolve db r.end_) :=
reportedBelowBegin_le_cnt_resolve_end hcomp hrev
have hcB : cnt db r.begin.key ≤ beginSlack r := by
have h := hanchor
rw [anchor_eq_count_sub_slack db r (le_of_lt hbegin)] at h
unfold cnt
omega
have hcntE : cnt db r.end_.key =
cnt db (resolve db r.end_) + (clampNonposD r + 1) := by
rw [cnt_eq_add_between db hRE, hlen]
by_cases hB_le_E : r.begin.key ≤ r.end_.key
· have hcntEB : cnt db r.end_.key =
cnt db r.begin.key + (between db r.begin.key r.end_.key).length :=
cnt_eq_add_between db hB_le_E
have hdnat : clampNonposD r + 1 ≤
(between db r.begin.key r.end_.key).length +
(beginSlack r - reportedBelowBegin r res) := by
omega
have hcast : (((clampNonposD r + 1 : ℕ)) : ℕ∞) ≤
((between db r.begin.key r.end_.key).length : ℕ∞) +
((beginSlack r - reportedBelowBegin r res : ℕ) : ℕ∞) := by
exact_mod_cast hdnat
have hg' : ((between db r.begin.key r.end_.key).length : ℕ∞) ≤
intervalCard r.begin.key r.end_.key :=
between_length_le_intervalCard hB_le_E
have hmain : (((clampNonposD r + 1 : ℕ)) : ℕ∞) ≤
intervalCard r.begin.key r.end_.key +
((beginSlack r - reportedBelowBegin r res : ℕ) : ℕ∞) :=
le_trans hcast (add_le_add hg' le_rfl)
have htsub : (((clampNonposD r + 1 : ℕ)) : ℕ∞) - intervalCard r.begin.key r.end_.key ≤
((beginSlack r - reportedBelowBegin r res : ℕ) : ℕ∞) := by
rw [tsub_le_iff_left]
exact hmain
unfold clampNonposBottom
calc (reportedBelowBegin r res : ℕ∞) +
((((clampNonposD r + 1 : ℕ)) : ℕ∞) - intervalCard r.begin.key r.end_.key)
≤ (reportedBelowBegin r res : ℕ∞) +
((beginSlack r - reportedBelowBegin r res : ℕ) : ℕ∞) :=
add_le_add le_rfl htsub
_ = (beginSlack r : ℕ∞) := by
rw [← ENat.natCast_add]
congr 1
omega
· have hEB : r.end_.key < r.begin.key := lt_of_not_ge hB_le_E
have hEBle : r.end_.key ≤ r.begin.key := le_of_lt hEB
have hcntB : cnt db r.begin.key =
cnt db r.end_.key + (between db r.end_.key r.begin.key).length :=
cnt_eq_add_between db hEBle
have hnat : reportedBelowBegin r res + (clampNonposD r + 1) ≤ beginSlack r := by
omega
have hcap0 : intervalCard r.begin.key r.end_.key = 0 :=
intervalCard_eq_zero_of_le hEBle
unfold clampNonposBottom
rw [hcap0]
have hcast : (((reportedBelowBegin r res + (clampNonposD r + 1) : ℕ)) : ℕ∞) ≤
(beginSlack r : ℕ∞) :=
Nat.cast_le.mpr hnat
simpa [ENat.natCast_add, add_comm, add_left_comm, add_assoc] using hcast
end FormalConflictRange