Files

1195 lines
52 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.Prototype
/-!
# A general flip-witness proof of the headline
This file develops the cell/flip-witness route to `exists_minimal_conflict_range`.
The key observation is that the finite decision procedure in the prototype is not
needed for the proof: the active cells can be defined directly by the existence of a
one-key toggle witness. The only combinatorial input is that toggling two keys in the
same endpoint cell has the same effect on every collected constraint.
-/
namespace FormalConflictRange
open RangeRead
/-! ## Endpoints and cells -/
/-- The endpoints occurring in a constraint. -/
def Constraint.endpoints (c : Constraint) : List (WithTop Key) := [c.lo, c.hi]
/-- All endpoints occurring in a disjunctive system. -/
def dnfEndpoints (D : ConstraintDNF) : Finset (WithTop Key) :=
(D.flatMap fun S => S.flatMap fun c => c.endpoints).toFinset
/-- The endpoint set used for cells, with explicit bottom and top sentinels. -/
def cellEndpoints (D : ConstraintDNF) : Finset (WithTop Key) :=
insert (([] : Key) : WithTop Key) (insert ⊤ (dnfEndpoints D))
theorem mem_dnfEndpoints_lo {D : ConstraintDNF} {S : ConstraintSystem} {c : Constraint}
(hS : S ∈ D) (hc : c ∈ S) : c.lo ∈ dnfEndpoints D := by
rw [dnfEndpoints, List.mem_toFinset, List.mem_flatMap]
refine ⟨S, hS, ?_⟩
rw [List.mem_flatMap]
exact ⟨c, hc, by simp [Constraint.endpoints]⟩
theorem mem_dnfEndpoints_hi {D : ConstraintDNF} {S : ConstraintSystem} {c : Constraint}
(hS : S ∈ D) (hc : c ∈ S) : c.hi ∈ dnfEndpoints D := by
rw [dnfEndpoints, List.mem_toFinset, List.mem_flatMap]
refine ⟨S, hS, ?_⟩
rw [List.mem_flatMap]
exact ⟨c, hc, by simp [Constraint.endpoints]⟩
theorem dnfEndpoints_subset_cellEndpoints (D : ConstraintDNF) :
dnfEndpoints D ⊆ cellEndpoints D := by
intro e he
exact Finset.mem_insert_of_mem (Finset.mem_insert_of_mem he)
/-- Two keys lie in the same cell when every endpoint separates them the same way. -/
def SameCell (E : Finset (WithTop Key)) (k k' : Key) : Prop :=
∀ e ∈ E, ((k : WithTop Key) < e ↔ (k' : WithTop Key) < e)
theorem SameCell.refl (E : Finset (WithTop Key)) (k : Key) : SameCell E k k :=
fun _ _ => Iff.rfl
theorem SameCell.symm {E : Finset (WithTop Key)} {k k' : Key} (h : SameCell E k k') :
SameCell E k' k :=
fun e he => (h e he).symm
/-! ## Moving one key inside a cell -/
/-- Replace a stored key `old` by an absent key `new`, preserving sortedness. -/
def DB.move (db : DB) (old new : Key) (_hold : old ∈ db.keys) (hnew : new ∉ db.keys) : DB :=
(db.erase old).insert new (by
rw [DB.mem_erase_iff]
rintro ⟨hne, hmem⟩
exact hnew hmem)
/-- The keys of a moved database are obtained by erasing the old key and inserting
the new one. -/
@[simp] theorem DB.move_keys (db : DB) (old new : Key) (hold : old ∈ db.keys)
(hnew : new ∉ db.keys) :
(db.move old new hold hnew).keys = (db.erase old).keys.orderedInsert (· ≤ ·) new := rfl
/-- Moving one key within a cell preserves every endpoint count. -/
theorem cnt_move_eq_of_sameCell {E : Finset (WithTop Key)} {db : DB} {old new : Key}
(hsame : SameCell E old new) (hold : old ∈ db.keys) (hnew : new ∉ db.keys)
{e : WithTop Key} (he : e ∈ E) :
cnt (db.move old new hold hnew) e = cnt db e := by
have hnew' : new ∉ (db.erase old).keys := by
rw [DB.mem_erase_iff]
rintro ⟨hne, hmem⟩
exact hnew hmem
have hins := cnt_insert_eq (db.erase old) new hnew' e
have herase := cnt_erase_eq db old hold e
have hlt := hsame e he
have hnat : (cnt (db.move old new hold hnew) e : ℤ) = (cnt db e : ℤ) := by
rw [DB.move, hins, herase]
by_cases h : (old : WithTop Key) < e
· have h' : (new : WithTop Key) < e := hlt.mp h
simp [h, h']
· have h' : ¬ (new : WithTop Key) < e := fun hn => h (hlt.mpr hn)
simp [h, h']
exact_mod_cast hnat
/-- Erasing either of two stored keys in the same cell gives the same endpoint
counts. -/
theorem cnt_erase_eq_of_sameCell {E : Finset (WithTop Key)} {db : DB} {k k' : Key}
(hsame : SameCell E k k') (hk : k ∈ db.keys) (hk' : k' ∈ db.keys)
{e : WithTop Key} (he : e ∈ E) :
cnt (db.erase k) e = cnt (db.erase k') e := by
have hkE := cnt_erase_eq db k hk e
have hk'E := cnt_erase_eq db k' hk' e
have hlt := hsame e he
have hnat : (cnt (db.erase k) e : ℤ) = (cnt (db.erase k') e : ℤ) := by
rw [hkE, hk'E]
by_cases h : (k : WithTop Key) < e
· have h' : (k' : WithTop Key) < e := hlt.mp h
simp [h, h']
· have h' : ¬ (k' : WithTop Key) < e := fun hn => h (hlt.mpr hn)
simp [h, h']
exact_mod_cast hnat
/-- Inserting either of two absent keys in the same cell gives the same endpoint
counts. -/
theorem cnt_insert_eq_of_sameCell {E : Finset (WithTop Key)} {db : DB} {k k' : Key}
(hsame : SameCell E k k') (hk : k ∉ db.keys) (hk' : k' ∉ db.keys)
{e : WithTop Key} (he : e ∈ E) :
cnt (db.insert k hk) e = cnt (db.insert k' hk') e := by
have hkE := cnt_insert_eq db k hk e
have hk'E := cnt_insert_eq db k' hk' e
have hlt := hsame e he
have hnat : (cnt (db.insert k hk) e : ℤ) = (cnt (db.insert k' hk') e : ℤ) := by
rw [hkE, hk'E]
by_cases h : (k : WithTop Key) < e
· have h' : (k' : WithTop Key) < e := hlt.mp h
simp [h, h']
· have h' : ¬ (k' : WithTop Key) < e := fun hn => h (hlt.mpr hn)
simp [h, h']
exact_mod_cast hnat
/-- Two databases with the same endpoint counts satisfy the same constraints. -/
theorem eval_eq_of_agree_endpoints {D : ConstraintDNF} {db₁ db₂ : DB}
(h : ∀ e ∈ dnfEndpoints D, cnt db₁ e = cnt db₂ e) :
∀ S ∈ D, ∀ c ∈ S, c.eval db₁ = c.eval db₂ := by
intro S hS c hc
have hlo := h c.lo (mem_dnfEndpoints_lo hS hc)
have hhi := h c.hi (mem_dnfEndpoints_hi hS hc)
simp [Constraint.eval, hlo, hhi]
/-- Equal endpoint counts give the same truth value for every alternative. -/
theorem systemHoldsAt_congr_endpoints {D : ConstraintDNF} {db₁ db₂ : DB}
(h : ∀ e ∈ dnfEndpoints D, cnt db₁ e = cnt db₂ e)
{S : ConstraintSystem} (hS : S ∈ D) :
SystemHoldsAt S db₁ ↔ SystemHoldsAt S db₂ := by
have heval := eval_eq_of_agree_endpoints h S hS
constructor
· intro hh c hc
change c.eval db₂ ≤ c.bound
rw [← heval c hc]
exact hh c hc
· intro hh c hc
change c.eval db₁ ≤ c.bound
rw [heval c hc]
exact hh c hc
/-- Equal endpoint counts give the same disjunction. -/
theorem anyHolds_congr_endpoints {D : ConstraintDNF} {db₁ db₂ : DB}
(h : ∀ e ∈ dnfEndpoints D, cnt db₁ e = cnt db₂ e) :
AnyHolds D db₁ ↔ AnyHolds D db₂ := by
constructor
· rintro ⟨S, hS, hh⟩
exact ⟨S, hS, (systemHoldsAt_congr_endpoints h hS).mp hh⟩
· rintro ⟨S, hS, hh⟩
exact ⟨S, hS, (systemHoldsAt_congr_endpoints h hS).mpr hh⟩
/-- A move inside a cell preserves the disjunction. -/
theorem anyHolds_move_of_sameCell {D : ConstraintDNF} {E : Finset (WithTop Key)}
{db : DB} {old new : Key}
(hE : dnfEndpoints D ⊆ E) (hsame : SameCell E old new)
(hold : old ∈ db.keys) (hnew : new ∉ db.keys) :
AnyHolds D (db.move old new hold hnew) ↔ AnyHolds D db := by
apply anyHolds_congr_endpoints
intro e he
exact cnt_move_eq_of_sameCell hsame hold hnew (hE he)
/-- Erasing either of two stored keys in the same cell preserves the disjunction. -/
theorem anyHolds_erase_of_sameCell {D : ConstraintDNF} {E : Finset (WithTop Key)}
{db : DB} {k k' : Key}
(hE : dnfEndpoints D ⊆ E) (hsame : SameCell E k k')
(hk : k ∈ db.keys) (hk' : k' ∈ db.keys) :
AnyHolds D (db.erase k) ↔ AnyHolds D (db.erase k') := by
apply anyHolds_congr_endpoints
intro e he
exact cnt_erase_eq_of_sameCell hsame hk hk' (hE he)
/-- Inserting either of two absent keys in the same cell preserves the disjunction. -/
theorem anyHolds_insert_of_sameCell {D : ConstraintDNF} {E : Finset (WithTop Key)}
{db : DB} {k k' : Key}
(hE : dnfEndpoints D ⊆ E) (hsame : SameCell E k k')
(hk : k ∉ db.keys) (hk' : k' ∉ db.keys) :
AnyHolds D (db.insert k hk) ↔ AnyHolds D (db.insert k' hk') := by
apply anyHolds_congr_endpoints
intro e he
exact cnt_insert_eq_of_sameCell hsame hk hk' (hE he)
/-! ## Flip witnesses -/
/-- A one-key toggle witness: a compatible database whose flip at `k` is not
compatible. -/
def FlipWitness (r : RangeRead) (res : Result) (k : Key) : Prop :=
∃ db : DB, RangeRead.Compatible db r res ∧
¬ RangeRead.Compatible (toggle db k) r res
/-- Flipping a stored key erases it. -/
theorem toggle_eq_erase_of_mem {db : DB} {k : Key} (hk : k ∈ db.keys) :
toggle db k = db.erase k := by
simp [toggle, hk]
/-- Flipping an absent key inserts it. -/
theorem toggle_eq_insert_of_not_mem {db : DB} {k : Key} (hk : k ∉ db.keys) :
toggle db k = db.insert k hk := by
simp [toggle, hk]
/-- Every reported key has a flip witness: in any compatible database it is
stored, and erasing it breaks compatibility. This exposes the witness that
`necessary_of_mem_result` constructs internally, so the cell machinery can use
reported keys as active representatives. -/
theorem flipWitness_of_mem_result {r : RangeRead} {res : Result}
(hread : Readable r res) {k : Key} (hk : k ∈ res.keys) :
FlipWitness r res k := by
obtain ⟨db₀, hcomp⟩ := hread
have hkdb : k ∈ db₀.keys := RangeRead.compatible_keys_subset hcomp hk
refine ⟨db₀, hcomp, ?_⟩
rw [toggle_eq_erase_of_mem hkdb]
intro hcompErase
exact DB.not_mem_erase_self db₀ k
(RangeRead.compatible_keys_subset hcompErase hk)
/-- Under a characterizing DNF, a flip witness is exactly a compatible database
whose flip fails the disjunction. -/
theorem flipWitness_iff_exists_not_anyHolds {D : ConstraintDNF} {r : RangeRead}
{res : Result} (hchar : CharacterizesDNF D r res) {k : Key} :
FlipWitness r res k ↔
∃ db : DB, RangeRead.Compatible db r res ∧ ¬ AnyHolds D (toggle db k) := by
constructor
· rintro ⟨db, hcomp, hnot⟩
refine ⟨db, hcomp, fun hany => hnot ?_⟩
exact (hchar (toggle db k)).mpr ⟨hcomp.1, hany⟩
· rintro ⟨db, hcomp, hnot⟩
refine ⟨db, hcomp, fun hcomp' => hnot ?_⟩
exact ((hchar (toggle db k)).mp hcomp').2
/-- Erasing a moved stored key recovers the original erased database's counts. -/
theorem cnt_erase_move_eq_of_sameCell {E : Finset (WithTop Key)} {db : DB} {k k' : Key}
(hsame : SameCell E k k') (hk : k ∈ db.keys) (hk' : k' ∉ db.keys)
{e : WithTop Key} (he : e ∈ E) :
cnt ((db.move k k' hk hk').erase k') e = cnt (db.erase k) e := by
have hk'_db' : k' ∈ (db.move k k' hk hk').keys := by
unfold DB.move
exact DB.mem_insert_self (db.erase k) k' _
have h1 := cnt_erase_eq (db.move k k' hk hk') k' hk'_db' e
have h2 := cnt_erase_eq db k hk e
have h3 := cnt_move_eq_of_sameCell hsame hk hk' he
have hlt := hsame e he
have hnat : (cnt ((db.move k k' hk hk').erase k') e : ℤ) = (cnt (db.erase k) e : ℤ) := by
rw [h1, h2, h3]
by_cases h : (k : WithTop Key) < e
· have h' : (k' : WithTop Key) < e := hlt.mp h
simp [h, h']
· have h' : ¬ (k' : WithTop Key) < e := fun hn => h (hlt.mpr hn)
simp [h, h']
exact_mod_cast hnat
/-- The key moved into the old key's place is absent from the moved database. -/
theorem not_mem_move_of_mem_not_mem {db : DB} {k k' : Key} (hk : k ∉ db.keys)
(hk' : k' ∈ db.keys) : k' ∉ (db.move k' k hk' hk).keys := by
unfold DB.move
rw [DB.insert_keys, List.mem_orderedInsert]
rintro (heq | hmem)
· exact hk (heq ▸ hk')
· exact (DB.mem_erase_iff.mp hmem).1 rfl
/-- Inserting an absent key after moving a stored key to its place gives the same
counts as inserting the originally absent key. -/
theorem cnt_insert_move_eq_of_sameCell {E : Finset (WithTop Key)} {db : DB} {k k' : Key}
(hsame : SameCell E k k') (hk : k ∉ db.keys) (hk' : k' ∈ db.keys)
(hins : k' ∉ (db.move k' k hk' hk).keys)
{e : WithTop Key} (he : e ∈ E) :
cnt ((db.move k' k hk' hk).insert k' hins) e = cnt (db.insert k hk) e := by
have hne : k' ≠ k := fun heq => hk (heq ▸ hk')
have hk'_db' : k' ∉ (db.move k' k hk' hk).keys := hins
have h1 := cnt_insert_eq (db.move k' k hk' hk) k' hins e
have h2 := cnt_insert_eq db k hk e
have h3 := cnt_move_eq_of_sameCell hsame.symm hk' hk he
have hlt := hsame e he
have hnat : (cnt ((db.move k' k hk' hk).insert k' hins) e : ℤ) =
(cnt (db.insert k hk) e : ℤ) := by
rw [h1, h2, h3]
by_cases h : (k : WithTop Key) < e
· have h' : (k' : WithTop Key) < e := hlt.mp h
simp [h, h']
· have h' : ¬ (k' : WithTop Key) < e := fun hn => h (hlt.mpr hn)
simp [h, h']
exact_mod_cast hnat
/-- The flip-witness property transfers to another key in the same cell. -/
theorem flipWitness_of_sameCell_forward {D : ConstraintDNF} {r : RangeRead} {res : Result}
(hchar : CharacterizesDNF D r res) {k k' : Key}
(hsame : SameCell (cellEndpoints D) k k') :
FlipWitness r res k → FlipWitness r res k' := by
intro hwit
by_cases hkk : k = k'
· simpa [hkk] using hwit
rw [flipWitness_iff_exists_not_anyHolds hchar] at hwit ⊢
obtain ⟨db, hcomp, hnot⟩ := hwit
have hE : dnfEndpoints D ⊆ cellEndpoints D := dnfEndpoints_subset_cellEndpoints D
by_cases hkmem : k ∈ db.keys
· by_cases hk'mem : k' ∈ db.keys
· refine ⟨db, hcomp, ?_⟩
rw [toggle_eq_erase_of_mem hkmem] at hnot
rw [toggle_eq_erase_of_mem hk'mem]
exact fun hany => hnot ((anyHolds_erase_of_sameCell hE hsame hkmem hk'mem).mpr hany)
· let db' := db.move k k' hkmem hk'mem
have hcomp' : RangeRead.Compatible db' r res := by
rw [hchar db']
exact ⟨hcomp.1,
(anyHolds_move_of_sameCell hE hsame hkmem hk'mem).mpr ((hchar db).mp hcomp).2⟩
refine ⟨db', hcomp', ?_⟩
have hk'_db' : k' ∈ db'.keys := by
unfold db' DB.move
exact DB.mem_insert_self (db.erase k) k' _
rw [toggle_eq_erase_of_mem hkmem] at hnot
rw [toggle_eq_erase_of_mem hk'_db']
have hcnt : ∀ e ∈ dnfEndpoints D, cnt (db'.erase k') e = cnt (db.erase k) e := by
intro e he
exact cnt_erase_move_eq_of_sameCell hsame hkmem hk'mem (hE he)
exact fun hany => hnot ((anyHolds_congr_endpoints hcnt).mp hany)
· by_cases hk'mem : k' ∈ db.keys
· have hins : k' ∉ (db.move k' k hk'mem hkmem).keys :=
not_mem_move_of_mem_not_mem hkmem hk'mem
let db' := db.move k' k hk'mem hkmem
have hcomp' : RangeRead.Compatible db' r res := by
rw [hchar db']
exact ⟨hcomp.1,
(anyHolds_move_of_sameCell hE hsame.symm hk'mem hkmem).mpr
((hchar db).mp hcomp).2⟩
refine ⟨db', hcomp', ?_⟩
rw [toggle_eq_insert_of_not_mem hkmem] at hnot
change ¬ AnyHolds D (toggle (db.move k' k hk'mem hkmem) k')
rw [toggle_eq_insert_of_not_mem hins]
have hcnt : ∀ e ∈ dnfEndpoints D,
cnt (db'.insert k' hins) e = cnt (db.insert k hkmem) e := by
intro e he
exact cnt_insert_move_eq_of_sameCell hsame hkmem hk'mem hins (hE he)
exact fun hany => hnot ((anyHolds_congr_endpoints hcnt).mp hany)
· refine ⟨db, hcomp, ?_⟩
rw [toggle_eq_insert_of_not_mem hkmem] at hnot
rw [toggle_eq_insert_of_not_mem hk'mem]
exact fun hany => hnot ((anyHolds_insert_of_sameCell hE hsame hkmem hk'mem).mpr hany)
/-- The flip-witness property is constant on a cell. -/
theorem flipWitness_of_sameCell {D : ConstraintDNF} {r : RangeRead} {res : Result}
(hchar : CharacterizesDNF D r res) {k k' : Key}
(hsame : SameCell (cellEndpoints D) k k') :
FlipWitness r res k ↔ FlipWitness r res k' :=
⟨flipWitness_of_sameCell_forward hchar hsame,
flipWitness_of_sameCell_forward hchar hsame.symm⟩
/-! ## The finite cell partition -/
/-- The least endpoint strictly above `e`, or `⊤` when there is none (which only
happens at `e = ⊤`). -/
noncomputable def nextEndpoint (E : Finset (WithTop Key)) (e : WithTop Key) : WithTop Key :=
if h : (E.filter fun x => e < x).Nonempty then Finset.min' _ h else ⊤
theorem nextEndpoint_mem (E : Finset (WithTop Key)) {e : WithTop Key} (he : e < ⊤)
(hTop : ⊤ ∈ E) : nextEndpoint E e ∈ E := by
unfold nextEndpoint
by_cases h : (E.filter fun x => e < x).Nonempty
· rw [dite_eq_left h]
exact (Finset.mem_filter.mp (Finset.min'_mem _ h)).1
· exact absurd ⟨⊤, Finset.mem_filter.mpr ⟨hTop, he⟩⟩ h
theorem lt_nextEndpoint (E : Finset (WithTop Key)) {e : WithTop Key} (he : e < ⊤)
(hTop : ⊤ ∈ E) : e < nextEndpoint E e := by
unfold nextEndpoint
by_cases h : (E.filter fun x => e < x).Nonempty
· rw [dite_eq_left h]
exact (Finset.mem_filter.mp (Finset.min'_mem _ h)).2
· exact absurd ⟨⊤, Finset.mem_filter.mpr ⟨hTop, he⟩⟩ h
theorem nextEndpoint_le (E : Finset (WithTop Key)) {e x : WithTop Key}
(hx : x ∈ E) (hex : e < x) : nextEndpoint E e ≤ x := by
unfold nextEndpoint
by_cases h : (E.filter fun x => e < x).Nonempty
· rw [dite_eq_left h]
exact Finset.min'_le _ _ (Finset.mem_filter.mpr ⟨hx, hex⟩)
· exact absurd ⟨x, Finset.mem_filter.mpr ⟨hx, hex⟩⟩ h
/-- The greatest endpoint at or below `k`. -/
noncomputable def cellLo (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (k : Key) : WithTop Key :=
Finset.max' (E.filter fun e => e ≤ (k : WithTop Key)) (by
refine ⟨(([] : Key) : WithTop Key), ?_⟩
rw [Finset.mem_filter]
exact ⟨hBot, by simp [nil_le_key]⟩)
theorem cellLo_mem (E : Finset (WithTop Key)) (hBot : (([] : Key) : WithTop Key) ∈ E)
(k : Key) : cellLo E hBot k ∈ E := by
unfold cellLo
exact (Finset.mem_filter.mp (Finset.max'_mem (E.filter fun e => e ≤ (k : WithTop Key)) _)).1
theorem cellLo_le (E : Finset (WithTop Key)) (hBot : (([] : Key) : WithTop Key) ∈ E)
(k : Key) : cellLo E hBot k ≤ (k : WithTop Key) := by
unfold cellLo
exact (Finset.mem_filter.mp (Finset.max'_mem (E.filter fun e => e ≤ (k : WithTop Key)) _)).2
theorem le_cellLo (E : Finset (WithTop Key)) (hBot : (([] : Key) : WithTop Key) ∈ E)
{k : Key} {e : WithTop Key} (he : e ∈ E) (hek : e ≤ (k : WithTop Key)) :
e ≤ cellLo E hBot k := by
unfold cellLo
exact Finset.le_max' _ _ (Finset.mem_filter.mpr ⟨he, hek⟩)
/-- The next endpoint after the cell's lower endpoint. -/
noncomputable def cellHi (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (k : Key) : WithTop Key :=
nextEndpoint E (cellLo E hBot k)
/-- A representative of `k`'s cell: the endpoint itself for a singleton cell,
otherwise the successor of the cell's lower endpoint. The second component is the
upper boundary of the cell. -/
noncomputable def cellRep (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (k : Key) : Key × WithTop Key :=
let lo := cellLo E hBot k
match lo with
| some l =>
if (k : WithTop Key) = lo then (k, keyAfter k)
else (keyAfter l, nextEndpoint E lo)
| none => (k, keyAfter k)
/-- The singleton-cell representative of a finite endpoint. -/
def singletonRep (e : WithTop Key) : Key × WithTop Key :=
match e with
| some l => (l, keyAfter l)
| none => (([] : Key), (([] : Key) : WithTop Key))
/-- The open-cell representative following a finite endpoint. -/
noncomputable def openRep (E : Finset (WithTop Key)) (e : WithTop Key) :
Key × WithTop Key :=
match e with
| some l => (keyAfter l, nextEndpoint E e)
| none => (([] : Key), (([] : Key) : WithTop Key))
/-- The finite set of cell representatives, with their upper boundaries. -/
noncomputable def cellReps (E : Finset (WithTop Key))
(_hBot : (([] : Key) : WithTop Key) ∈ E) (_hTop : ⊤ ∈ E) :
Finset (Key × WithTop Key) :=
let endpoints := E.filter fun e => e ≠ ⊤
((endpoints.image singletonRep) ∪ (endpoints.image (openRep E))).filter
fun p => (p.1 : WithTop Key) < p.2
theorem cellEndpoints_bot (D : ConstraintDNF) :
(([] : Key) : WithTop Key) ∈ cellEndpoints D := by
simp [cellEndpoints]
theorem cellEndpoints_top (D : ConstraintDNF) : ⊤ ∈ cellEndpoints D := by
simp [cellEndpoints]
theorem cellLo_lt_top (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (k : Key) :
cellLo E hBot k < (⊤ : WithTop Key) :=
lt_of_le_of_lt (cellLo_le E hBot k) (WithTop.coe_lt_top k)
theorem cellHi_gt (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (hTop : ⊤ ∈ E) (k : Key) :
(k : WithTop Key) < cellHi E hBot k := by
unfold cellHi
have hlo_lt_top : cellLo E hBot k < (⊤ : WithTop Key) := cellLo_lt_top E hBot k
have hlt : cellLo E hBot k < nextEndpoint E (cellLo E hBot k) :=
lt_nextEndpoint E hlo_lt_top hTop
have hmem : nextEndpoint E (cellLo E hBot k) ∈ E :=
nextEndpoint_mem E hlo_lt_top hTop
by_contra hnot
have hle : nextEndpoint E (cellLo E hBot k) ≤ (k : WithTop Key) := le_of_not_gt hnot
have hle_lo : nextEndpoint E (cellLo E hBot k) ≤ cellLo E hBot k :=
le_cellLo E hBot hmem hle
exact (not_lt_of_ge hle_lo) hlt
theorem cellRep_eq_singleton {E : Finset (WithTop Key)}
(hBot : (([] : Key) : WithTop Key) ∈ E) {k l : Key}
(hlo : cellLo E hBot k = (l : WithTop Key)) (hk : (k : WithTop Key) = (l : WithTop Key)) :
cellRep E hBot k = (k, (keyAfter k : WithTop Key)) := by
simp [cellRep, hlo, hk]
/-- If a key is itself an endpoint, it is the lower endpoint of its cell, so the
cell representative is the singleton representative `(k, keyAfter k)`. -/
theorem cellRep_of_mem_endpoints {E : Finset (WithTop Key)}
(hBot : (([] : Key) : WithTop Key) ∈ E) {k : Key}
(hk : (k : WithTop Key) ∈ E) :
cellRep E hBot k = (k, (keyAfter k : WithTop Key)) := by
have hlo : cellLo E hBot k = (k : WithTop Key) :=
le_antisymm (cellLo_le E hBot k) (le_cellLo E hBot hk le_rfl)
exact cellRep_eq_singleton hBot hlo rfl
theorem cellRep_eq_open {E : Finset (WithTop Key)}
(hBot : (([] : Key) : WithTop Key) ∈ E) {k l : Key}
(hlo : cellLo E hBot k = (l : WithTop Key)) (hk : (k : WithTop Key) ≠ (l : WithTop Key)) :
cellRep E hBot k = (keyAfter l, nextEndpoint E (l : WithTop Key)) := by
simp [cellRep, hlo, hk]
theorem cellRep_fst_le (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (k : Key) :
(cellRep E hBot k).1 ≤ k := by
dsimp only [cellRep]
split
· split
· exact le_refl k
· rename_i l hlo hne
change cellLo E hBot k = (l : WithTop Key) at hlo
have hle : (l : WithTop Key) ≤ (k : WithTop Key) := by
rw [← hlo]
exact cellLo_le E hBot k
have hne' : (k : WithTop Key) ≠ (l : WithTop Key) := by
rw [hlo] at hne
exact hne
have hlt : l < k := by
exact lt_of_le_of_ne (WithTop.coe_le_coe.mp hle) (fun heq => hne' (by rw [heq]))
exact le_of_not_gt fun hklt =>
(not_le_of_gt hlt) ((lt_keyAfter_iff k l).mp hklt)
· exact le_refl k
theorem cellRep_snd_gt (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (hTop : ⊤ ∈ E) (k : Key) :
(k : WithTop Key) < (cellRep E hBot k).2 := by
dsimp only [cellRep]
split
· split
· exact WithTop.coe_lt_coe.mpr (keyAfter_self_lt k)
· rename_i l hlo hne
change cellLo E hBot k = (l : WithTop Key) at hlo
have hlt : (k : WithTop Key) < nextEndpoint E (l : WithTop Key) := by
have h := cellHi_gt E hBot hTop k
unfold cellHi at h
exact hlo ▸ h
dsimp only
rw [hlo]
exact hlt
· exact WithTop.coe_lt_coe.mpr (keyAfter_self_lt k)
theorem cellRep_sameCell (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (k : Key) :
SameCell E k (cellRep E hBot k).1 := by
dsimp only [cellRep]
split
· rename_i l hlo
split
· rename_i hk
change cellLo E hBot k = (l : WithTop Key) at hlo
have hkl : k = l := WithTop.coe_inj.mp (by simpa [hlo] using hk)
subst k
exact SameCell.refl E l
· rename_i hne
change cellLo E hBot k = (l : WithTop Key) at hlo
change SameCell E k (keyAfter l)
intro e he
have hle : (l : WithTop Key) ≤ (k : WithTop Key) := by
rw [← hlo]
exact cellLo_le E hBot k
have hlk : l < k := by
have hne' : (k : WithTop Key) ≠ (l : WithTop Key) := by
rw [hlo] at hne
exact hne
exact lt_of_le_of_ne (WithTop.coe_le_coe.mp hle) (fun heq => hne' (by rw [heq]))
have hkey_le : (keyAfter l : WithTop Key) ≤ (k : WithTop Key) :=
WithTop.coe_le_coe.mpr <| le_of_not_gt fun hklt =>
(not_le_of_gt hlk) ((lt_keyAfter_iff k l).mp hklt)
constructor
· intro hke
exact lt_of_le_of_lt hkey_le hke
· intro hkeye
by_contra hke
have hek : (e : WithTop Key) ≤ (k : WithTop Key) := le_of_not_gt hke
have hele : e ≤ cellLo E hBot k := le_cellLo E hBot he hek
have hle' : (l : WithTop Key) < e :=
lt_trans (WithTop.coe_lt_coe.mpr (keyAfter_self_lt l)) hkeye
rw [hlo] at hele
exact (not_lt_of_ge hele) hle'
· rename_i hnone
have hcontra : cellLo E hBot k < (⊤ : WithTop Key) := cellLo_lt_top E hBot k
rw [hnone] at hcontra
exact absurd hcontra (lt_irrefl ⊤)
theorem cellRep_mem_cellReps (E : Finset (WithTop Key))
(hBot : (([] : Key) : WithTop Key) ∈ E) (hTop : ⊤ ∈ E) (k : Key) :
cellRep E hBot k ∈ cellReps E hBot hTop := by
dsimp only [cellRep]
split
· split
· rename_i l hlo hk
change cellLo E hBot k = (l : WithTop Key) at hlo
have hmem : (l : WithTop Key) ∈ E := by rw [← hlo]; exact cellLo_mem E hBot k
have hkl : k = l := WithTop.coe_inj.mp (by simpa [hlo] using hk)
subst k
have hne : (l : WithTop Key) ≠ ⊤ := by simp
have hlt : (l : WithTop Key) < (keyAfter l : WithTop Key) :=
WithTop.coe_lt_coe.mpr (keyAfter_self_lt l)
refine Finset.mem_filter.mpr ⟨?_, hlt⟩
exact Finset.mem_union.mpr (Or.inl (Finset.mem_image.mpr
⟨(l : WithTop Key), Finset.mem_filter.mpr ⟨hmem, hne⟩, by simp [singletonRep]⟩))
· rename_i l hlo hne
change cellLo E hBot k = (l : WithTop Key) at hlo
have hmem : (l : WithTop Key) ∈ E := by rw [← hlo]; exact cellLo_mem E hBot k
have hne_top : (l : WithTop Key) ≠ ⊤ := by simp
have hle : (l : WithTop Key) ≤ (k : WithTop Key) := by
rw [← hlo]
exact cellLo_le E hBot k
have hlk : l < k := by
have hne' : (k : WithTop Key) ≠ (l : WithTop Key) := by
rw [hlo] at hne
exact hne
exact lt_of_le_of_ne (WithTop.coe_le_coe.mp hle) (fun heq => hne' (by rw [heq]))
have hkey_le : (keyAfter l : WithTop Key) ≤ (k : WithTop Key) :=
WithTop.coe_le_coe.mpr <| le_of_not_gt fun hklt =>
(not_le_of_gt hlk) ((lt_keyAfter_iff k l).mp hklt)
have hk_hi : (k : WithTop Key) < nextEndpoint E (l : WithTop Key) := by
have h := cellHi_gt E hBot hTop k
unfold cellHi at h
exact hlo ▸ h
have hlt : (keyAfter l : WithTop Key) < nextEndpoint E (l : WithTop Key) :=
lt_of_le_of_lt hkey_le hk_hi
rw [hlo]
refine Finset.mem_filter.mpr ⟨?_, hlt⟩
exact Finset.mem_union.mpr (Or.inr (Finset.mem_image.mpr
⟨(l : WithTop Key), Finset.mem_filter.mpr ⟨hmem, hne_top⟩, by simp [openRep]⟩))
· rename_i hnone
have hcontra : cellLo E hBot k < (⊤ : WithTop Key) := cellLo_lt_top E hBot k
rw [hnone] at hcontra
exact absurd hcontra (lt_irrefl ⊤)
/-- Every representative in `cellReps` is either a singleton rep or an open rep. -/
theorem mem_cellReps_cases {E : Finset (WithTop Key)}
(hBot : (([] : Key) : WithTop Key) ∈ E) (hTop : ⊤ ∈ E)
{p : Key × WithTop Key} (hp : p ∈ cellReps E hBot hTop) :
(∃ l : Key, (l : WithTop Key) ∈ E ∧ p = (l, (keyAfter l : WithTop Key))) ∨
(∃ l : Key, (l : WithTop Key) ∈ E ∧
p = (keyAfter l, nextEndpoint E (l : WithTop Key))) := by
unfold cellReps at hp
rw [Finset.mem_filter] at hp
obtain ⟨hunion, hlt⟩ := hp
rcases Finset.mem_union.mp hunion with hsingle | hopen
· obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hsingle
obtain ⟨heE, hne⟩ := Finset.mem_filter.mp he
cases e with
| coe l =>
exact Or.inl ⟨l, by simpa using heE, by simp [singletonRep]⟩
| top =>
simp [singletonRep] at hlt
· obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hopen
obtain ⟨heE, hne⟩ := Finset.mem_filter.mp he
cases e with
| coe l =>
exact Or.inr ⟨l, by simpa using heE, by simp [openRep]⟩
| top =>
simp [openRep] at hlt
/-- A key lying in a representative's interval is in the same cell as the
representative. -/
theorem sameCell_of_mem_cellReps {E : Finset (WithTop Key)}
(hBot : (([] : Key) : WithTop Key) ∈ E) (hTop : ⊤ ∈ E)
{p : Key × WithTop Key} (hp : p ∈ cellReps E hBot hTop) {k : Key}
(hlo : p.1 ≤ k) (hhi : (k : WithTop Key) < p.2) :
SameCell E k p.1 := by
rcases mem_cellReps_cases hBot hTop hp with ⟨l, hlE, rfl⟩ | ⟨l, hlE, rfl⟩
· -- singleton rep: the half-open interval [l, keyAfter l) contains only l
change SameCell E k l
change l ≤ k at hlo
change (k : WithTop Key) < (keyAfter l : WithTop Key) at hhi
have hkl : k = l := by
have hk_lt : k < keyAfter l := WithTop.coe_lt_coe.mp hhi
exact le_antisymm ((lt_keyAfter_iff k l).mp hk_lt) hlo
subst k
exact SameCell.refl E l
· -- open rep: no endpoint lies strictly between `l` and the next endpoint
change SameCell E k (keyAfter l)
change keyAfter l ≤ k at hlo
change (k : WithTop Key) < nextEndpoint E (l : WithTop Key) at hhi
intro e he
constructor
· intro hke
exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr hlo) hke
· intro hkeye
have hlkey : (l : WithTop Key) < (keyAfter l : WithTop Key) :=
WithTop.coe_lt_coe.mpr (keyAfter_self_lt l)
have hle : (l : WithTop Key) < e := lt_trans hlkey hkeye
by_contra hnot
have hle' : e ≤ (k : WithTop Key) := le_of_not_gt hnot
have hnext_le : nextEndpoint E (l : WithTop Key) ≤ e :=
nextEndpoint_le E he hle
have he_lt : e < nextEndpoint E (l : WithTop Key) :=
lt_of_le_of_lt hle' hhi
exact (not_lt_of_ge hnext_le) he_lt
/-! ## Toggling a list of keys -/
/-- Toggle each key in a list, in order. -/
def toggleList (db : DB) : List Key → DB
| [] => db
| k :: ks => toggleList (toggle db k) ks
/-- Membership after a single toggle. -/
theorem mem_toggle_keys {db : DB} {k x : Key} :
x ∈ (toggle db k).keys ↔ (x = k ∧ x ∉ db.keys) ∨ (x ≠ k ∧ x ∈ db.keys) := by
by_cases hx : x = k
· subst x
by_cases hk : k ∈ db.keys
· rw [toggle_eq_erase_of_mem hk]
have hnot' : k ∉ db.keys.erase k := db.nodup.not_mem_erase
simp [hnot', hk]
· rw [toggle_eq_insert_of_not_mem hk]
simp [hk]
· by_cases hk : k ∈ db.keys
· rw [toggle_eq_erase_of_mem hk, DB.mem_erase_iff]
simp [hx]
· rw [toggle_eq_insert_of_not_mem hk, DB.mem_insert_iff hk]
simp [hx]
/-- Toggling a duplicate-free list once gives the expected membership: a key of
the list is present exactly when it was absent before, and every other key is
unchanged. -/
theorem mem_toggleList_keys {db : DB} {ks : List Key} (hnd : ks.Nodup) (x : Key) :
x ∈ (toggleList db ks).keys ↔
if x ∈ ks then x ∉ db.keys else x ∈ db.keys := by
induction ks generalizing db with
| nil => simp [toggleList]
| cons k ks ih =>
rw [List.nodup_cons] at hnd
obtain ⟨hknot, hnd'⟩ := hnd
simp only [toggleList]
rw [ih hnd']
by_cases hx : x = k
· subst x
have hxks : k ∉ ks := hknot
simp [List.mem_cons, hxks, mem_toggle_keys]
· have hxtoggle : x ∈ (toggle db k).keys ↔ x ∈ db.keys := by
rw [mem_toggle_keys]
simp [hx]
by_cases hxks : x ∈ ks
· simp [List.mem_cons, hx, hxks, hxtoggle]
· simp [List.mem_cons, hx, hxks, hxtoggle]
/-- A list-toggle preserves sortedness. -/
theorem toggleList_sorted (db : DB) (ks : List Key) : (toggleList db ks).keys.SortedLT := by
induction ks generalizing db with
| nil => exact db.sorted
| cons k ks ih => exact ih (toggle db k)
/-! ## The active cells and their hull -/
/-- The representatives of the cells that admit a one-key flip witness. -/
noncomputable def activeReps (r : RangeRead) (res : Result) (D : ConstraintDNF) :
Finset (Key × WithTop Key) := by
classical
exact (cellReps (cellEndpoints D) (cellEndpoints_bot D) (cellEndpoints_top D)).filter
(fun p => FlipWitness r res p.1)
/-- The least key among the active cell representatives. -/
noncomputable def activeBegin (A : Finset (Key × WithTop Key)) (h : A.Nonempty) : Key :=
(A.image fun p => p.1).min' (h.image fun p => p.1)
/-- The greatest upper boundary among the active cell representatives. -/
noncomputable def activeEnd (A : Finset (Key × WithTop Key)) (h : A.Nonempty) : WithTop Key :=
(A.image fun p => p.2).max' (h.image fun p => p.2)
/-- The hull of the active cells, from the least active key to the greatest active
upper boundary. When there are no active cells this is the empty range. -/
noncomputable def flipHull (r : RangeRead) (res : Result) (D : ConstraintDNF) :
ConflictRange := by
classical
let A := activeReps r res D
exact if h : A.Nonempty then
⟨(activeBegin A h : WithTop Key), activeEnd A h⟩
else
⟨(([] : Key) : WithTop Key), (([] : Key) : WithTop Key)⟩
theorem activeReps_mem_iff {r : RangeRead} {res : Result} {D : ConstraintDNF}
{p : Key × WithTop Key} :
p ∈ activeReps r res D ↔
p ∈ cellReps (cellEndpoints D) (cellEndpoints_bot D) (cellEndpoints_top D) ∧
FlipWitness r res p.1 := by
classical
unfold activeReps
rw [Finset.mem_filter]
theorem cellRep_mem_activeReps_iff {r : RangeRead} {res : Result} {D : ConstraintDNF}
(hchar : CharacterizesDNF D r res) {k : Key} :
cellRep (cellEndpoints D) (cellEndpoints_bot D) k ∈ activeReps r res D ↔
FlipWitness r res k := by
rw [activeReps_mem_iff]
have hsame : SameCell (cellEndpoints D) k
(cellRep (cellEndpoints D) (cellEndpoints_bot D) k).1 :=
cellRep_sameCell (cellEndpoints D) (cellEndpoints_bot D) k
have hiff := flipWitness_of_sameCell hchar hsame
constructor
· rintro ⟨_, hw⟩
exact hiff.mpr hw
· intro hw
exact ⟨cellRep_mem_cellReps (cellEndpoints D) (cellEndpoints_bot D)
(cellEndpoints_top D) k, hiff.mp hw⟩
theorem activeBegin_le {A : Finset (Key × WithTop Key)} {h : A.Nonempty}
{p : Key × WithTop Key} (hp : p ∈ A) : activeBegin A h ≤ p.1 := by
unfold activeBegin
exact Finset.min'_le _ _ (Finset.mem_image.mpr ⟨p, hp, rfl⟩)
theorem le_activeEnd {A : Finset (Key × WithTop Key)} {h : A.Nonempty}
{p : Key × WithTop Key} (hp : p ∈ A) : p.2 ≤ activeEnd A h := by
unfold activeEnd
exact Finset.le_max' _ _ (Finset.mem_image.mpr ⟨p, hp, rfl⟩)
theorem flipHull_eq_active {r : RangeRead} {res : Result} {D : ConstraintDNF}
{h : (activeReps r res D).Nonempty} :
flipHull r res D =
⟨(activeBegin (activeReps r res D) h : WithTop Key),
activeEnd (activeReps r res D) h⟩ := by
classical
unfold flipHull
rw [dite_eq_left h]
theorem flipHull_eq_empty {r : RangeRead} {res : Result} {D : ConstraintDNF}
(h : ¬ (activeReps r res D).Nonempty) :
flipHull r res D =
⟨(([] : Key) : WithTop Key), (([] : Key) : WithTop Key)⟩ := by
classical
unfold flipHull
rw [dite_eq_right h]
set_option maxHeartbeats 1000000 in
-- Unfolding the hull's endpoint expressions is expensive; give this declaration room.
theorem active_cellRep_inside_hull {r : RangeRead} {res : Result} {D : ConstraintDNF}
{k : Key} (ha : cellRep (cellEndpoints D) (cellEndpoints_bot D) k ∈
activeReps r res D) :
k ∈ flipHull r res D := by
classical
let A := activeReps r res D
have hne : A.Nonempty := ⟨_, ha⟩
rw [flipHull_eq_active (h := hne)]
rw [ConflictRange.mem_iff]
constructor
· exact le_trans (WithTop.coe_le_coe.mpr (activeBegin_le ha))
(WithTop.coe_le_coe.mpr (cellRep_fst_le (cellEndpoints D)
(cellEndpoints_bot D) k))
· exact lt_of_lt_of_le (cellRep_snd_gt (cellEndpoints D) (cellEndpoints_bot D)
(cellEndpoints_top D) k) (le_activeEnd (h := hne) ha)
theorem not_flipWitness_of_not_mem_hull {r : RangeRead} {res : Result} {D : ConstraintDNF}
(hchar : CharacterizesDNF D r res) {k : Key} (hk : k ∉ flipHull r res D) :
¬ FlipWitness r res k := by
intro hw
have ha : cellRep (cellEndpoints D) (cellEndpoints_bot D) k ∈ activeReps r res D :=
(cellRep_mem_activeReps_iff hchar).mpr hw
exact hk (active_cellRep_inside_hull ha)
theorem compatible_toggle_of_not_mem_hull {r : RangeRead} {res : Result} {D : ConstraintDNF}
(hchar : CharacterizesDNF D r res) {db : DB} {k : Key}
(hcomp : RangeRead.Compatible db r res) (hk : k ∉ flipHull r res D) :
RangeRead.Compatible (toggle db k) r res := by
by_contra hnot
exact not_flipWitness_of_not_mem_hull hchar hk ⟨db, hcomp, hnot⟩
theorem compatible_toggleList_of_forall_not_mem_hull {r : RangeRead} {res : Result}
{D : ConstraintDNF} (hchar : CharacterizesDNF D r res) {db : DB} {ks : List Key}
(hcomp : RangeRead.Compatible db r res)
(hks : ∀ k ∈ ks, k ∉ flipHull r res D) :
RangeRead.Compatible (toggleList db ks) r res := by
induction ks generalizing db with
| nil => simpa [toggleList] using hcomp
| cons k ks ih =>
simp only [toggleList]
exact ih (compatible_toggle_of_not_mem_hull hchar hcomp (hks k (by simp)))
(fun x hx => hks x (by simp [hx]))
/-! ## The symmetric-difference toggle path -/
/-- The keys whose membership differs between two databases. -/
def diffKeys (db₁ db₂ : DB) : List Key :=
(db₁.keys.filter fun k => decide (k ∉ db₂.keys)) ++
(db₂.keys.filter fun k => decide (k ∉ db₁.keys))
theorem mem_diffKeys {db₁ db₂ : DB} {k : Key} :
k ∈ diffKeys db₁ db₂ ↔
(k ∈ db₁.keys ∧ k ∉ db₂.keys) ∨ (k ∉ db₁.keys ∧ k ∈ db₂.keys) := by
unfold diffKeys
rw [List.mem_append, List.mem_filter, List.mem_filter]
simp only [decide_eq_true_eq]
constructor
· rintro (⟨h1, h2⟩ | ⟨h1, h2⟩)
· exact Or.inl ⟨h1, h2⟩
· exact Or.inr ⟨h2, h1⟩
· rintro (⟨h1, h2⟩ | ⟨h1, h2⟩)
· exact Or.inl ⟨h1, h2⟩
· exact Or.inr ⟨h2, h1⟩
theorem diffKeys_nodup (db₁ db₂ : DB) : (diffKeys db₁ db₂).Nodup := by
unfold diffKeys
rw [List.nodup_append]
refine ⟨db₁.nodup.filter _, db₂.nodup.filter _, ?_⟩
intro a ha b hb heq
subst b
have ha₁ : a ∈ db₁.keys := (List.mem_filter.mp ha).1
have hb₁ : a ∉ db₁.keys := of_decide_eq_true (List.mem_filter.mp hb).2
exact hb₁ ha₁
theorem diffKeys_not_mem_of_agreeOn {cr : ConflictRange} {db₁ db₂ : DB}
(h : AgreeOn cr db₁ db₂) {k : Key} (hk : k ∈ cr) :
k ∉ diffKeys db₁ db₂ := by
rw [mem_diffKeys]
rintro (⟨h1, h2⟩ | ⟨h1, h2⟩)
· exact h2 (((agreeOn_iff cr db₁ db₂).mp h k hk).mp h1)
· exact h1 (((agreeOn_iff cr db₁ db₂).mp h k hk).mpr h2)
theorem toggleList_diffKeys_keys (db₁ db₂ : DB) :
(toggleList db₁ (diffKeys db₁ db₂)).keys = db₂.keys := by
apply List.SortedLT.eq_of_mem_iff (toggleList_sorted db₁ (diffKeys db₁ db₂)) db₂.sorted
intro x
rw [mem_toggleList_keys (diffKeys_nodup db₁ db₂) x]
by_cases h1 : x ∈ db₁.keys <;> by_cases h2 : x ∈ db₂.keys
· have hx : x ∉ diffKeys db₁ db₂ := by
rw [mem_diffKeys]; tauto
simp [hx, h1, h2]
· have hx : x ∈ diffKeys db₁ db₂ := by
rw [mem_diffKeys]; exact Or.inl ⟨h1, h2⟩
simp [hx, h1, h2]
· have hx : x ∈ diffKeys db₁ db₂ := by
rw [mem_diffKeys]; exact Or.inr ⟨h1, h2⟩
simp [hx, h1, h2]
· have hx : x ∉ diffKeys db₁ db₂ := by
rw [mem_diffKeys]; tauto
simp [hx, h1, h2]
/-! ## Soundness and necessity of the hull -/
theorem flipHull_sound {D : ConstraintDNF} {r : RangeRead} {res : Result}
(hchar : CharacterizesDNF D r res) : Sound r res (flipHull r res D) := by
intro db₁ db₂ hagree
constructor
· intro hcomp₁
let ks := diffKeys db₁ db₂
have hks : ∀ k ∈ ks, k ∉ flipHull r res D := by
intro k hk hkcr
exact diffKeys_not_mem_of_agreeOn (cr := flipHull r res D) hagree hkcr hk
have hcomp_tl := compatible_toggleList_of_forall_not_mem_hull hchar hcomp₁ hks
have hkeys := toggleList_diffKeys_keys db₁ db₂
exact (RangeRead.compatible_congr (RangeRead.completeKeys_congr hkeys r)).mp hcomp_tl
· intro hcomp₂
let ks := diffKeys db₂ db₁
have hks : ∀ k ∈ ks, k ∉ flipHull r res D := by
intro k hk hkcr
exact diffKeys_not_mem_of_agreeOn (cr := flipHull r res D)
(AgreeOn.symm hagree) hkcr hk
have hcomp_tl := compatible_toggleList_of_forall_not_mem_hull hchar hcomp₂ hks
have hkeys := toggleList_diffKeys_keys db₂ db₁
exact (RangeRead.compatible_congr (RangeRead.completeKeys_congr hkeys r)).mp hcomp_tl
set_option maxHeartbeats 1000000 in
-- Unfolding the hull's endpoint expressions is expensive; give this declaration room.
theorem necessary_of_mem_flipHull {D : ConstraintDNF} {r : RangeRead} {res : Result}
(hchar : CharacterizesDNF D r res) {k : Key} (hk : k ∈ flipHull r res D) :
Necessary r res k := by
classical
let A := activeReps r res D
have hne : A.Nonempty := by
by_contra hA
rw [flipHull_eq_empty (h := hA)] at hk
rw [ConflictRange.mem_iff] at hk
exact (not_lt_of_ge hk.1) hk.2
rw [flipHull_eq_active (h := hne)] at hk
have hmin_mem : activeBegin A hne ∈ A.image (fun p => p.1) := Finset.min'_mem _ _
obtain ⟨p, hpA, hpkey⟩ := Finset.mem_image.mp hmin_mem
have hp_le : p.1 ≤ k := by
have h := hk.1
rw [← hpkey] at h
exact WithTop.coe_le_coe.mp h
by_cases hcell : ∃ p ∈ A, p.1 ≤ k ∧ (k : WithTop Key) < p.2
· obtain ⟨p, hpA, hlo, hhi⟩ := hcell
have hpcell : p ∈ cellReps (cellEndpoints D) (cellEndpoints_bot D)
(cellEndpoints_top D) := ((activeReps_mem_iff).mp hpA).1
have hsame : SameCell (cellEndpoints D) k p.1 :=
sameCell_of_mem_cellReps (cellEndpoints_bot D) (cellEndpoints_top D) hpcell hlo hhi
have hpw : FlipWitness r res p.1 := ((activeReps_mem_iff).mp hpA).2
exact necessary_of_toggle ((flipWitness_of_sameCell hchar hsame).mpr hpw)
· have hmax_mem : activeEnd A hne ∈ A.image (fun p => p.2) := Finset.max'_mem _ _
obtain ⟨q, hqA, hqend⟩ := Finset.mem_image.mp hmax_mem
have hqle : ¬ q.1 ≤ k := by
intro hqk
exact hcell ⟨q, hqA, hqk, by rw [hqend]; exact hk.2⟩
have hkq : k < q.1 := lt_of_not_ge hqle
have hp_nec : Necessary r res p.1 :=
necessary_of_toggle ((activeReps_mem_iff).mp hpA).2
have hq_nec : Necessary r res q.1 :=
necessary_of_toggle ((activeReps_mem_iff).mp hqA).2
exact Necessary.of_between hp_nec hq_nec hp_le (le_of_lt hkq)
theorem necessarySet_eq_flipHull {D : ConstraintDNF} {r : RangeRead} {res : Result}
(hchar : CharacterizesDNF D r res) :
(flipHull r res D).toSet = necessarySet r res := by
ext k
constructor
· intro hk
exact necessary_of_mem_flipHull hchar hk
· intro hk
exact hk (flipHull r res D) (flipHull_sound hchar)
theorem exists_minimal_of_characterizes {D : ConstraintDNF} {r : RangeRead} {res : Result}
(hchar : CharacterizesDNF D r res) :
∃ cr : ConflictRange, Minimal r res cr :=
exists_minimal_of_necessarySet_representable
⟨flipHull r res D, necessarySet_eq_flipHull hchar⟩
/-- The flip hull of a characterizing DNF is itself minimal, not merely some range
whose existence follows from the characterization. -/
theorem minimal_flipHull {D : ConstraintDNF} {r : RangeRead} {res : Result}
(hchar : CharacterizesDNF D r res) :
Minimal r res (flipHull r res D) :=
(minimal_iff_sound_and_necessary).mpr
⟨flipHull_sound hchar, fun _ hk => necessary_of_mem_flipHull hchar hk⟩
/-- **The headline, unconditional on a readable read.** Every read/result pair
that is realized by some database has a minimal conflict range. The characterizing
DNF is `emptyConstraints` for the empty result and the precise collector otherwise;
the general flip-witness hull then represents the necessary keys. -/
theorem exists_minimal_conflict_range_of_readable {r : RangeRead} {res : Result}
(hread : Readable r res) : ∃ cr : ConflictRange, Minimal r res cr := by
obtain ⟨db, hcomp⟩ := hread
by_cases hne : res.keys = []
· have hmore : res.more = false := by
by_contra hm
have hmtrue : res.more = true := by
cases h : res.more
· exact absurd h hm
· rfl
exact (RangeRead.compatible_ne_nil_of_more hcomp hmtrue) hne
have hres : res = emptyRes := by
cases res with
| mk ks more =>
simp at hne
subst ks
have hmore' : more = false := by simpa using hmore
subst more
rfl
have hchar : CharacterizesDNF (emptyConstraints r) r res := by
rw [hres]
exact characterizesDNF_emptyConstraints r
exact exists_minimal_of_characterizes hchar
· have hA : ascendingKeys r res ≠ [] := ascendingKeys_ne_nil hne
have hpair : (ascendingKeys r res).Pairwise (· < ·) :=
pairwise_ascendingKeys ⟨db, hcomp⟩ hne
exact exists_minimal_of_characterizes
(characterizesDNF_collectOf (r := r) (res := res) hA hpair)
/-! ## The general algorithm
The algorithm is not a table of offset cases. It is the cellwise flip-witness hull
of a characterizing DNF: partition the key space at the DNF endpoints, mark a cell
active when a one-key toggle in that cell breaks the DNF, and take the hull of the
active cells. The characterizing DNF is `emptyConstraints` for the empty result and
the precise collector otherwise.
The definition below is noncomputable only because `FlipWitness` is an existential
over databases. The cellwise shape is the complete algorithm statement; an
executable version replaces `FlipWitness` by a decision procedure for active cells. -/
/-- The characterizing DNF used by the general algorithm: the empty theory for an
empty result and the precise collector for a nonempty result. -/
def characterizingDNF (r : RangeRead) (res : Result) : ConstraintDNF :=
if res.keys = [] then emptyConstraints r
else collectOf r (ascendingKeys r res) res.more
/-- The DNF produced by `characterizingDNF` characterizes every readable pair. -/
theorem characterizesDNF_characterizingDNF {r : RangeRead} {res : Result}
(hread : Readable r res) :
CharacterizesDNF (characterizingDNF r res) r res := by
obtain ⟨db, hcomp⟩ := hread
unfold characterizingDNF
by_cases hne : res.keys = []
· have hmore : res.more = false := by
by_contra hm
have hmtrue : res.more = true := by
cases h : res.more
· exact absurd h hm
· rfl
exact (RangeRead.compatible_ne_nil_of_more hcomp hmtrue) hne
have hres : res = emptyRes := by
cases res with
| mk ks more =>
simp at hne
subst ks
have hmore' : more = false := by simpa using hmore
subst more
rfl
rw [ite_eq_left hne, hres]
exact characterizesDNF_emptyConstraints r
· have hA : ascendingKeys r res ≠ [] := ascendingKeys_ne_nil hne
have hpair : (ascendingKeys r res).Pairwise (· < ·) :=
pairwise_ascendingKeys ⟨db, hcomp⟩ hne
rw [ite_eq_right hne]
exact characterizesDNF_collectOf (r := r) (res := res) hA hpair
/-- **The general conflict-range algorithm.** Take the cellwise flip-witness hull
of the characterizing DNF. This is the offset-free specification: the endpoint
cells, their active statuses, and the hull are the whole algorithm. -/
noncomputable def conflictRangeGeneral (r : RangeRead) (res : Result) : ConflictRange :=
flipHull r res (characterizingDNF r res)
/-- **The general algorithm is correct.** On every readable pair it returns a
minimal conflict range. The proof is the characterization lemma together with the
flip-hull minimality theorem; no offset case analysis is involved. -/
theorem conflictRangeGeneral_minimal {r : RangeRead} {res : Result}
(hread : Readable r res) :
Minimal r res (conflictRangeGeneral r res) :=
minimal_flipHull (characterizesDNF_characterizingDNF hread)
/-- A Boolean activity oracle is correct when it accepts exactly the keys with a
one-key flip witness. This is the only interface the cellwise algorithm consumes;
constructing such an oracle is the remaining implementation task. -/
def ActiveDecider (r : RangeRead) (res : Result) (active : Key → Bool) : Prop :=
∀ k, active k = true ↔ FlipWitness r res k
/-- The cell representatives selected by a Boolean activity oracle. This is the
computational shape of `activeReps`: the only difference is that `FlipWitness` is
replaced by a decision procedure. -/
noncomputable def activeRepsOf (D : ConstraintDNF) (active : Key → Bool) :
Finset (Key × WithTop Key) :=
(cellReps (cellEndpoints D) (cellEndpoints_bot D) (cellEndpoints_top D)).filter
(fun p => active p.1)
/-- The hull of a finite set of cell representatives. This is the endpoint
extraction used by both `flipHull` and the oracle-driven algorithm. -/
noncomputable def hullOfActiveReps (A : Finset (Key × WithTop Key)) : ConflictRange :=
if h : A.Nonempty then
⟨(activeBegin A h : WithTop Key), activeEnd A h⟩
else
⟨(([] : Key) : WithTop Key), (([] : Key) : WithTop Key)⟩
/-- The cellwise algorithm with an abstract activity oracle. It is the executable
shape of `conflictRangeGeneral`: once `active r res` is a decision procedure for
`FlipWitness r res`, this definition computes the hull. -/
noncomputable def conflictRangeCellwise (r : RangeRead) (res : Result)
(active : Key → Bool) : ConflictRange :=
hullOfActiveReps (activeRepsOf (characterizingDNF r res) active)
theorem activeRepsOf_eq_activeReps {D : ConstraintDNF} {r : RangeRead} {res : Result}
{active : Key → Bool}
(hactive : ActiveDecider r res active) :
activeRepsOf D active = activeReps r res D := by
ext p
simp only [activeRepsOf, activeReps, Finset.mem_filter]
exact ⟨fun h => ⟨h.1, (hactive p.1).mp h.2⟩,
fun h => ⟨h.1, (hactive p.1).mpr h.2⟩⟩
theorem hullOfActiveReps_eq_flipHull {D : ConstraintDNF} {r : RangeRead} {res : Result}
{active : Key → Bool}
(hactive : ActiveDecider r res active) :
hullOfActiveReps (activeRepsOf D active) = flipHull r res D := by
unfold hullOfActiveReps flipHull
rw [activeRepsOf_eq_activeReps (D := D) hactive]
/-- The oracle-driven cellwise algorithm is the general algorithm, provided the
oracle decides exactly the one-key flip witnesses. -/
theorem conflictRangeCellwise_eq_general {r : RangeRead} {res : Result}
{active : Key → Bool}
(hactive : ActiveDecider r res active) :
conflictRangeCellwise r res active = conflictRangeGeneral r res := by
unfold conflictRangeCellwise conflictRangeGeneral
exact hullOfActiveReps_eq_flipHull (D := characterizingDNF r res) hactive
/-- **Correctness of the oracle-driven cellwise algorithm.** If the activity
oracle decides `FlipWitness` exactly, then the cellwise hull is minimal on every
readable pair. This isolates the only remaining implementation obligation: build
and prove such an oracle (for example, the region-count/DBM test). -/
theorem conflictRangeCellwise_minimal {r : RangeRead} {res : Result}
{active : Key → Bool}
(hactive : ActiveDecider r res active)
(hread : Readable r res) :
Minimal r res (conflictRangeCellwise r res active) := by
rw [conflictRangeCellwise_eq_general hactive]
exact conflictRangeGeneral_minimal hread
/-- The active-cell algorithm computes exactly the necessary set. This is the
general-principle correctness statement: the hull of the active cells is the set of
keys forced by every sound range. -/
theorem conflictRangeCellwise_toSet_eq_necessarySet {r : RangeRead} {res : Result}
{active : Key → Bool}
(hactive : ActiveDecider r res active)
(hread : Readable r res) :
(conflictRangeCellwise r res active).toSet = necessarySet r res := by
rw [conflictRangeCellwise_eq_general hactive]
exact necessarySet_eq_flipHull (characterizesDNF_characterizingDNF hread)
end FormalConflictRange