[−][src]Crate pergola
This is a small crate that provides a generic unitaljoinsemilattice type (hereafter: "lattice") along with a few common instances.
Lattices are defined in two separate pieces: a definition trait LatticeDef
that provides the typeandfunctions 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
withmin
or u32
withmax
) 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 u32withmax 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);
Composite tuple lattice
use pergola::{MaxDef,Tuple3,LatticeElt}; type NumDef = MaxDef<u32>; type NumElt = LatticeElt<NumDef>; type TupDef = Tuple3<NumDef,NumDef,NumDef>; type TupElt = LatticeElt<TupDef>; let n1: NumElt = (1).into(); let n2: NumElt = (2).into(); let n3: NumElt = (3).into(); let tup: TupElt = (n1, n2, n3).into(); assert!(tup.value.0 < tup.value.1); assert!((tup.value.0 + tup.value.1) == tup.value.1); let n1ref: &NumElt = &tup.value.0; let n2ref: &NumElt = &tup.value.1; assert!(n1ref < n2ref);
Trickier unionmapofunionbitsets 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 crossbeams and a sturdy open lattice, often upon which woody vines are trained.
Structs
ArcOrdMapWithIntersection  Similar to other intersectionbased 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 joinwithunit  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 intersectionbased 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 joinwithunit  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 
BitSetWithUnion  This lattice is a standard 
BitSetWrapper  Wrap a 
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 
RcOrdMapWithIntersection  Similar to other intersectionbased 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 joinwithunit  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 lattice for 2 inner lattices, joining elements pairwise
and with the product partial order (not lexicographical order) where 
Tuple3  Cartesian product lattice for 3 inner lattices, joining elements pairwise
and with the product partial order (not lexicographical order) where

Tuple4  Cartesian product lattice for 4 inner lattices, joining elements pairwise
and with the product partial order (not lexicographical order) where

Tuple5  Cartesian product lattice for 5 inner lattices, joining elements pairwise
and with the product partial order (not lexicographical order) where

Traits
DefTraits 

LatticeDef  Implement this trait on a (typically vacuous) type to define a specific lattice as a typewithsomechoiceofoperators. 
MaxUnitDefault  A marker trait here to pick out types where 
MaxUnitMinValue  A marker type for other types that use the 
ValTraits 
