vthread 0.1.0

Bounded carrier-affine virtual threads for Rust
Documentation
fn max_depth(signature: &Signature) -> usize {
    let root = match &signature.0 {
        Root::Empty => return 0,
        Root::Singleton(_) => return 1,
        Root::Tree(root) => root,
    };
    let mut depth = 0;
    let mut pending = vec![(root.as_ref(), 1)];
    while let Some((node, current)) = pending.pop() {
        depth = depth.max(current);
        if let NodeKind::Branch { left, right, .. } = &node.kind {
            pending.push((left.as_ref(), current + 1));
            pending.push((right.as_ref(), current + 1));
        }
    }
    depth
}

use super::{NodeKind, Root, Signature};

#[test]
fn singleton_signatures_stay_inline() {
    assert!(matches!(Signature::singleton(7).0, Root::Singleton(7)));
}

#[test]
fn insertion_order_does_not_change_exact_set_identity() {
    let mut forward = Signature::default();
    let mut reverse = Signature::default();
    for id in 0..1_000 {
        forward = forward.union(&Signature::singleton(id));
    }
    for id in (0..1_000).rev() {
        reverse = reverse.union(&Signature::singleton(id));
    }
    assert_eq!(forward.candidate(), reverse.candidate());
    assert!(forward.same_set(&reverse));
    assert!(max_depth(&forward) <= usize::BITS as usize + 1);
}

#[test]
fn union_is_exact_idempotent_and_structurally_bounded() {
    let mut even = Signature::default();
    let mut odd = Signature::default();
    for id in 0..10_000 {
        let item = Signature::singleton(id);
        if id % 2 == 0 {
            even = even.union(&item);
        } else {
            odd = odd.union(&item);
        }
    }
    let all = even.union(&odd);
    assert_eq!(all.cardinality(), 10_000);
    assert!(all.same_set(&all.union(&even)));
    assert!(max_depth(&all) <= usize::BITS as usize + 1);
    assert!(!even.same_set(&odd));
}

#[test]
fn structurally_shared_equality_visits_only_changed_paths() {
    let mut base = Signature::default();
    for id in 0..10_000 {
        base = base.union(&Signature::singleton(id));
    }
    let addition = Signature::singleton(20_000);
    let (left, left_work) = base.union_counted(&addition);
    let (right, right_work) = base.union_counted(&addition);
    assert_eq!(left_work.union_items, 1);
    assert_eq!(right_work.union_items, 1);
    assert!(left_work.allocated_nodes <= usize::BITS as usize + 2);
    assert!(right_work.allocated_nodes <= usize::BITS as usize + 2);

    let (same, comparison) = left.same_set_counted(&right);
    assert!(same);
    assert!(
        comparison.equality_nodes <= 2 * usize::BITS as usize + 3,
        "shared equality visited {} Patricia nodes",
        comparison.equality_nodes
    );
    assert_eq!(comparison.union_items, 0);
    assert_eq!(comparison.allocated_nodes, 0);
}