Crate postbox

Crate postbox 

Source
Expand description

§postbox — lattice basics + async join cells

Part of the postbox workspace

Core pieces:

  • lattice: traits and helpers for lattices (join, meet, and bounded variants)
  • crdt: classic state-based CRDTs built on those lattices:
  • lvar (feature = “async”): an LVar-style cell whose state only grows by lattice join
  • propagator (feature = “async”): propagator networks for accumulative computation with semigroup-valued cells
  • join_stream_ext (feature = “async”): stream adapters to fold Stream<Item = L> by lattice join
  • mvar (feature = “async”): a classic MVar (single-slot put/take), separate from the monotone cell

§Concepts

A join-semilattice is a type L with an operation join: &L × &L → L that is associative, commutative, and idempotent. It induces an order x ≤ y iff x.join(y) == y.

  • Common joins: max (on numbers), union (on sets), min (on the dual order).
  • If a bottom element ⊥ exists, implement BoundedJoinSemilattice so you can fold from empty.

A meet-semilattice has the dual meet operation (greatest lower bound). A lattice has both join and meet. When both bottom and top exist, it’s a bounded lattice.

§Features

This crate has several optional features (all enabled by default):

  • async (enabled by default): Enables async/await support, including:

    • lvar::LVar: monotone lattice variables with async waiting
    • mvar::MVar: classic single-slot async cells
    • join_stream_ext: stream folding with lattice join
    • Requires tokio and futures dependencies

  • derive (enabled by default): Provides derive macros for automatic trait implementations:

    • #[derive(JoinSemilattice)]: derive join from field-wise joins
    • #[derive(BoundedJoinSemilattice)]: derive bottom from field-wise bottoms
    • #[derive(MeetSemilattice)]: derive meet from field-wise meets
    • #[derive(BoundedMeetSemilattice)]: derive top from field-wise tops

  • bitflags (enabled by default): Adds support for using BitOr with types from the bitflags crate

    • Enables testing and documentation for bitflags integration

To use only the core lattice types without async or derives:

postbox = { version = "…", default-features = false }

§Quick start

use std::collections::HashSet;
use postbox::lattice::BoundedJoinSemilattice;
use postbox::lattice::JoinSemilattice;

// Join = union on sets
let a: HashSet<_> = [1,2].into_iter().collect();
let b: HashSet<_> = [2,3].into_iter().collect();
let j = a.join(&b);
assert_eq!(j, HashSet::from([1,2,3]));
assert!(HashSet::<i32>::bottom().is_empty());

§Async example

postbox = { version = "…", features = ["async"] }
ⓘ
use std::collections::HashSet;
use postbox::LVar;

let cell = LVar::<HashSet<&'static str>>::new();
let target: HashSet<_> = ["a","b","c"].into_iter().collect();
let waiter = {
  let cell = cell.clone();
  tokio::spawn(async move { cell.await_at_least(&target).await })
};
cell.put_join(&HashSet::from(["a"]));
cell.put_join(&HashSet::from(["b","c"]));
let got = waiter.await.unwrap();
assert!(target.is_subset(&got));

Modules§

crdt
CRDTs built on lattice combinators Basic state-based CRDTs built on lattice primitives.
join_stream_ext
Stream extensions for folding by lattice joins (uses futures::Stream). Stream extensions for join-semilattices (feature = "async").
lattice
Core algebra: lattice traits (join, meet, bounded variants) and standard helpers. Core lattice traits and building blocks.
lvar
Join-only, monotone cell (LVar): state increases via lattice join. Async LVar-style monotone cell built on join-semilattices.
mvar
A classic single-slot async MVar (blocking put/take). Not monotone. MVar-style for Rust (tokio)
propagator
Propagator networks for monotonic computation with lattice-valued cells. Propagator networks for accumulative computation with algebraic cells.

Traits§

BoundedJoinSemilattice
A bounded join-semilattice: a join-semilattice with a bottom element.
BoundedLattice
A bounded lattice: a lattice with both bottom and top elements.
BoundedMeetSemilattice
A bounded meet-semilattice: a meet-semilattice with a top element.
JoinSemilattice
A join-semilattice: a type with an associative, commutative, idempotent binary operation.
Lattice
A lattice: a type with both join (least upper bound) and meet (greatest lower bound) operations.
MeetSemilattice
A meet-semilattice: a type with an associative, commutative, idempotent binary operation that computes greatest lower bounds.

Derive Macros§

BoundedJoinSemilattice
Derive macro for BoundedJoinSemilattice.
BoundedMeetSemilattice
Derive macro for BoundedMeetSemilattice.
JoinSemilattice
Derive macro for JoinSemilattice.
MeetSemilattice
Derive macro for MeetSemilattice.