vthread 0.0.1

Bounded carrier-affine virtual threads for Rust
Documentation
use super::{Graph, Kind, Signature};
use std::{
    collections::BTreeSet,
    sync::{Arc, atomic::AtomicBool},
};

#[derive(Default)]
struct Reference {
    nodes: Vec<ReferenceNode>,
}

struct ReferenceNode {
    cancelled: bool,
    children: Vec<usize>,
}

impl Reference {
    fn insert(&mut self, parents: &[usize]) -> usize {
        let id = self.nodes.len();
        let cancelled = parents.iter().any(|parent| self.nodes[*parent].cancelled);
        self.nodes.push(ReferenceNode {
            cancelled,
            children: Vec::new(),
        });
        for parent in parents {
            self.nodes[*parent].children.push(id);
        }
        id
    }

    fn cancel(&mut self, id: usize) {
        let mut pending = vec![id];
        while let Some(id) = pending.pop() {
            if self.nodes[id].cancelled {
                continue;
            }
            self.nodes[id].cancelled = true;
            pending.extend(self.nodes[id].children.clone());
        }
    }
}

fn insert(graph: &mut Graph, reference: &mut Reference, parents: &[usize]) -> usize {
    let expected = reference.insert(parents);
    let actual = graph.insert(parents, Arc::new(AtomicBool::new(false)));
    assert_eq!(actual, expected);
    actual
}

fn assert_equivalent(graph: &Graph, reference: &Reference, live: &[usize], step: usize) {
    for id in live {
        assert_eq!(
            graph.is_cancelled(*id),
            reference.nodes[*id].cancelled,
            "step={step} token={id}"
        );
    }
    let actual_relays = graph
        .nodes
        .values()
        .filter(|entry| entry.kind == Kind::Relay)
        .count();
    assert_eq!(actual_relays, graph.relays);
    for (id, entry) in &graph.nodes {
        if entry.kind == Kind::Relay {
            assert!(entry.parents.len() > 1, "step={step} unary parents at {id}");
            assert!(
                entry.children.len() > 1,
                "step={step} unary children at {id}"
            );
            let expected = entry
                .parents
                .iter()
                .fold(Signature::default(), |set, parent| {
                    set.union(&graph.nodes[parent].signature)
                });
            assert!(entry.signature.same_set(&expected));
            assert!(graph.relay_index[&entry.signature.candidate()].contains(id));
        } else {
            assert!(entry.signature.same_set(&Signature::singleton(*id)));
        }
        for parent in &entry.parents {
            let predecessor = &graph.nodes[parent];
            assert!(predecessor.children.contains(id));
            assert!(parent < id);
            assert!(!predecessor.cancelled || entry.cancelled);
        }
        for child in &entry.children {
            assert!(graph.nodes[child].parents.contains(id));
            assert!(id < child);
        }
    }
    for (candidate, ids) in &graph.relay_index {
        for id in ids {
            let entry = &graph.nodes[id];
            assert_eq!(*candidate, entry.signature.candidate());
            assert_eq!(entry.kind, Kind::Relay);
        }
    }
}

#[test]
fn compressed_graph_matches_a_non_pruning_reference_under_mixed_operations() {
    let mut graph = Graph::default();
    let mut reference = Reference::default();
    let mut live = Vec::new();
    let mut seed = 0x4d59_5df4_d0f3_3173_u64;

    for step in 0..5_000 {
        seed = seed
            .wrapping_mul(6_364_136_223_846_793_005)
            .wrapping_add(1_442_695_040_888_963_407);
        let choice = (seed >> 32) as usize % 100;
        if live.len() < 4 || (choice < 48 && live.len() < 48) {
            let count = ((seed >> 16) as usize % 3).min(live.len());
            let mut parents = BTreeSet::new();
            let mut cursor = seed;
            while parents.len() < count {
                cursor = cursor.rotate_left(17).wrapping_add(0x9e37_79b9_7f4a_7c15);
                parents.insert(live[(cursor as usize) % live.len()]);
            }
            let parents = parents.into_iter().collect::<Vec<_>>();
            live.push(insert(&mut graph, &mut reference, &parents));
        } else {
            let index = (seed as usize) % live.len();
            let id = live[index];
            if choice < 72 {
                graph.cancel(id);
                reference.cancel(id);
            } else {
                graph.remove(id);
                live.swap_remove(index);
            }
        }
        assert_equivalent(&graph, &reference, &live, step);
    }
}