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);

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 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 Option<BTreeMap> and the unit is again a putative “maximum” map-with-all-possible-keys (represented by None).

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 BitSetWithIntersection lattice, but covering sets of arbitrary ordered values.

ArcOrdSetWithUnion

This is the same semantics as the BitSetWithUnion lattice, but covering sets of arbitrary ordered values.

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 Option<BTreeMap> and the unit is again a putative “maximum” map-with-all-possible-keys (represented by None).

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 BitSetWithIntersection lattice, but covering sets of arbitrary ordered values.

BTreeSetWithUnion

This is the same semantics as the BitSetWithUnion lattice, but covering sets of arbitrary ordered values.

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 LatticeDef.

MaxDef

This lattice definition recycles the Ord::max and Ord::cmp of its element type, as well as using Default::default as its unit. In other words this is the “most normal” lattice over unsigned scalar, vector or string types, probably the one you want most of the time.

MaxNum

This lattice definition recycles the Ord::max and Ord::cmp of its element type, as well as using Bounded::min_value as its unit. This is similar to MaxDef except it works with signed types: the default value of a signed type is still 0 and that’s not a unit with respect to Ord::max in a lattice with negative numbers.

MinNum

This is like MinOpt but for numeric (or specifically Bounded) types that have a numeric upper bound: it uses that as the unit rather than the additional “maximal value” tacked on in MinOpt. Best option for numeric lattices with join as minimum.

MinOpt

This lattice is similar to MaxDef but inverts the order, with the minimal value according to Ord::cmp as its join, and the unit being a putative “maximal” value of the element type. Since several Ord types do not have a maximal value (think strings, maps, etc.) MinOpt represents its element using an Option where None is the “maximal” value (that forms the lattice unit) and Some is for the other non-unit values.

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 Option<BTreeMap> and the unit is again a putative “maximum” map-with-all-possible-keys (represented by None).

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 BitSetWithIntersection lattice, but covering sets of arbitrary ordered values.

RcOrdSetWithUnion

This is the same semantics as the BitSetWithUnion lattice, but covering sets of arbitrary ordered values.

Tuple2

Cartesian product lattice for 2 inner lattices, joining elements pairwise and with the product partial order (not lexicographical order) where (a, b) <= (c, d) iff a <= c and b <= d.

Tuple3

Cartesian product lattice for 3 inner lattices, joining elements pairwise and with the product partial order (not lexicographical order) where (a, b, c) <= (d, e, f) iff a <= d and b <= e and c <= f.

Tuple4

Cartesian product lattice for 4 inner lattices, joining elements pairwise and with the product partial order (not lexicographical order) where (a, b, c, d) <= (e, f, g, h) iff a <= e and b <= f and c <= g and d <= h.

Tuple5

Cartesian product lattice for 5 inner lattices, joining elements pairwise and with the product partial order (not lexicographical order) where (a, b, c, d, e) <= (f, g, h, i, j) iff a <= f and b <= g and c <= h and d <= i and e <= j.

Traits

DefTraits

DefTraits is used to constrain LatticeDefs and also type parameters of structs that implement LatticeDef. This requires some explaining.

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 Default::default is safe to use as a unit for a max-lattice. In particular it’s not safe in types like signed integers, where there are many values less than Default::default.

MaxUnitMinValue

A marker type for other types that use the Bounded::min_value as the unit for a max-lattice.

ValTraits

ValTraits is used to constrain the LatticeDef::T types to include basic assumptions we need all datatypes to support. But notably not Ord! While several LatticeDef type parameters do require Ord (which is because of the the deriving-bug workaround described in the docs of DefTraits) the partial orders of the lattice are separate and defined by the LatticeDefs themselves, and several important LatticeDef::T types are not totally ordered at all (namely all the set-like and map-like ones).