[−][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.
To minimize disruption caused by this two-level wrapping scheme and provide a
degree of compositionality, every LatticeElt
also implements LatticeDef
by
delegation to the LatticeDef
it's parameterized over.
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.0, BitSet::from_bytes(&[0b11111111])); assert_eq!(w.value["b"].value.0, BitSet::from_bytes(&[0b10101010]));
Name
Wikipedia:
A pergola is an outdoor garden feature forming a shaded walkway, passageway, or sitting area of vertical posts or pillars that usually support cross-beams and a sturdy open lattice, often upon which woody vines are trained.
Structs
ArcOrdMapWithIntersection | 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 |
ArcOrdMapWithUnion | 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. |
ArcOrdSetWithIntersection | This is the same semantics as the |
ArcOrdSetWithUnion | This is the same semantics as the |
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. |
BitSetWrapper | Wrap a BitSet in a newtype so we can implement serde traits on it (weirdly by delegating to its inner BitVec). |
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 |
RcOrdMapWithIntersection | 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 |
RcOrdMapWithUnion | 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. |
RcOrdSetWithIntersection | This is the same semantics as the |
RcOrdSetWithUnion | This is the same semantics as the |
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
DefTraits |
|
EltDef | Trait to extract the Def back out of a given LatticeElt. |
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 |
ValTraits |
|