#[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!