clipasm 0.5.0

A strict, typed language for compiling and rendering Video and Audio graphs
Documentation
//! Monotonic type-variable storage and unification.

use crate::model::ValueType;

#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub(super) struct TypeVarId(u32);

impl TypeVarId {
    const fn index(self) -> usize {
        self.0 as usize
    }
}

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub(super) struct TypeDomain(u8);

impl TypeDomain {
    const VIDEO: u8 = 0b01;
    const AUDIO: u8 = 0b10;
    pub(super) const TIMELINE: Self = Self(Self::VIDEO | Self::AUDIO);

    #[must_use]
    pub(super) const fn from_value_type(value_type: ValueType) -> Self {
        match value_type {
            ValueType::Video => Self(Self::VIDEO),
            ValueType::Audio => Self(Self::AUDIO),
        }
    }

    #[cfg(test)]
    #[must_use]
    pub(super) const fn contains(self, value_type: ValueType) -> bool {
        let candidate = Self::from_value_type(value_type);
        candidate.0 != 0 && self.0 & candidate.0 == candidate.0
    }

    #[must_use]
    pub(super) const fn intersection(self, other: Self) -> Self {
        Self(self.0 & other.0)
    }

    #[must_use]
    pub(super) const fn is_subset_of(self, other: Self) -> bool {
        self.0 & !other.0 == 0
    }

    #[must_use]
    pub(super) const fn overlaps(self, other: Self) -> bool {
        self.0 & other.0 != 0
    }

    #[must_use]
    pub(super) const fn is_empty(self) -> bool {
        self.0 == 0
    }

    #[must_use]
    pub(super) const fn concrete(self) -> Option<ValueType> {
        match self.0 {
            Self::VIDEO => Some(ValueType::Video),
            Self::AUDIO => Some(ValueType::Audio),
            _ => None,
        }
    }
}

impl From<ValueType> for TypeDomain {
    fn from(value_type: ValueType) -> Self {
        Self::from_value_type(value_type)
    }
}

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) struct TypeConflict {
    pub(super) left: TypeDomain,
    pub(super) right: TypeDomain,
}

#[derive(Clone, Debug)]
struct TypeNode {
    parent: TypeVarId,
    domain: TypeDomain,
    rank: u8,
}

#[derive(Clone, Debug, Default)]
pub(super) struct TypeArena {
    nodes: Vec<TypeNode>,
    revision: u64,
}

impl TypeArena {
    #[must_use]
    pub(super) fn allocate(&mut self) -> TypeVarId {
        self.allocate_domain(TypeDomain::TIMELINE)
    }

    #[must_use]
    pub(super) fn allocate_exact(&mut self, value_type: ValueType) -> TypeVarId {
        self.allocate_domain(value_type.into())
    }

    pub(super) fn equate(
        &mut self,
        left: TypeVarId,
        right: TypeVarId,
    ) -> std::result::Result<(), TypeConflict> {
        let left_root = self.root(left);
        let right_root = self.root(right);
        let left_domain = self.nodes[left_root.index()].domain;
        let right_domain = self.nodes[right_root.index()].domain;
        let intersection = left_domain.intersection(right_domain);

        if intersection.is_empty() {
            return Err(TypeConflict {
                left: left_domain,
                right: right_domain,
            });
        }
        if left_root == right_root {
            return Ok(());
        }

        let left_rank = self.nodes[left_root.index()].rank;
        let right_rank = self.nodes[right_root.index()].rank;
        let (parent, child) = if left_rank < right_rank {
            (right_root, left_root)
        } else {
            (left_root, right_root)
        };

        self.nodes[child.index()].parent = parent;
        self.nodes[parent.index()].domain = intersection;
        if left_rank == right_rank {
            self.nodes[parent.index()].rank = self.nodes[parent.index()]
                .rank
                .checked_add(1)
                .expect("type arena rank overflow");
        }
        self.bump_revision();
        Ok(())
    }

    pub(super) fn constrain(
        &mut self,
        variable: TypeVarId,
        value_type: ValueType,
    ) -> std::result::Result<(), TypeConflict> {
        let root = self.root(variable);
        let current = self.nodes[root.index()].domain;
        let required = TypeDomain::from(value_type);
        let intersection = current.intersection(required);

        if intersection.is_empty() {
            return Err(TypeConflict {
                left: current,
                right: required,
            });
        }
        if intersection != current {
            self.nodes[root.index()].domain = intersection;
            self.bump_revision();
        }
        Ok(())
    }

    pub(super) fn constrain_domain(
        &mut self,
        variable: TypeVarId,
        required: TypeDomain,
    ) -> std::result::Result<(), TypeConflict> {
        let root = self.root(variable);
        let current = self.nodes[root.index()].domain;
        let intersection = current.intersection(required);

        if intersection.is_empty() {
            return Err(TypeConflict {
                left: current,
                right: required,
            });
        }
        if intersection != current {
            self.nodes[root.index()].domain = intersection;
            self.bump_revision();
        }
        Ok(())
    }

    #[must_use]
    pub(super) fn domain(&self, variable: TypeVarId) -> TypeDomain {
        self.nodes[self.root(variable).index()].domain
    }

    #[must_use]
    pub(super) const fn revision(&self) -> u64 {
        self.revision
    }

    fn allocate_domain(&mut self, domain: TypeDomain) -> TypeVarId {
        let raw = u32::try_from(self.nodes.len()).expect("too many type variables");
        let variable = TypeVarId(raw);
        self.nodes.push(TypeNode {
            parent: variable,
            domain,
            rank: 0,
        });
        self.bump_revision();
        variable
    }

    fn root(&self, variable: TypeVarId) -> TypeVarId {
        let mut current = variable;
        loop {
            let parent = self.nodes[current.index()].parent;
            if parent == current {
                return current;
            }
            current = parent;
        }
    }

    fn bump_revision(&mut self) {
        self.revision = self
            .revision
            .checked_add(1)
            .expect("type arena revision overflow");
    }
}