1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221
#![warn(missing_docs)]
#![doc = include_str!("../README.md")]
use std::cmp::Ordering::{self, *};
pub use cc_traits;
use sealed::sealed;
/// Module for definiting algebraic structures and properties.
pub mod algebra;
pub mod collections;
mod conflict;
mod dom_pair;
pub mod map_union;
pub mod map_union_with_tombstones;
mod ord;
mod pair;
mod point;
pub mod set_union;
pub mod set_union_with_tombstones;
pub mod test;
pub mod union_find;
mod unit;
mod vec_union;
mod with_bot;
mod with_top;
pub use conflict::Conflict;
pub use dom_pair::DomPair;
pub use ord::{Max, Min};
pub use pair::Pair;
pub use point::Point;
pub use vec_union::VecUnion;
pub use with_bot::WithBot;
pub use with_top::WithTop;
/// Alias trait for lattice types.
#[sealed]
pub trait Lattice: Sized + Merge<Self> + LatticeOrd + NaiveLatticeOrd + IsBot + IsTop {}
#[sealed]
impl<T> Lattice for T where T: Sized + Merge<Self> + LatticeOrd + NaiveLatticeOrd + IsBot + IsTop {}
/// Trait for lattice merge (AKA "join" or "least upper bound").
pub trait Merge<Other> {
/// Merge `other` into the `self` lattice.
///
/// This operation must be associative, commutative, and idempotent.
///
/// Returns `true` if `self` changed, `false` otherwise.
/// Returning `true` implies that the new value for `self` is later in the lattice order than
/// the old value. Returning `false` means that `self` was unchanged and therefore `other` came
/// before `self` (or the two are equal) in the lattice order.
fn merge(&mut self, other: Other) -> bool;
/// Merge `this` and `delta` together, returning the new value.
fn merge_owned(mut this: Self, delta: Other) -> Self
where
Self: Sized,
{
Self::merge(&mut this, delta);
this
}
}
/// Trait for lattice partial order comparison
/// PartialOrd is implemented for many things, this trait can be used to require the type be a lattice.
pub trait LatticeOrd<Rhs = Self>: PartialOrd<Rhs> {}
/// Naive lattice compare, based on the [`Merge::merge`] function.
#[sealed]
pub trait NaiveLatticeOrd<Rhs = Self>
where
Self: Clone + Merge<Rhs> + Sized,
Rhs: Clone + Merge<Self>,
{
/// Naive compare based on the [`Merge::merge`] method. This method can be very inefficient;
/// use [`PartialOrd::partial_cmp`] instead.
///
/// This method should not be overridden.
fn naive_cmp(&self, other: &Rhs) -> Option<Ordering> {
let mut self_a = self.clone();
let other_a = other.clone();
let self_b = self.clone();
let mut other_b = other.clone();
match (self_a.merge(other_a), other_b.merge(self_b)) {
(true, true) => None,
(true, false) => Some(Less),
(false, true) => Some(Greater),
(false, false) => Some(Equal),
}
}
}
#[sealed]
impl<This, Other> NaiveLatticeOrd<Other> for This
where
Self: Clone + Merge<Other>,
Other: Clone + Merge<Self>,
{
}
/// Same as `From` but for lattices.
///
/// This should only be implemented between different representations of the same lattice type.
/// This should recursively convert nested lattice types, but not non-lattice ("scalar") types.
pub trait LatticeFrom<Other> {
/// Convert from the `Other` lattice into `Self`.
fn lattice_from(other: Other) -> Self;
}
/// Trait to check if a lattice instance is bottom (⊥).
pub trait IsBot {
/// Returns if `self` is lattice bottom (⊥).
///
/// Must be consistent with equality, any element equal to bottom is also considered to be bottom.
fn is_bot(&self) -> bool;
}
/// Trait to check if a lattice instance is top (⊤) and therefore cannot change any futher.
pub trait IsTop {
/// Returns if `self` is lattice top (⊤).
///
/// Must be consistent with equality, any element equal to top is also considered to be top.
fn is_top(&self) -> bool;
}
/// Trait to atomize a lattice into individual elements. For example, a [`set_union::SetUnion`]
/// will be broken up into individual singleton elements.
///
/// Formally, breaks up `Self` into an set of lattice points forming a (strong) [antichain](https://en.wikipedia.org/wiki/Antichain).
/// "Strong" in the sense that any pair of lattice points in the antichain should have a greatest
/// lower bound (GLB or "meet") of bottom.
pub trait Atomize: Merge<Self::Atom> {
/// The type of atoms for this lattice.
type Atom: 'static + IsBot;
/// The iter type iterating the antichain atoms.
type AtomIter: 'static + Iterator<Item = Self::Atom>;
/// Atomize self: convert into an iter of atoms.
///
/// The returned iterator should be empty if and only if `self.is_bot()` is true.
/// All atoms in the returned iterator should have `self.is_bot()` be false.
///
/// Returned values must merge to reform a value equal to the original `self`.
fn atomize(self) -> Self::AtomIter;
}
/// Trait for recursively revealing the underlying types within lattice types.
pub trait DeepReveal {
/// The underlying type when revealed.
type Revealed;
/// Reveals the underlying lattice types recursively.
fn deep_reveal(self) -> Self::Revealed;
}
/// Semilattice morphism. Lattice merge must distribute over this unary function.
///
/// Use [`crate::test::check_lattice_morphism`] to spot-test an implementation.
///
/// See the [lattice math doc's lattice morphism section](https://hydro.run/docs/hydroflow/lattices_crate/lattice_math/#lattice-morphism).
pub trait LatticeMorphism<LatIn> {
/// The output lattice type.
type Output;
/// Executes the function.
fn call(&mut self, lat_in: LatIn) -> Self::Output;
}
/// Semilattice bimorphism. Lattice merge must distribute over this binary function, in both arguments.
///
/// Use [`crate::test::check_lattice_bimorphism`] to spot-test an implementation.
///
/// See the [lattice math doc's lattice bimorphism section](https://hydro.run/docs/hydroflow/lattices_crate/lattice_math/#lattice-bimorphism).
pub trait LatticeBimorphism<LatA, LatB> {
/// The output lattice type.
type Output;
/// Executes the function.
fn call(&mut self, lat_a: LatA, lat_b: LatB) -> Self::Output;
}
/// Converts a closure to a morphism. Does not check for correctness.
pub fn closure_to_morphism<LatIn, LatOut, F>(
func: F,
) -> impl LatticeMorphism<LatIn, Output = LatOut>
where
F: FnMut(LatIn) -> LatOut,
{
struct FnMorphism<F>(F);
impl<F, LatIn, LatOut> LatticeMorphism<LatIn> for FnMorphism<F>
where
F: FnMut(LatIn) -> LatOut,
{
type Output = LatOut;
fn call(&mut self, lat_in: LatIn) -> Self::Output {
(self.0)(lat_in)
}
}
FnMorphism(func)
}
/// Converts a closure to a bimorphism. Does not check for correctness.
pub fn closure_to_bimorphism<LatA, LatB, LatOut, F>(
func: F,
) -> impl LatticeBimorphism<LatA, LatB, Output = LatOut>
where
F: FnMut(LatA, LatB) -> LatOut,
{
struct FnBimorphism<F>(F);
impl<F, LatA, LatB, LatOut> LatticeBimorphism<LatA, LatB> for FnBimorphism<F>
where
F: FnMut(LatA, LatB) -> LatOut,
{
type Output = LatOut;
fn call(&mut self, lat_a: LatA, lat_b: LatB) -> Self::Output {
(self.0)(lat_a, lat_b)
}
}
FnBimorphism(func)
}