[−][src]Crate pergola
This is a small crate that provides a generic unital-join-semilattice type (hereafter: "lattice") along with a few common instances.
Lattices are defined in two separate pieces: a definition trait LatticeDef
that provides the type-and-functions for a given lattice and a user interface
struct LatticeElt
that's parameterized by a LatticeDef
and provides
convenient methods to work with (including impls of standard Rust operator
traits).
This unusual split exists because many types have multiple equally viable lattices you can build on them (eg. u32-with-min or u32-with-max) and we want to avoid both coupling any given lattice definition to the type or accidentally inheriting an impl for any of the type's "standard semantics" as the lattice semantics, eg. we don't want to inherit u32's standard partial order as any lattice's partial order, unless explicitly building such a lattice.
Examples
Simple u32-with-max lattice
use pergola::{MaxDef,LatticeElt}; type Def = MaxDef<u32>; // lattice def for "u32 with max for join" type Elt = LatticeElt<Def>; // element struct, implementing std traits let v = Elt::new_from(1); let u = Elt::new_from(2); let w = v + u; // calls join(), which calls max() assert!(v < u); assert!(v < w);
Trickier union-map-of-union-bitsets lattice
use pergola::{BTreeMapWithUnion,BitSetWithUnion,LatticeElt}; use bit_set::BitSet; use std::collections::BTreeMap; type Def = BTreeMapWithUnion<String,BitSetWithUnion>; type Elt = LatticeElt<Def>; let bs_a1 = BitSet::from_bytes(&[0b11110000]); let bs_a2 = BitSet::from_bytes(&[0b00001111]); let bs_b = BitSet::from_bytes(&[0b10101010]); let v = Elt::new_from([(String::from("a"),bs_a1.into()), (String::from("b"),bs_b.into())].iter().cloned().collect()); let u = Elt::new_from([(String::from("a"),bs_a2.into())].iter().cloned().collect()); let w = &v + &u; assert!(!(v < u)); // bs_a1 is not a subset of bs_a2, // so v["a"] is unordered wrt. u["a"]. assert!(v < w); // However, w is a join and join unions // the values at common keys, so v["a"] < w["a"]. assert!(u < w); // And likewise the other input to the join. assert_eq!(w.value["a"].value, BitSet::from_bytes(&[0b11111111])); assert_eq!(w.value["b"].value, BitSet::from_bytes(&[0b10101010]));
Structs
BTreeMapWithIntersection | Similar to other intersection-based lattices in this crate, this lattice is
a map that stores inner lattices and joins using intersection. Maps are
represented as |
BTreeMapWithUnion | This is a lattice for maps that contain other lattices as values. The join operator takes the union of (key, value) pairs for keys present in only one map -- equivalent to an elementwise join-with-unit -- and the elementwise join of values for keys that exist in both maps. |
BTreeSetWithIntersection | This is the same semantics as the |
BTreeSetWithUnion | This is the same semantics as the |
BitSetWithIntersection | This lattice is a standard bitset-with-intersection. |
BitSetWithUnion | This lattice is a standard bitset-with-union. |
LatticeElt | Write code that uses lattices over this type, and it will delegate
to the functions of the parameter |
MaxDef | This lattice definition recycles the |
MaxNum | This lattice definition recycles the |
MinNum | This is like |
MinOpt | This lattice is similar to MaxDef but inverts the order, with the minimal
value according to |
Tuple2 | Cartesian product lattices or 2, 3, 4, 5 inner lattices. Join joins elements pairwise, order is the product order (not lexicographical order) i.e. where (a, b) <= (c, d) iff a <= c and b <= d. |
Tuple3 | |
Tuple4 | |
Tuple5 |
Traits
LatticeDef | Implement this trait on a (typically vacuous) type to define a specific lattice as a type-with-some-choice-of-operators. |
MaxUnitDefault | A marker trait here to pick out types where |
MaxUnitMinValue | A marker type for other types that use the |