vthread 0.0.1

Bounded carrier-affine virtual threads for Rust
Documentation
//! Compressed cancellation graph; callers serialize every transition.

use std::{
    collections::{BTreeMap, BTreeSet},
    sync::{
        Arc,
        atomic::{AtomicBool, Ordering},
    },
};

#[path = "cancellation_signature.rs"]
mod signature;
use signature::{Candidate, Signature};

#[path = "cancellation_graph_normalize.rs"]
mod normalize;
#[path = "cancellation_graph_rewrite.rs"]
mod rewrite;
use normalize::RelayWork;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum Kind {
    Token,
    Relay,
}

struct Entry {
    kind: Kind,
    flag: Option<Arc<AtomicBool>>,
    cancelled: bool,
    parents: BTreeSet<usize>,
    children: BTreeSet<usize>,
    signature: Signature,
}

#[cfg(test)]
#[derive(Clone, Copy, Debug, Default)]
pub(super) struct WorkSnapshot {
    pub(super) union_items: usize,
    pub(super) equality_nodes: usize,
    pub(super) allocated_nodes: usize,
    pub(super) candidate_checks: usize,
    pub(super) relay_checks: usize,
    pub(super) topology_rebuilds: usize,
}

#[derive(Default)]
pub(super) struct Graph {
    next: usize,
    relays: usize,
    nodes: BTreeMap<usize, Entry>,
    relay_index: BTreeMap<Candidate, BTreeSet<usize>>,
    #[cfg(test)]
    work: WorkSnapshot,
}

impl Graph {
    pub(super) fn insert(&mut self, parents: &[usize], flag: Arc<AtomicBool>) -> usize {
        let id = self.next;
        self.next = self
            .next
            .checked_add(1)
            .expect("cancellation identity exhausted");
        let parents = parents.iter().copied().collect::<BTreeSet<_>>();
        let cancelled = parents.iter().any(|parent| self.nodes[parent].cancelled);
        flag.store(cancelled, Ordering::Release);
        for parent in &parents {
            self.nodes
                .get_mut(parent)
                .expect("live parent")
                .children
                .insert(id);
        }
        self.nodes.insert(
            id,
            Entry {
                kind: Kind::Token,
                flag: Some(flag),
                cancelled,
                parents,
                children: BTreeSet::new(),
                signature: Signature::singleton(id),
            },
        );
        id
    }

    pub(super) fn remove(&mut self, id: usize) {
        let (parents, children, inherited, relay) = {
            let entry = self.nodes.get(&id).expect("live cancellation node");
            assert_eq!(entry.kind, Kind::Token, "token removed twice");
            (
                entry.parents.clone(),
                entry.children.clone(),
                entry
                    .parents
                    .iter()
                    .any(|parent| self.nodes[parent].cancelled),
                entry.parents.len() > 1 && entry.children.len() > 1,
            )
        };
        if relay {
            let signature = self.signature_for(&parents);
            let entry = self.nodes.get_mut(&id).expect("live cancellation node");
            entry.kind = Kind::Relay;
            entry.flag = None;
            entry.cancelled = inherited;
            entry.signature = signature;
            self.relays += 1;
            self.index_relay(id);
            self.normalize(
                std::iter::once(RelayWork::known(id))
                    .chain(children.into_iter().map(RelayWork::dirty)),
            );
        } else {
            let affected = self.erase(id, true, true);
            self.normalize(affected);
        }
    }

    pub(super) fn cancel(&mut self, id: usize) {
        let mut pending = vec![id];
        let mut changed_relays = Vec::new();
        while let Some(id) = pending.pop() {
            let children = {
                let node = self.nodes.get_mut(&id).expect("live cancellation path");
                if node.cancelled {
                    continue;
                }
                node.cancelled = true;
                if let Some(flag) = &node.flag {
                    flag.store(true, Ordering::Release);
                } else {
                    changed_relays.push(id);
                }
                node.children.iter().copied().collect::<Vec<_>>()
            };
            pending.extend(children);
        }
        self.normalize(changed_relays.into_iter().map(RelayWork::known));
    }

    pub(super) fn is_cancelled(&self, id: usize) -> bool {
        self.nodes[&id].cancelled
    }

    #[cfg(test)]
    pub(super) fn snapshot(&self) -> (usize, usize, usize) {
        let tokens = self
            .nodes
            .values()
            .filter(|entry| entry.kind == Kind::Token)
            .count();
        let links = self.nodes.values().map(|entry| entry.children.len()).sum();
        (tokens, self.relays, links)
    }

    #[cfg(test)]
    pub(super) fn work_snapshot(&self) -> WorkSnapshot {
        self.work
    }

    #[cfg(test)]
    pub(super) fn reset_work(&mut self) {
        self.work = WorkSnapshot::default();
    }

    #[cfg(test)]
    fn record_signature_work(&mut self, work: signature::Work) {
        self.work.union_items += work.union_items;
        self.work.equality_nodes += work.equality_nodes;
        self.work.allocated_nodes += work.allocated_nodes;
    }
}

#[cfg(test)]
#[path = "cancellation_graph_test.rs"]
mod cancellation_graph_test;

#[cfg(test)]
#[path = "cancellation_graph_differential_test.rs"]
mod cancellation_graph_differential_test;