Files

387 lines
16 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.RangeRead
/-!
# Conflict ranges
A `ConflictRange` is a half-open interval of keys `[begin, end_)`, independent
of any database. Both ends are `WithTop Key`: the lower end `⊥` is the empty
key, an ordinary key below every other, so an unbounded lower end needs no
sentinel, while the upper end `⊤` denotes an unbounded range past every key. A
key lies in the range when `begin ≤ k < end_`.
## Why both ends are `WithTop`
Both ends share one type, so a conflict range is uniformly an interval in
`WithTop Key`, matching `RangeRead.inRange` and resolved selector targets; in
particular the keys read by `RangeRead.readAll` fill the range `[⊥, ⊤)`. The
bottom does no work of its own: `begin = ⊥` is exactly the empty key, which is
how "unbounded below" is spelled and how a range genuinely begins at a key —
as the necessary-key analysis of `FormalConflictRange.Sound` shows, the empty
key itself can be necessary. The useless corners are symmetric: `end_ = ⊥` and
`begin = ⊤` both denote nothing but the empty range, since no key lies strictly
below the empty key or at or above `⊤`. Membership remains a property of
genuine keys, as the necessary-key analysis requires: a necessary key must be
contained in every sound range, and only genuine keys can be.
-/
namespace FormalConflictRange
/-- A conflict range is a half-open interval of keys `[begin, end_)`, whose
lower end may be the empty key (the bottom of `WithTop Key`) for an unbounded
range and whose upper end may be `⊤` for an unbounded range. -/
structure ConflictRange where
begin : WithTop Key
end_ : WithTop Key
namespace ConflictRange
/-- A key falls in a conflict range when `begin ≤ k < end_`. -/
def mem (cr : ConflictRange) (k : Key) : Prop :=
cr.begin ≤ (k : WithTop Key) ∧ (k : WithTop Key) < cr.end_
instance : Membership Key ConflictRange := ⟨mem⟩
/-- The set of keys lying in a conflict range. -/
def toSet (cr : ConflictRange) : Set Key := {k | k ∈ cr}
/-- Membership in a conflict range is membership in its set of keys. -/
@[simp] theorem mem_toSet {cr : ConflictRange} {k : Key} : k ∈ cr.toSet ↔ k ∈ cr := Iff.rfl
/-- A nonempty range is determined by its set of keys. The lower end is the
least key in the set, and the upper end is the first key excluded above it (or
`⊤` when no key is excluded). -/
theorem eq_of_toSet_eq_of_nonempty {cr cr' : ConflictRange}
(h : cr.toSet = cr'.toSet) (hne : ∃ k : Key, k ∈ cr) : cr = cr' := by
obtain ⟨k, hk⟩ := hne
have hk'_set : k ∈ cr'.toSet := by
rw [← h]
exact mem_toSet.mpr hk
have hk' : k ∈ cr' := mem_toSet.mp hk'_set
have hb : cr.begin ≤ cr'.begin := by
by_contra hnot
have hlt : cr'.begin < cr.begin := lt_of_not_ge hnot
cases hb' : cr'.begin with
| top =>
rw [hb'] at hlt
exact absurd hlt (not_lt.mpr (le_top))
| coe c =>
have hc_le_k : (c : WithTop Key) ≤ (k : WithTop Key) := by
have hkbegin := hk'.1
rw [hb'] at hkbegin
exact hkbegin
have hc' : c ∈ cr' := by
constructor
· rw [hb']
· exact lt_of_le_of_lt hc_le_k hk'.2
have hc'_set : c ∈ cr'.toSet := mem_toSet.mpr hc'
have hltc : (c : WithTop Key) < cr.begin := by
rw [hb'] at hlt
exact hlt
have hc_not : ¬ c ∈ cr := by
intro hmem
exact absurd hmem.1 (not_le.mpr hltc)
have hc_set : c ∈ cr.toSet := by
rw [h]
exact hc'_set
exact hc_not (mem_toSet.mp hc_set)
have hb' : cr'.begin ≤ cr.begin := by
by_contra hnot
have hlt : cr.begin < cr'.begin := lt_of_not_ge hnot
cases hb : cr.begin with
| top =>
rw [hb] at hlt
exact absurd hlt (not_lt.mpr (le_top))
| coe c =>
have hc_le_k : (c : WithTop Key) ≤ (k : WithTop Key) := by
have hkbegin := hk.1
rw [hb] at hkbegin
exact hkbegin
have hc : c ∈ cr := by
constructor
· rw [hb]
· exact lt_of_le_of_lt hc_le_k hk.2
have hc_set : c ∈ cr.toSet := mem_toSet.mpr hc
have hltc : (c : WithTop Key) < cr'.begin := by
rw [hb] at hlt
exact hlt
have hc_not : ¬ c ∈ cr' := by
intro hmem
exact absurd hmem.1 (not_le.mpr hltc)
have hc'_set : c ∈ cr'.toSet := by
rw [← h]
exact hc_set
exact hc_not (mem_toSet.mp hc'_set)
have he : cr.end_ ≤ cr'.end_ := by
by_contra hnot
have hlt : cr'.end_ < cr.end_ := lt_of_not_ge hnot
cases he' : cr'.end_ with
| top =>
rw [he'] at hlt
exact absurd hlt (not_lt.mpr (le_top))
| coe c =>
have hk_lt_c : (k : WithTop Key) < (c : WithTop Key) := by
have hkend := hk'.2
rw [he'] at hkend
exact hkend
have hc : c ∈ cr := by
constructor
· exact le_trans hk.1 (le_of_lt hk_lt_c)
· rw [he'] at hlt
exact hlt
have hc_set : c ∈ cr.toSet := mem_toSet.mpr hc
have hc_not : ¬ c ∈ cr' := by
intro hmem
have hltc := hmem.2
rw [he'] at hltc
exact absurd hltc (lt_irrefl _)
have hc'_set : c ∈ cr'.toSet := by
rw [← h]
exact hc_set
exact hc_not (mem_toSet.mp hc'_set)
have he' : cr'.end_ ≤ cr.end_ := by
by_contra hnot
have hlt : cr.end_ < cr'.end_ := lt_of_not_ge hnot
cases he : cr.end_ with
| top =>
rw [he] at hlt
exact absurd hlt (not_lt.mpr (le_top))
| coe c =>
have hk_lt_c : (k : WithTop Key) < (c : WithTop Key) := by
have hkend := hk.2
rw [he] at hkend
exact hkend
have hc' : c ∈ cr' := by
constructor
· exact le_trans hk'.1 (le_of_lt hk_lt_c)
· rw [he] at hlt
exact hlt
have hc'_set : c ∈ cr'.toSet := mem_toSet.mpr hc'
have hc_not : ¬ c ∈ cr := by
intro hmem
have hltc := hmem.2
rw [he] at hltc
exact absurd hltc (lt_irrefl _)
have hc_set : c ∈ cr.toSet := by
rw [h]
exact hc'_set
exact hc_not (mem_toSet.mp hc_set)
cases cr with
| mk b e =>
cases cr' with
| mk b' e' =>
have hb_eq : b = b' := le_antisymm hb hb'
have he_eq : e = e' := le_antisymm he he'
rw [hb_eq, he_eq]
/-- A conflict range is empty when its end is at or below its begin. -/
def IsEmpty (cr : ConflictRange) : Prop := cr.end_ ≤ cr.begin
/-- The keys of `db` lying in the conflict range, ascending. -/
def keys (cr : ConflictRange) (db : DB) : List Key :=
db.keys.filter
(fun (k : Key) => decide (cr.begin ≤ (↑k : WithTop Key) ∧ (↑k : WithTop Key) < cr.end_))
/-- Filtering a database by a conflict range is filtering by its endpoints. -/
theorem keys_eq_inRange (cr : ConflictRange) (db : DB) :
cr.keys db = RangeRead.inRange db.keys cr.begin cr.end_ := rfl
/-- A key is in the range's keys exactly when it is stored and in the range. -/
theorem mem_keys_iff {cr : ConflictRange} {db : DB} {k : Key} :
k ∈ cr.keys db ↔ k ∈ db.keys ∧ k ∈ cr := by
change k ∈ db.keys.filter
(fun (k : Key) =>
decide (cr.begin ≤ (↑k : WithTop Key) ∧ (↑k : WithTop Key) < cr.end_)) ↔
k ∈ db.keys ∧ cr.begin ≤ (k : WithTop Key) ∧ (k : WithTop Key) < cr.end_
rw [List.mem_filter, decide_eq_true_eq]
/-- An empty conflict range contains no keys. -/
theorem not_mem_of_isEmpty {cr : ConflictRange} (h : cr.IsEmpty) (k : Key) : k ∉ cr := by
intro hk
exact absurd hk.2 (not_lt.mpr (le_trans h hk.1))
/-- The keys of an empty conflict range are empty. -/
theorem keys_eq_nil_of_isEmpty {cr : ConflictRange} (h : cr.IsEmpty) (db : DB) :
cr.keys db = [] := by
rw [List.eq_nil_iff_forall_not_mem]
intro k hk
rw [mem_keys_iff] at hk
exact not_mem_of_isEmpty h k hk.2
/-- The range's keys are a sublist of the database's keys. -/
theorem keys_sublist (cr : ConflictRange) (db : DB) : (cr.keys db).Sublist db.keys :=
List.filter_sublist
/-- The range's keys are duplicate-free. -/
theorem keys_nodup (cr : ConflictRange) (db : DB) : (cr.keys db).Nodup :=
(keys_sublist cr db).nodup db.sorted.pairwise.nodup
/-- The range's keys are strictly increasing. -/
theorem keys_pairwise (cr : ConflictRange) (db : DB) :
List.Pairwise (· < ·) (cr.keys db) :=
db.sorted.pairwise.sublist (keys_sublist cr db)
/-- A key in the range lies between the endpoints. -/
theorem mem_iff {cr : ConflictRange} {k : Key} :
k ∈ cr ↔ cr.begin ≤ k ∧ (k : WithTop Key) < cr.end_ :=
Iff.rfl
/-- A conflict range contains every key between any two keys it contains. -/
theorem mem_of_between {cr : ConflictRange} {a b k : Key}
(ha : a ∈ cr) (hb : b ∈ cr) (hak : a ≤ k) (hkb : k ≤ b) : k ∈ cr :=
⟨le_trans ha.1 (by exact_mod_cast hak), lt_of_le_of_lt (by exact_mod_cast hkb) hb.2⟩
/-- The intersection of two conflict ranges, as a conflict range: the interval
from the larger lower end to the smaller upper end. -/
def inter (cr₁ cr₂ : ConflictRange) : ConflictRange :=
⟨max cr₁.begin cr₂.begin, min cr₁.end_ cr₂.end_⟩
/-- A key lies in an intersection of conflict ranges exactly when it lies in both.
This is the only property of `inter` the soundness analysis needs: intersecting
ranges intersects their stored keys. -/
theorem mem_inter_iff {cr₁ cr₂ : ConflictRange} {k : Key} :
k ∈ inter cr₁ cr₂ ↔ k ∈ cr₁ ∧ k ∈ cr₂ := by
change (max cr₁.begin cr₂.begin ≤ (k : WithTop Key) ∧
(k : WithTop Key) < min cr₁.end_ cr₂.end_) ↔
((cr₁.begin ≤ (k : WithTop Key) ∧ (k : WithTop Key) < cr₁.end_) ∧
(cr₂.begin ≤ (k : WithTop Key) ∧ (k : WithTop Key) < cr₂.end_))
rw [max_le_iff, lt_min_iff]
tauto
/-- Erasing an interval disjoint from a range leaves the range's stored keys
unchanged. The interval `[a, b)` is disjoint from `cr` when it lies entirely
below `cr.begin` (`cr.begin ≤ a` is excluded) or entirely at or above `cr.end_`.
This is the interval analogue of `keys_erase_of_not_mem`. -/
theorem keys_eraseInterval_of_disjoint (cr : ConflictRange) (db : DB) {a b : Key}
(hdisj : ∀ x, a ≤ x → x < b → x ∉ cr) :
cr.keys (db.eraseInterval (↑a) (↑b)) = cr.keys db := by
unfold keys
rw [DB.eraseInterval_keys, List.filter_filter]
apply List.filter_congr
intro x _
by_cases hp : cr.begin ≤ (x : WithTop Key) ∧ (x : WithTop Key) < cr.end_
· have hq : ¬ (a ≤ x ∧ x < b) := fun h => hdisj x h.1 h.2 hp
simp [hp, hq]
· simp [hp]
/-- Inserting an interval disjoint from a range leaves the range's stored keys
unchanged. This is the interval analogue of `keys_insert_of_not_mem`: the keys
below `a` and at or above `b` are kept, and the inserted successor chain lies in
`[a, b)` and so outside `cr`. -/
theorem keys_insertInterval_of_disjoint (cr : ConflictRange) (db : DB) {a b : Key}
(hab : a ≤ b) (n : ℕ) (hn : ∀ i < n, chain a i < b)
(hdisj : ∀ x, a ≤ x → x < b → x ∉ cr) :
cr.keys (db.insertInterval a b hab n hn) = cr.keys db := by
unfold keys
rw [DB.insertInterval_keys, List.filter_append, List.filter_append]
have hrest : List.filter (fun (k : Key) => decide (cr.begin ≤ (↑k : WithTop Key) ∧
(↑k : WithTop Key) < cr.end_)) (List.map (chain a) (List.range n)) = [] := by
rw [List.filter_eq_nil_iff]
intro x hx hcon
rw [List.mem_map] at hx
obtain ⟨i, hi, rfl⟩ := hx
rw [decide_eq_true_eq] at hcon
exact hdisj (chain a i) (chain_le a i) (hn i (List.mem_range.mp hi)) hcon
rw [hrest, List.append_nil]
apply List.SortedLT.eq_of_mem_iff
· rw [List.sortedLT_append]
refine ⟨?_, ?_, ?_⟩
· exact List.sortedLT_iff_pairwise.mpr ((db.sorted.pairwise.filter _).filter _)
· exact List.sortedLT_iff_pairwise.mpr ((db.sorted.pairwise.filter _).filter _)
· intro x hx y hy
rw [List.mem_filter] at hx hy
exact lt_of_lt_of_le
(of_decide_eq_true (List.mem_filter.mp hx.1).2)
(le_trans hab (of_decide_eq_true (List.mem_filter.mp hy.1).2))
· exact List.sortedLT_iff_pairwise.mpr (db.sorted.pairwise.filter _)
· intro x
constructor
· intro hx
simp only [List.mem_append, List.mem_filter, decide_eq_true_eq] at hx ⊢
rcases hx with ⟨⟨hx, hp⟩, hr⟩ | ⟨⟨hx, hq⟩, hr⟩
· exact ⟨hx, hr⟩
· exact ⟨hx, hr⟩
· intro hx
simp only [List.mem_append, List.mem_filter, decide_eq_true_eq] at hx ⊢
obtain ⟨hx, hr⟩ := hx
have hpq : x < a ∨ b ≤ x := by
rcases lt_or_ge x a with h | h
· exact Or.inl h
· exact Or.inr (le_of_not_gt fun hxb => hdisj x h hxb hr)
rcases hpq with h | h
· exact Or.inl ⟨⟨hx, h⟩, hr⟩
· exact Or.inr ⟨⟨hx, h⟩, hr⟩
/-- Erasing a key outside a range leaves the range's stored keys unchanged. This
is the `[k, keyAfter k)` case of `keys_eraseInterval_of_disjoint`, via
`DB.erase_eq_eraseInterval`. -/
theorem keys_erase_of_not_mem (cr : ConflictRange) (db : DB) {k : Key}
(hk : k ∉ cr) : cr.keys (db.erase k) = cr.keys db := by
rw [DB.erase_eq_eraseInterval]
exact keys_eraseInterval_of_disjoint cr db fun x hkx hxk => by
have hx : x = k := le_antisymm ((lt_keyAfter_iff x k).mp hxk) hkx
rw [hx]; exact hk
/-- Inserting a key outside a range leaves the range's stored keys unchanged. This
is the one-element-chain case of `keys_insertInterval_of_disjoint`, via
`DB.insert_eq_insertInterval`. -/
theorem keys_insert_of_not_mem (cr : ConflictRange) (db : DB) {k : Key}
(hdb : k ∉ db.keys) (hk : k ∉ cr) : cr.keys (db.insert k hdb) = cr.keys db := by
rw [DB.insert_eq_insertInterval db k hdb]
exact keys_insertInterval_of_disjoint cr db (le_of_lt (keyAfter_self_lt k)) 1
(by intro i _; interval_cases i
simp only [chain, List.replicate_zero, List.append_nil]
exact keyAfter_self_lt k)
fun x hkx hxk => by
have hx : x = k := le_antisymm ((lt_keyAfter_iff x k).mp hxk) hkx
rw [hx]; exact hk
end ConflictRange
/-- A conflict range is a subrange of another when every key lying in the first
also lies in the second. -/
def Subrange (cr' cr : ConflictRange) : Prop := ∀ k, k ∈ cr' → k ∈ cr
/-- A conflict range is a proper subrange when it is a subrange and the reverse
containment fails, i.e. the larger range contains a key the smaller does not. -/
def ProperSubrange (cr' cr : ConflictRange) : Prop :=
Subrange cr' cr ∧ ¬ Subrange cr cr'
namespace Subrange
theorem refl (cr : ConflictRange) : Subrange cr cr := fun _ hk => hk
theorem trans {cr₁ cr₂ cr₃ : ConflictRange} (h₁ : Subrange cr₁ cr₂)
(h₂ : Subrange cr₂ cr₃) : Subrange cr₁ cr₃ :=
fun k hk => h₂ k (h₁ k hk)
end Subrange
/-- A conflict range is a subrange of another exactly when its set of keys is a
subset of the other's. -/
theorem subrange_iff_subset {cr' cr : ConflictRange} :
Subrange cr' cr ↔ cr'.toSet ⊆ cr.toSet :=
Iff.rfl
/-- A range whose endpoints lie inside another's is a subrange. -/
theorem subrange_of_le {cr' cr : ConflictRange} (hb : cr.begin ≤ cr'.begin)
(he : cr'.end_ ≤ cr.end_) : Subrange cr' cr :=
fun _ hk => ⟨le_trans hb hk.1, lt_of_lt_of_le hk.2 he⟩
/-- A key in the larger range but not the smaller refutes the reverse
containment, making the smaller a proper subrange. -/
theorem not_subrange_of_witness {cr' cr : ConflictRange} (k : Key)
(hk : k ∈ cr) (hk' : k ∉ cr') : ¬ Subrange cr cr' :=
fun h => hk' (h k hk)
/-- A range contained by another, with a witness key missing from the smaller,
is a proper subrange. -/
theorem properSubrange_of_le_of_witness {cr' cr : ConflictRange}
(hb : cr.begin ≤ cr'.begin) (he : cr'.end_ ≤ cr.end_) (k : Key)
(hk : k ∈ cr) (hk' : k ∉ cr') : ProperSubrange cr' cr :=
⟨subrange_of_le hb he, not_subrange_of_witness k hk hk'⟩
end FormalConflictRange