[−][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);

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 `LatticeDef`s 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 `LatticeDef`s themselves, and several important `LatticeDef::T` types are not totally ordered at all (namely all the set-like and map-like ones).