Something went wrong. Try again.
forked from verus-lang/verus
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082#[allow(unused_imports)]use super::map::*;#[allow(unused_imports)]use super::pervasive::*;#[allow(unused_imports)]use super::prelude::*;
verus! {
/// `ISet<A>` is a set type for specifications.////// An object `set: ISet<A>` is a subset of the set of all values `a: A`./// Equivalently, it can be thought of as a boolean predicate on `A`.////// In general, a set might be infinite./// To work specifically with finite sets, see the [`self.finite()`](ISet::finite) predicate.////// ISets can be constructed in a few different ways:/// * [`ISet::empty`] gives an empty set/// * [`ISet::full`] gives the set of all elements in `A`/// * [`ISet::new`] constructs a set from a boolean predicate/// * The [`iset!`] macro, to construct small sets of a fixed size/// * By manipulating an existing sequence with [`ISet::union`], [`ISet::intersect`],/// [`ISet::difference`], [`ISet::complement`], [`ISet::filter`], [`ISet::insert`],/// or [`ISet::remove`].////// To prove that two sequences are equal, it is usually easiest to use the extensionality/// operator `=~=`.#[verifier::ext_equal]#[verifier::reject_recursive_types(A)]#[cfg_attr(verus_keep_ghost, rustc_diagnostic_item = "verus::vstd::iset::ISet")]pub struct ISet<A> { set: spec_fn(A) -> bool,}
impl<A> ISet<A> { /// The "empty" set. /// /// Usage Example: <br> /// ```rust /// let empty_set = ISet::<A>::empty(); /// /// assert(empty_set.is_empty()); /// assert(empty_set.complement() =~= ISet::<A>::full()); /// assert(ISet::<A>::empty().finite()); /// assert(ISet::<A>::empty().len() == 0); /// assert(forall |x: A| !ISet::<A>::empty().contains(x)); /// ``` /// Axioms around the empty set are: <br> /// * [`lemma_iset_empty_finite`] /// * [`lemma_iset_empty_len`] <br> /// * [`lemma_iset_empty`] #[rustc_diagnostic_item = "verus::vstd::iset::ISet::empty"] pub closed spec fn empty() -> ISet<A> { ISet { set: |a| false } }
/// ISet whose membership is determined by the given boolean predicate. /// /// Usage Examples: /// ```rust /// let set_a = ISet::new(|x : nat| x < 42); /// let set_b = ISet::<A>::new(|x| some_predicate(x)); /// assert(forall|x| some_predicate(x) <==> set_b.contains(x)); /// ``` pub closed spec fn new(f: spec_fn(A) -> bool) -> ISet<A> { ISet { set: f } }
/// The "full" set, i.e., set containing every element of type `A`. #[rustc_diagnostic_item = "verus::vstd::iset::ISet::full"] pub open spec fn full() -> ISet<A> { ISet::empty().complement() }
/// Predicate indicating if the set contains the given element. #[rustc_diagnostic_item = "verus::vstd::iset::ISet::contains"] pub closed spec fn contains(self, a: A) -> bool { (self.set)(a) }
/// Predicate indicating if the set contains the given element: supports `self has a` syntax. #[verifier::inline] pub open spec fn spec_has(self, a: A) -> bool { self.contains(a) }
/// Returns `true` if the first argument is a subset of the second. #[rustc_diagnostic_item = "verus::vstd::iset::ISet::subset_of"] pub open spec fn subset_of(self, s2: ISet<A>) -> bool { forall|a: A| self.contains(a) ==> s2.contains(a) }
#[verifier::inline] pub open spec fn spec_le(self, s2: ISet<A>) -> bool { self.subset_of(s2) }
/// Returns a new set with the given element inserted. /// If that element is already in the set, then an identical set is returned. #[rustc_diagnostic_item = "verus::vstd::iset::ISet::insert"] pub closed spec fn insert(self, a: A) -> ISet<A> { ISet { set: |a2| if a2 == a { true } else { (self.set)(a2) }, } }
/// Returns a new set with the given element removed. /// If that element is already absent from the set, then an identical set is returned. #[rustc_diagnostic_item = "verus::vstd::iset::ISet::remove"] pub closed spec fn remove(self, a: A) -> ISet<A> { ISet { set: |a2| if a2 == a { false } else { (self.set)(a2) }, } }
/// Union of two sets. pub closed spec fn union(self, s2: ISet<A>) -> ISet<A> { ISet { set: |a| (self.set)(a) || (s2.set)(a) } }
/// `+` operator, synonymous with `union` #[verifier::inline] pub open spec fn spec_add(self, s2: ISet<A>) -> ISet<A> { self.union(s2) }
/// Intersection of two sets. pub closed spec fn intersect(self, s2: ISet<A>) -> ISet<A> { ISet { set: |a| (self.set)(a) && (s2.set)(a) } }
/// `*` operator, synonymous with `intersect` #[verifier::inline] pub open spec fn spec_mul(self, s2: ISet<A>) -> ISet<A> { self.intersect(s2) }
/// ISet difference, i.e., the set of all elements in the first one but not in the second. pub closed spec fn difference(self, s2: ISet<A>) -> ISet<A> { ISet { set: |a| (self.set)(a) && !(s2.set)(a) } }
/// `-` operator, synonymous with `difference` #[verifier::inline] pub open spec fn spec_sub(self, s2: ISet<A>) -> ISet<A> { self.difference(s2) }
/// ISet complement (within the space of all possible elements in `A`). pub closed spec fn complement(self) -> ISet<A> { ISet { set: |a| !(self.set)(a) } }
/// ISet of all elements in the given set which satisfy the predicate `f`. pub open spec fn filter(self, f: spec_fn(A) -> bool) -> ISet<A> { self.intersect(Self::new(f)) }
/// Returns `true` if the set is finite. pub closed spec fn finite(self) -> bool { exists|f: spec_fn(A) -> nat, ub: nat| { &&& #[trigger] trigger_finite(f, ub) &&& inj_on(f, self) &&& forall|a| self.contains(a) ==> f(a) < ub } }
pub open spec fn to_set(self) -> Option<Set<A>> recommends self.finite(), { Set::<A>::new_from_iset(self) }
/// Cardinality of the set. (Only meaningful if a set is finite.) pub closed spec fn len(self) -> nat { self.fold(0, |acc: nat, a| acc + 1) }
/// Chooses an arbitrary element of the set. /// /// This is often useful for proofs by induction. /// /// (Note that, although the result is arbitrary, it is still a _deterministic_ function /// like any other `spec` function.) pub open spec fn choose(self) -> A { choose|a: A| self.contains(a) }
/// Creates a [`Map`] whose domain is the given set. /// The values of the map are given by `f`, a function of the keys. pub uninterp spec fn mk_map<V>(self, f: spec_fn(A) -> V) -> IMap<A, V>;
/// Returns `true` if the sets are disjoint, i.e., if their interesection is /// the empty set. pub open spec fn disjoint(self, s2: Self) -> bool { forall|a: A| self.contains(a) ==> !s2.contains(a) }
/// Returns `true` if this set is congruent to (contains the same elements as) /// a given finite Set. pub open spec fn congruent(self, s2: Set<A>) -> bool { forall|a: A| #![all_triggers] self.contains(a) <==> s2.contains(a) }}
// Closures make triggering finicky but using this to trigger explicitly works well.spec fn trigger_finite<A>(f: spec_fn(A) -> nat, ub: nat) -> bool { true}
spec fn inj_on<A, B>(f: spec_fn(A) -> B, s: ISet<A>) -> bool { forall|a1, a2| #![all_triggers] s.contains(a1) && s.contains(a2) && a1 != a2 ==> f(a1) != f(a2)}
pub mod fold { //! This module defines a fold function for finite sets and proves a number of associated //! lemmas. //! //! The module was ported (with some modifications) from Isabelle/HOL's finite set theory in: //! `HOL/Finite_ISet.thy` //! That file contains the following author list: //! //! //! (* Title: HOL/Finite_ISet.thy //! Author: Tobias Nipkow //! Author: Lawrence C Paulson //! Author: Markus Wenzel //! Author: Jeremy Avigad //! Author: Andrei Popescu //! *) //! //! //! The file is distributed under a 3-clause BSD license as indicated in the file `COPYRIGHT` //! in Isabelle's root directory, which also carries the following copyright notice: //! //! Copyright (c) 1986-2024, //! University of Cambridge, //! Technische Universitaet Muenchen, //! and contributors. use super::*;
broadcast group group_iset_lemmas_early { lemma_iset_empty, lemma_iset_new, lemma_iset_insert_same, lemma_iset_insert_different, lemma_iset_remove_same, lemma_iset_remove_insert, lemma_iset_remove_different, lemma_iset_union, lemma_iset_intersect, lemma_iset_difference, lemma_iset_complement, lemma_iset_ext_equal, lemma_iset_ext_equal_deep, lemma_iset_empty_finite, lemma_iset_insert_finite, lemma_iset_remove_finite, }
pub open spec fn is_fun_commutative<A, B>(f: spec_fn(B, A) -> B) -> bool { forall|a1, a2, b| #[trigger] f(f(b, a2), a1) == f(f(b, a1), a2) }
// This predicate is intended to be used like an inductive predicate, with the corresponding // introduction, elimination and induction rules proved below. #[verifier(opaque)] spec fn fold_graph<A, B>(z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y: B, d: nat) -> bool decreases d, { if s === ISet::empty() { &&& z == y &&& d == 0 } else { exists|yr, a| { &&& #[trigger] trigger_fold_graph(yr, a) &&& d > 0 &&& s.remove(a).finite() &&& s.contains(a) &&& fold_graph(z, f, s.remove(a), yr, sub(d, 1)) &&& y == f(yr, a) } } }
spec fn trigger_fold_graph<A, B>(yr: B, a: A) -> bool { true }
// Introduction rules proof fn lemma_fold_graph_empty_intro<A, B>(z: B, f: spec_fn(B, A) -> B) ensures fold_graph(z, f, ISet::empty(), z, 0), { reveal(fold_graph); }
proof fn lemma_fold_graph_insert_intro<A, B>( z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y: B, d: nat, a: A, ) requires fold_graph(z, f, s, y, d), !s.contains(a), ensures fold_graph(z, f, s.insert(a), f(y, a), d + 1), { broadcast use group_iset_lemmas_early;
reveal(fold_graph); let _ = trigger_fold_graph(y, a); assert(s == s.insert(a).remove(a)); }
// Elimination rules proof fn lemma_fold_graph_empty_elim<A, B>(z: B, f: spec_fn(B, A) -> B, y: B, d: nat) requires fold_graph(z, f, ISet::empty(), y, d), ensures z == y, d == 0, { reveal(fold_graph); }
proof fn lemma_fold_graph_insert_elim<A, B>( z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y: B, d: nat, a: A, ) requires is_fun_commutative(f), fold_graph(z, f, s.insert(a), y, d), !s.contains(a), ensures d > 0, exists|yp| y == f(yp, a) && #[trigger] fold_graph(z, f, s, yp, sub(d, 1)), { reveal(fold_graph); lemma_fold_graph_insert_elim_aux(z, f, s.insert(a), y, d, a); assert(s.insert(a).remove(a) =~= s); let yp = choose|yp| y == f(yp, a) && #[trigger] fold_graph(z, f, s, yp, sub(d, 1)); }
proof fn lemma_fold_graph_insert_elim_aux<A, B>( z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y: B, d: nat, a: A, ) requires is_fun_commutative(f), fold_graph(z, f, s, y, d), s.contains(a), ensures exists|yp| y == f(yp, a) && #[trigger] fold_graph(z, f, s.remove(a), yp, sub(d, 1)), decreases d, { broadcast use group_iset_lemmas_early;
reveal(fold_graph); let (yr, aa): (B, A) = choose|yr, aa| #![all_triggers] { &&& trigger_fold_graph(yr, a) &&& d > 0 &&& s.remove(aa).finite() &&& s.contains(aa) &&& fold_graph(z, f, s.remove(aa), yr, sub(d, 1)) &&& y == f(yr, aa) }; assert(trigger_fold_graph(yr, a)); if s.remove(aa) === ISet::empty() { } else { if a == aa { } else { lemma_fold_graph_insert_elim_aux(z, f, s.remove(aa), yr, sub(d, 1), a); let yrp = choose|yrp| yr == f(yrp, a) && #[trigger] fold_graph( z, f, s.remove(aa).remove(a), yrp, sub(d, 2), ); assert(fold_graph(z, f, s.remove(aa).insert(aa).remove(a), f(yrp, aa), sub(d, 1))) by { assert(s.remove(aa).remove(a) == s.remove(aa).insert(aa).remove(a).remove(aa)); assert(trigger_fold_graph(yrp, aa)); }; } } }
// Induction rule proof fn lemma_fold_graph_induct<A, B>( z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y: B, d: nat, pred: spec_fn(ISet<A>, B, nat) -> bool, ) requires is_fun_commutative(f), fold_graph(z, f, s, y, d), pred(ISet::empty(), z, 0), forall|a, s, y, d| pred(s, y, d) && !s.contains(a) && #[trigger] fold_graph(z, f, s, y, d) ==> pred( #[trigger] s.insert(a), f(y, a), d + 1, ), ensures pred(s, y, d), decreases d, { broadcast use group_iset_lemmas_early;
reveal(fold_graph); if s === ISet::empty() { lemma_fold_graph_empty_elim(z, f, y, d); } else { let a = s.choose(); lemma_fold_graph_insert_elim(z, f, s.remove(a), y, d, a); let yp = choose|yp| y == f(yp, a) && #[trigger] fold_graph(z, f, s.remove(a), yp, sub(d, 1)); lemma_fold_graph_induct(z, f, s.remove(a), yp, sub(d, 1), pred); } }
impl<A> ISet<A> { /// Folds the set, applying `f` to perform the fold. The next element for the fold is chosen by /// the choose operator. /// /// Given a set `s = {x0, x1, x2, ..., xn}`, applying this function `s.fold(init, f)` /// returns `f(...f(f(init, x0), x1), ..., xn)`. pub closed spec fn fold<B>(self, z: B, f: spec_fn(B, A) -> B) -> B recommends self.finite(), is_fun_commutative(f), { let (y, d): (B, nat) = choose|y, d| fold_graph(z, f, self, y, d); y } }
proof fn lemma_fold_graph_finite<A, B>(z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y: B, d: nat) requires is_fun_commutative(f), fold_graph(z, f, s, y, d), ensures s.finite(), { broadcast use group_iset_lemmas_early;
let pred = |s: ISet<A>, y, d| s.finite(); lemma_fold_graph_induct(z, f, s, y, d, pred); }
proof fn lemma_fold_graph_deterministic<A, B>( z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y1: B, y2: B, d1: nat, d2: nat, ) requires is_fun_commutative(f), fold_graph(z, f, s, y1, d1), fold_graph(z, f, s, y2, d2), ensures y1 == y2, d1 == d2, { let pred = |s: ISet<A>, y1: B, d1: nat| forall|y2, d2| fold_graph(z, f, s, y2, d2) ==> y1 == y2 && d2 == d1; // Base case assert(pred(ISet::empty(), z, 0)) by { assert forall|y2, d2| fold_graph(z, f, ISet::empty(), y2, d2) implies z == y2 && d2 == 0 by { lemma_fold_graph_empty_elim(z, f, y2, d2); }; }; // Step case assert forall|a, s, y1, d1| pred(s, y1, d1) && !s.contains(a) && #[trigger] fold_graph( z, f, s, y1, d1, ) implies pred(#[trigger] s.insert(a), f(y1, a), d1 + 1) by { assert forall|y2, d2| fold_graph(z, f, s.insert(a), y2, d2) implies f(y1, a) == y2 && d2 == d1 + 1 by { lemma_fold_graph_insert_elim(z, f, s, y2, d2, a); }; }; lemma_fold_graph_induct(z, f, s, y2, d2, pred); }
proof fn lemma_fold_is_fold_graph<A, B>(z: B, f: spec_fn(B, A) -> B, s: ISet<A>, y: B, d: nat) requires is_fun_commutative(f), fold_graph(z, f, s, y, d), ensures s.fold(z, f) == y, { lemma_fold_graph_finite(z, f, s, y, d); if s.fold(z, f) != y { let (y2, d2) = choose|y2, d2| fold_graph(z, f, s, y2, d2) && y2 != y; lemma_fold_graph_deterministic(z, f, s, y2, y, d2, d); assert(false); } }
// At this point set cardinality is not yet defined, so we can't easily give a decreasing // measure to prove the subsequent lemma `lemma_fold_graph_exists`. Instead, we first prove // this lemma, for which we use the upper bound of a finiteness witness as the decreasing // measure. pub proof fn lemma_finite_set_induct<A>(s: ISet<A>, pred: spec_fn(ISet<A>) -> bool) requires s.finite(), pred(ISet::empty()), forall|s, a| pred(s) && s.finite() && !s.contains(a) ==> #[trigger] pred(s.insert(a)), ensures pred(s), { let (f, ub) = choose|f: spec_fn(A) -> nat, ub: nat| #[trigger] trigger_finite(f, ub) && inj_on(f, s) && (forall|a| s.contains(a) ==> f(a) < ub); lemma_finite_set_induct_aux(s, f, ub, pred); }
proof fn lemma_finite_set_induct_aux<A>( s: ISet<A>, f: spec_fn(A) -> nat, ub: nat, pred: spec_fn(ISet<A>) -> bool, ) requires inj_on(f, s), s.finite(), forall|a| s.contains(a) ==> f(a) < ub, pred(ISet::empty()), forall|s, a| pred(s) && s.finite() && !s.contains(a) ==> #[trigger] pred(s.insert(a)), ensures pred(s), decreases ub, { broadcast use group_iset_lemmas_early;
if s =~= ISet::empty() { } else { let a = s.choose(); // If `f` maps something to `ub - 1`, remap it to `f(a)` so we can decrease ub let fp = |aa| if f(aa) == ub - 1 { f(a) } else { f(aa) }; lemma_finite_set_induct_aux(s.remove(a), fp, sub(ub, 1), pred); } }
proof fn lemma_fold_graph_exists<A, B>(z: B, f: spec_fn(B, A) -> B, s: ISet<A>) requires s.finite(), is_fun_commutative(f), ensures exists|y, d| fold_graph(z, f, s, y, d), { let pred = |s| exists|y, d| fold_graph(z, f, s, y, d); // Base case assert(fold_graph(z, f, ISet::empty(), z, 0)) by { lemma_fold_graph_empty_intro(z, f); }; // Step case assert forall|s, a| pred(s) && s.finite() && !s.contains(a) implies #[trigger] pred( s.insert(a), ) by { let (y, d): (B, nat) = choose|y, d| fold_graph(z, f, s, y, d); lemma_fold_graph_insert_intro(z, f, s, y, d, a); }; lemma_finite_set_induct(s, pred); }
pub broadcast proof fn lemma_fold_insert<A, B>(s: ISet<A>, z: B, f: spec_fn(B, A) -> B, a: A) requires s.finite(), !s.contains(a), is_fun_commutative(f), ensures #[trigger] s.insert(a).fold(z, f) == f(s.fold(z, f), a), { lemma_fold_graph_exists(z, f, s); let (y, d): (B, nat) = choose|y, d| fold_graph(z, f, s, y, d); lemma_fold_graph_insert_intro(z, f, s, s.fold(z, f), d, a); lemma_fold_is_fold_graph(z, f, s.insert(a), f(s.fold(z, f), a), d + 1); }
pub broadcast proof fn lemma_fold_empty<A, B>(z: B, f: spec_fn(B, A) -> B) ensures #[trigger] ISet::empty().fold(z, f) == z, { let (y, d): (B, nat) = choose|y, d| fold_graph(z, f, ISet::empty(), y, d); lemma_fold_graph_empty_intro(z, f); lemma_fold_graph_empty_elim(z, f, y, d); }
}
// Lemmas/// The empty set contains no elementspub broadcast proof fn lemma_iset_empty<A>(a: A) ensures !(#[trigger] ISet::empty().contains(a)),{}
/// A call to `ISet::new` with the predicate `f` contains `a` if and only if `f(a)` is true.pub broadcast proof fn lemma_iset_new<A>(f: spec_fn(A) -> bool, a: A) ensures #[trigger] ISet::new(f).contains(a) == f(a),{}
/// The result of inserting element `a` into set `s` must contains `a`.pub broadcast proof fn lemma_iset_insert_same<A>(s: ISet<A>, a: A) ensures #[trigger] s.insert(a).contains(a),{}
/// If `a1` does not equal `a2`, then the result of inserting element `a2` into set `s`/// must contain `a1` if and only if the set contained `a1` before the insertion of `a2`.pub broadcast proof fn lemma_iset_insert_different<A>(s: ISet<A>, a1: A, a2: A) requires a1 != a2, ensures #[trigger] s.insert(a2).contains(a1) == s.contains(a1),{}
/// The result of removing element `a` from set `s` must not contain `a`.pub broadcast proof fn lemma_iset_remove_same<A>(s: ISet<A>, a: A) ensures !(#[trigger] s.remove(a).contains(a)),{}
/// Removing an element `a` from a set `s` and then inserting `a` back into the set`/// is equivalent to the original set `s`.pub broadcast proof fn lemma_iset_remove_insert<A>(s: ISet<A>, a: A) requires s.contains(a), ensures (#[trigger] s.remove(a)).insert(a) == s,{ assert forall|aa| #![all_triggers] s.remove(a).insert(a).contains(aa) implies s.contains( aa, ) by { if a == aa { } else { lemma_iset_remove_different(s, aa, a); lemma_iset_insert_different(s.remove(a), aa, a); } }; assert forall|aa| #![all_triggers] s.contains(aa) implies s.remove(a).insert(a).contains( aa, ) by { if a == aa { lemma_iset_insert_same(s.remove(a), a); } else { lemma_iset_remove_different(s, aa, a); lemma_iset_insert_different(s.remove(a), aa, a); } }; lemma_iset_ext_equal(s.remove(a).insert(a), s);}
/// If `a1` does not equal `a2`, then the result of removing element `a2` from set `s`/// must contain `a1` if and only if the set contained `a1` before the removal of `a2`.pub broadcast proof fn lemma_iset_remove_different<A>(s: ISet<A>, a1: A, a2: A) requires a1 != a2, ensures #[trigger] s.remove(a2).contains(a1) == s.contains(a1),{}
/// The union of sets `s1` and `s2` contains element `a` if and only if/// `s1` contains `a` and/or `s2` contains `a`.pub broadcast proof fn lemma_iset_union<A>(s1: ISet<A>, s2: ISet<A>, a: A) ensures #[trigger] s1.union(s2).contains(a) == (s1.contains(a) || s2.contains(a)),{}
/// The intersection of sets `s1` and `s2` contains element `a` if and only if/// both `s1` and `s2` contain `a`.pub broadcast proof fn lemma_iset_intersect<A>(s1: ISet<A>, s2: ISet<A>, a: A) ensures #[trigger] s1.intersect(s2).contains(a) == (s1.contains(a) && s2.contains(a)),{}
/// The set difference between `s1` and `s2` contains element `a` if and only if/// `s1` contains `a` and `s2` does not contain `a`.pub broadcast proof fn lemma_iset_difference<A>(s1: ISet<A>, s2: ISet<A>, a: A) ensures #[trigger] s1.difference(s2).contains(a) == (s1.contains(a) && !s2.contains(a)),{}
/// The complement of set `s` contains element `a` if and only if `s` does not contain `a`.pub broadcast proof fn lemma_iset_complement<A>(s: ISet<A>, a: A) ensures #[trigger] s.complement().contains(a) == !s.contains(a),{}
/// ISets `s1` and `s2` are equal if and only if they contain all of the same elements.pub broadcast proof fn lemma_iset_ext_equal<A>(s1: ISet<A>, s2: ISet<A>) ensures #[trigger] (s1 =~= s2) <==> (forall|a: A| s1.contains(a) == s2.contains(a)),{ if s1 =~= s2 { assert(forall|a: A| s1.contains(a) == s2.contains(a)); } if forall|a: A| s1.contains(a) == s2.contains(a) { if !(forall|a: A| #[trigger] (s1.set)(a) <==> (s2.set)(a)) { assert(exists|a: A| #[trigger] (s1.set)(a) != (s2.set)(a)); let a = choose|a: A| #[trigger] (s1.set)(a) != (s2.set)(a); assert(s1.contains(a)); assert(false); } assert(s1 =~= s2); }}
pub broadcast proof fn lemma_iset_ext_equal_deep<A>(s1: ISet<A>, s2: ISet<A>) ensures #[trigger] (s1 =~~= s2) <==> s1 =~= s2,{}
pub broadcast axiom fn lemma_iset_mk_map_domain<K, V>(s: ISet<K>, f: spec_fn(K) -> V) ensures #[trigger] s.mk_map(f).dom() == s,;
pub broadcast axiom fn lemma_iset_mk_map_index<K, V>(s: ISet<K>, f: spec_fn(K) -> V, key: K) requires s.contains(key), ensures #[trigger] s.mk_map(f)[key] == f(key),;
// Trusted axioms about finite/// The empty set is finite.pub broadcast proof fn lemma_iset_empty_finite<A>() ensures #[trigger] ISet::<A>::empty().finite(),{ let f = |a: A| 0; let ub = 0; let _ = trigger_finite(f, ub);}
/// The result of inserting an element `a` into a finite set `s` is also finite.pub broadcast proof fn lemma_iset_insert_finite<A>(s: ISet<A>, a: A) requires s.finite(), ensures #[trigger] s.insert(a).finite(),{ let (f, ub) = choose|f: spec_fn(A) -> nat, ub: nat| #[trigger] trigger_finite(f, ub) && inj_on(f, s) && (forall|a| s.contains(a) ==> f(a) < ub); let f2 = |a2: A| if a2 == a { ub } else { f(a2) }; let ub2 = ub + 1; let _ = trigger_finite(f2, ub2); assert forall|a1, a2| #![all_triggers] s.insert(a).contains(a1) && s.insert(a).contains(a2) && a1 != a2 implies f2(a1) != f2( a2, ) by { if a != a1 { assert(s.contains(a1)); } if a != a2 { assert(s.contains(a2)); } }; assert forall|a2| s.insert(a).contains(a2) implies #[trigger] f2(a2) < ub2 by { if a == a2 { } else { assert(s.contains(a2)); } };}
/// The result of removing an element `a` from a finite set `s` is also finite.pub broadcast proof fn lemma_iset_remove_finite<A>(s: ISet<A>, a: A) requires s.finite(), ensures #[trigger] s.remove(a).finite(),{ let (f, ub) = choose|f: spec_fn(A) -> nat, ub: nat| #[trigger] trigger_finite(f, ub) && inj_on(f, s) && (forall|a| s.contains(a) ==> f(a) < ub); assert forall|a1, a2| #![all_triggers] s.remove(a).contains(a1) && s.remove(a).contains(a2) && a1 != a2 implies f(a1) != f(a2) by { if a != a1 { assert(s.contains(a1)); } if a != a2 { assert(s.contains(a2)); } }; assert(inj_on(f, s.remove(a))); assert forall|a2| s.remove(a).contains(a2) implies #[trigger] f(a2) < ub by { if a == a2 { } else { assert(s.contains(a2)); } };}
/// The union of two finite sets is finite.pub broadcast proof fn lemma_iset_union_finite<A>(s1: ISet<A>, s2: ISet<A>) requires s1.finite(), s2.finite(), ensures #[trigger] s1.union(s2).finite(),{ let (f1, ub1) = choose|f: spec_fn(A) -> nat, ub: nat| #[trigger] trigger_finite(f, ub) && inj_on(f, s1) && (forall|a| s1.contains(a) ==> f(a) < ub); let (f2, ub2) = choose|f: spec_fn(A) -> nat, ub: nat| #[trigger] trigger_finite(f, ub) && inj_on(f, s2) && (forall|a| s2.contains(a) ==> f(a) < ub); let f3 = |a| if s1.contains(a) { f1(a) } else { ub1 + f2(a) }; let ub3 = ub1 + ub2; assert(trigger_finite(f3, ub3)); assert(forall|a| #![all_triggers] s1.union(s2).contains(a) ==> s1.contains(a) || s2.contains(a));}
/// The intersection of two finite sets is finite.pub broadcast proof fn lemma_iset_intersect_finite<A>(s1: ISet<A>, s2: ISet<A>) requires s1.finite() || s2.finite(), ensures #[trigger] s1.intersect(s2).finite(),{ assert(forall|a| #![all_triggers] s1.intersect(s2).contains(a) ==> s1.contains(a) && s2.contains(a));}
/// The set difference between two finite sets is finite.pub broadcast proof fn lemma_iset_difference_finite<A>(s1: ISet<A>, s2: ISet<A>) requires s1.finite(), ensures #[trigger] s1.difference(s2).finite(),{ assert(forall|a| #![all_triggers] s1.difference(s2).contains(a) ==> s1.contains(a) && !s2.contains(a));}
/// An infinite set `s` contains the element `s.choose()`.pub broadcast proof fn lemma_iset_choose_infinite<A>(s: ISet<A>) requires !s.finite(), ensures #[trigger] s.contains(s.choose()),{ let f = |a: A| 0; let ub = 0; let _ = trigger_finite(f, ub);}
// Trusted axioms about len// Note: we could add more axioms about len, but they would be incomplete.// The following, with lemma_iset_ext_equal, are enough to build libraries about len./// The empty set has length 0.pub broadcast proof fn lemma_iset_empty_len<A>() ensures #[trigger] ISet::<A>::empty().len() == 0,{ fold::lemma_fold_empty(0, |b: nat, a: A| b + 1);}
/// The result of inserting an element `a` into a finite set `s` has length/// `s.len() + 1` if `a` is not already in `s` and length `s.len()` otherwise.pub broadcast proof fn lemma_iset_insert_len<A>(s: ISet<A>, a: A) requires s.finite(), ensures #[trigger] s.insert(a).len() == s.len() + (if s.contains(a) { 0int } else { 1 }),{ if s.contains(a) { assert(s =~= s.insert(a)); } else { fold::lemma_fold_insert(s, 0, |b: nat, a: A| b + 1, a); }}
/// The result of removing an element `a` from a finite set `s` has length/// `s.len() - 1` if `a` is in `s` and length `s.len()` otherwise.pub broadcast proof fn lemma_iset_remove_len<A>(s: ISet<A>, a: A) requires s.finite(), ensures s.len() == #[trigger] s.remove(a).len() + (if s.contains(a) { 1int } else { 0 }),{ lemma_iset_remove_finite(s, a); lemma_iset_insert_len(s.remove(a), a); if s.contains(a) { assert(s =~= s.remove(a).insert(a)); } else { assert(s =~= s.remove(a)); }}
/// If a finite set `s` contains any element, it has length greater than 0.pub broadcast proof fn lemma_iset_contains_len<A>(s: ISet<A>, a: A) requires s.finite(), #[trigger] s.contains(a), ensures #[trigger] s.len() != 0,{ let a = s.choose(); assert(s.remove(a).insert(a) =~= s); lemma_iset_remove_finite(s, a); lemma_iset_insert_finite(s.remove(a), a); lemma_iset_insert_len(s.remove(a), a);}
/// A finite set `s` contains the element `s.choose()` if it has length greater than 0.pub broadcast proof fn lemma_iset_choose_len<A>(s: ISet<A>) requires s.finite(), #[trigger] s.len() != 0, ensures #[trigger] s.contains(s.choose()),{ // Separate statements to work around https://github.com/verus-lang/verusfmt/issues/86 broadcast use lemma_iset_contains_len; broadcast use lemma_iset_empty_len; broadcast use lemma_iset_ext_equal; broadcast use lemma_iset_insert_finite;
let pred = |s: ISet<A>| s.finite() ==> s.len() == 0 <==> s =~= ISet::empty(); fold::lemma_finite_set_induct(s, pred);}
pub proof fn lemma_iset_finite_if_subset_of_seq<A>(i: ISet<A>, s: Seq<A>) requires forall|a| i.contains(a) ==> s.contains(a), ensures i.finite(),{ let f = |a: A| (s.index_of(a) as nat); let ub = s.len(); assert(inj_on(f, i)) by { assert forall|a1, a2| #![all_triggers] i.contains(a1) && i.contains(a2) && a1 != a2 implies f(a1) != f(a2) by { assert(s.contains(a1)); assert(s.contains(a2)); assert(0 <= f(a1) < s.len() && s[f(a1) as int] == a1); assert(0 <= f(a2) < s.len() && s[f(a2) as int] == a2); } } assert forall|a| i.contains(a) implies f(a) < ub by { assert(s.contains(a)); assert(0 <= f(a) < s.len() && s[f(a) as int] == a); } assert(trigger_finite(f, ub));}
pub broadcast group group_iset_lemmas { lemma_iset_empty, lemma_iset_new, lemma_iset_insert_same, lemma_iset_insert_different, lemma_iset_remove_same, lemma_iset_remove_insert, lemma_iset_remove_different, lemma_iset_union, lemma_iset_intersect, lemma_iset_difference, lemma_iset_complement, lemma_iset_ext_equal, lemma_iset_ext_equal_deep, lemma_iset_mk_map_domain, lemma_iset_mk_map_index, lemma_iset_empty_finite, lemma_iset_insert_finite, lemma_iset_remove_finite, lemma_iset_union_finite, lemma_iset_intersect_finite, lemma_iset_difference_finite, lemma_iset_choose_infinite, lemma_iset_empty_len, lemma_iset_insert_len, lemma_iset_remove_len, lemma_iset_contains_len, lemma_iset_choose_len,}
// Macros#[doc(hidden)]#[macro_export]macro_rules! iset_internal { [$($elem:expr),* $(,)?] => { $crate::vstd::iset::ISet::empty() $(.insert($elem))* };}
#[macro_export]macro_rules! iset { [$($tail:tt)*] => { $crate::vstd::prelude::verus_proof_macro_exprs!($crate::vstd::iset::iset_internal!($($tail)*)) };}
pub use iset_internal;pub use iset;
} // verus!