#[allow(unused_imports)] use super::map::*; #[allow(unused_imports)] use super::pervasive::*; #[allow(unused_imports)] use super::prelude::*; verus! { /// `ISet` is a set type for specifications. /// /// An object `set: ISet` 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 { set: spec_fn(A) -> bool, } impl ISet { /// The "empty" set. /// /// Usage Example:
/// ```rust /// let empty_set = ISet::
::empty(); /// /// assert(empty_set.is_empty()); /// assert(empty_set.complement() =~= ISet::::full()); /// assert(ISet::::empty().finite()); /// assert(ISet::::empty().len() == 0); /// assert(forall |x: A| !ISet::::empty().contains(x)); /// ``` /// Axioms around the empty set are:
/// * [`lemma_iset_empty_finite`] /// * [`lemma_iset_empty_len`]
/// * [`lemma_iset_empty`] #[rustc_diagnostic_item = "verus::vstd::iset::ISet::empty"] pub closed spec fn empty() -> ISet
{ 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::::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 { 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 { 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) -> bool { forall|a: A| self.contains(a) ==> s2.contains(a) } #[verifier::inline] pub open spec fn spec_le(self, s2: ISet) -> 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 { 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 { ISet { set: |a2| if a2 == a { false } else { (self.set)(a2) }, } } /// Union of two sets. pub closed spec fn union(self, s2: ISet) -> ISet { ISet { set: |a| (self.set)(a) || (s2.set)(a) } } /// `+` operator, synonymous with `union` #[verifier::inline] pub open spec fn spec_add(self, s2: ISet) -> ISet { self.union(s2) } /// Intersection of two sets. pub closed spec fn intersect(self, s2: ISet) -> ISet { ISet { set: |a| (self.set)(a) && (s2.set)(a) } } /// `*` operator, synonymous with `intersect` #[verifier::inline] pub open spec fn spec_mul(self, s2: ISet) -> ISet { 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) -> ISet { ISet { set: |a| (self.set)(a) && !(s2.set)(a) } } /// `-` operator, synonymous with `difference` #[verifier::inline] pub open spec fn spec_sub(self, s2: ISet) -> ISet { self.difference(s2) } /// ISet complement (within the space of all possible elements in `A`). pub closed spec fn complement(self) -> ISet { 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 { 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> recommends self.finite(), { Set::::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(self, f: spec_fn(A) -> V) -> IMap; /// 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) -> 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(f: spec_fn(A) -> nat, ub: nat) -> bool { true } spec fn inj_on(f: spec_fn(A) -> B, s: ISet) -> 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(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(z: B, f: spec_fn(B, A) -> B, s: ISet, 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(yr: B, a: A) -> bool { true } // Introduction rules proof fn lemma_fold_graph_empty_intro(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( z: B, f: spec_fn(B, A) -> B, s: ISet, 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(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( z: B, f: spec_fn(B, A) -> B, s: ISet, 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( z: B, f: spec_fn(B, A) -> B, s: ISet, 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( z: B, f: spec_fn(B, A) -> B, s: ISet, y: B, d: nat, pred: spec_fn(ISet, 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 ISet { /// 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(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(z: B, f: spec_fn(B, A) -> B, s: ISet, 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, y, d| s.finite(); lemma_fold_graph_induct(z, f, s, y, d, pred); } proof fn lemma_fold_graph_deterministic( z: B, f: spec_fn(B, A) -> B, s: ISet, 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, 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(z: B, f: spec_fn(B, A) -> B, s: ISet, 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(s: ISet, pred: spec_fn(ISet) -> 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( s: ISet, f: spec_fn(A) -> nat, ub: nat, pred: spec_fn(ISet) -> 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(z: B, f: spec_fn(B, A) -> B, s: ISet) 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(s: ISet, 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(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 elements pub broadcast proof fn lemma_iset_empty(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(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(s: ISet, 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(s: ISet, 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(s: ISet, 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(s: ISet, 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(s: ISet, 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(s1: ISet, s2: ISet, 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(s1: ISet, s2: ISet, 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(s1: ISet, s2: ISet, 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(s: ISet, 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(s1: ISet, s2: ISet) 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(s1: ISet, s2: ISet) ensures #[trigger] (s1 =~~= s2) <==> s1 =~= s2, { } pub broadcast axiom fn lemma_iset_mk_map_domain(s: ISet, f: spec_fn(K) -> V) ensures #[trigger] s.mk_map(f).dom() == s, ; pub broadcast axiom fn lemma_iset_mk_map_index(s: ISet, 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() ensures #[trigger] ISet::::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(s: ISet, 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(s: ISet, 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(s1: ISet, s2: ISet) 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(s1: ISet, s2: ISet) 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(s1: ISet, s2: ISet) 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(s: ISet) 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() ensures #[trigger] ISet::::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(s: ISet, 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(s: ISet, 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(s: ISet, 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(s: ISet) 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| 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(i: ISet, s: Seq) 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!